Понятие делимости – это одно из основных понятий арифметики и теории чисел. Мы будем говорить о делимости целых чисел и в частных случаях - о делимостинатуральных чисел. Итак, дадим представление о делимости на множестве целых чисел.
Делимость натуральных чисел. Деление с остатком
Определение 1. Говорят, что натуральное число a делится на натуральное число b, если существует такое натуральное число c, что выполняется равенство
a = bc.
В противном случае говорят, что число a не делится начисло b.
Если число a больше, чем число b, и не делится на число b, то число a можно разделить на число b с остатком.
Определение 2.Деление числа a на число b с остатком означает, что найдутся такие натуральные числа c и r, что выполняются соотношения
a = bc + r, r < b.
Число b называется делителем, число c – частным, а число r – остатком от деления a на b.
Еще раз особо подчеркнем, что остаток r всегда меньше, чем делитель b.
Например, число 204 не делится на число 5, но, разделив число 204 на 5 с остатком, получаем:
Таким образом, частное от деления равно 40, а остаток равен 4.
Определение 3. Числа, делящиеся на 2, называют четными, а числа, которые не делятся на 2, называют нечетными.
Признаки делимости
Для того, чтобы быстро выяснить, делится ли одно натуральное число на другое, существуют признаки делимости.
| Признак делимости на | Формулировка | Пример |
| Число должно оканчиваться четной цифрой: 0, 2, 4, 6, 8 | ||
| Сумма цифр числа должна делиться на 3 | 745, (7 + 4 + 5 = 15) | |
| Число, образованное двумя последними цифрами, должно делиться на 4 | ||
| Число должно оканчиваться цифрой 0 или 5 | ||
| Число должно делиться на 2 и на 3 | 234, (2 + 3 + 4 = 9) | |
| На 7 должно делиться число, полученноевычитанием удвоенной последней цифры из исходного числа с отброшенной последней цифрой | 3626, (362 – 12 = 350) | |
| Число, образованное тремя последними цифрами, должно делиться на 8 | ||
| Сумма цифр должна делиться на 9 | 2574, (2 + 5 + 7 + 4 = 18) | |
| Число должно оканчиваться 0 | ||
| Сумма цифр, стоящих на четных местах, либо равна сумме цифр, стоящих на нечетных местах, либо отличается от нее на число, делящееся на 11 | 1408, (4 + 8 = 12; 1 + 0 = 1; 12 – 1 = 11) | |
| На 13 должно делиться число, полученноедобавлением учетверенной последней цифры к исходному числу с отброшенной последней цифрой | 299, (29 + 36 = 65) | |
| Число должно оканчиваться на 00, 25, 50 или 75 | ||
| Число должно оканчиваться на 00 или 50 | ||
| Число должно оканчиваться на 00 | ||
| Число должно оканчиваться на 000 |
Свойства делимости
Делимость обладает рядом характерных свойств. Перечислим и обоснуем основные свойства делимости, которые следуют из понятия делимости и свойств операций над целыми числами.
1. Любое целое число a делится на число a, на число −a, противоположное числу a, на единицу и на число −1.
Докажем это свойство делимости.
Для любого целого числа a справедливы равенства a=a·1 и a=1·a, из которых следует, что a делится на a, причем частное равно единице, и что a делится на 1, причем частное равно a. Для любого целого числа a также справедливы равенства a=(−a)·(−1) и a=(−1)·(−a), из которых следует делимость a на число, противоположное числу a, а также делимость a на минус единицу.
Отметим, что свойство делимости целого числа a на себя называют свойством рефлексивности.
2. Следующее свойство делимости утверждает, что нуль делится на любое целое число b.
Действительно, так как 0=b·0 для любого целого числа b, то нуль делится на любое целое число.
В частности, нуль делится и на нуль. Это подтверждает равенство 0=0·q, где q – любое целое число. Из этого равенства вытекает, что частным от деления нуля на нуль является любое целое число.
Также нужно отметить, что на 0 не делится никакое другое целое число a, отличное нуля. Поясним это. Если бы нуль делил целое число a, отличное от нуля, то должно было бы быть справедливо равенство a=0·q, где q – некоторое целое число, а последнее равенство возможно только при a=0.
3. Если целое число a делится на целое число b и модуль числа a меньше модуля числа b, то a равно нулю. В буквенном виде это свойство делимости записывается так: если a 
b и 
, то a=0.
Доказательство.
Так как a делится на b, то существует целое число q, при котором верно равенство a=b·q. Тогда должно быть справедливо и равенство 
, а в силу свойств модуля числа должно быть справедливо и равенство вида 
. Если q не равно нулю, то 
, откуда следует, что 
. Учитывая полученное неравенство, из равенства следует, что 
. Но это противоречит условию . Таким образом, q может быть равно только нулю, при этом получим a=b·q=b·0=0, что и требовалось доказать.
4. Если целое число a отлично от нуля и делится на целое число b, то модуль числа a не меньше модуля числа b. То есть, если a≠0 и a b, то . Это свойство делимости непосредственно вытекает из предыдущего.
5. Делителями единицы являются только целые числа 1 и −1.
Во-первых, покажем, что единица делится на 1 и на −1. Это следует из равенств 1=1·1 и 1=(−1)·(−1).
Осталось доказать, что никакое другое целое число не является делителем единицы.
Предположим, что целое число b, отличное от 1 и −1, является делителем единицы. Так как единица делится на b, то в силу предыдущего свойства делимости должно выполняться неравенство 
, которое равносильно неравенству 
. Этому неравенству удовлетворяют только три целых числа: 1, 0, и −1. Так как мы приняли, что b отлично от 1 и −1, то остается лишь b=0. Но b=0 не может быть делителем единицы (что мы показали при описании второго свойства делимости). Этим доказано, что никакие числа, отличные от 1 и −1, не являются делителями единицы.
6. Чтобы целое число a делилось на целое число b необходимо и достаточно, чтобы модуль числа a делился на модуль числа b.
Докажем сначала необходимость.
Пусть a делится на b, тогда существует такое целое число q, что a=b·q. Тогда 
. Так как 
является целым числом, то из равенства следует делимость модуля числа a на модуль числа b.
Теперь достаточность.
Пусть модуль числа a делится на модуль числа b, тогда существует такое целое число q, что 
. Если числа a и b положительные, то справедливо равенство a=b·q, которое доказывает делимость a на b. Если a и b отрицательные, то верно равенство −a=(−b)·q, которое можно переписать как a=b·q. Если a – отрицательное число, а b – положительное, то имеем −a=b·q, это равенство равносильно равенству a=b·(−q). Если a – положительное, а b – отрицательное, то имеем a=(−b)·q, и a=b·(−q). Так как и q и −q являются целыми числами, то полученные равенства доказывают, что a делится на b.
Следствие 1.
Если целое число a делится на целое число b, то a также делится на число −b, противоположное числу b.
Следствие 2.
Если целое число a делится на целое число b, то и −a делится на b.
Важность только что рассмотренного свойства делимости сложно переоценить - теорию делимости можно описывать на множестве целых положительных чисел, а это свойства делимости распространяет ее и на целые отрицательные числа.
7. Делимость обладает свойством транзитивности: если целое число a делится на некоторое целое число m, а число m в свою очередь делится на некоторое целое число b, то a делится на b. То есть, если a m и m b, то a b.
Приведем доказательство этого свойства делимости.
Так как a делится на m, то существует некоторое целое число a1 такое, что a=m·a1. Аналогично, так как m делится на b, то существует некоторое целое число m1 такое, что m=b·m1. Тогда a=m·a1=(b·m1)·a1=b·(m1·a1). Так как произведение двух целых чисел является целым числом, то m1·a1 - это некоторое целое число. Обозначив его q, приходим к равенству a=b·q, которое доказывает рассматриваемое свойство делимости.
8. Делимость обладает свойством антисимметричности, то есть, если a делится на b и одновременно b делится на a, то равны либо целые числа a и b, либо числа a и −b.
Из делимости a на b и b на a можно говорить о существовании целых чисел q1 и q2 таких, что a=b·q1 и b=a·q2. Подставив во второе равенство b·q1 вместо a, или подставив в первое равенство a·q2 вместо b, получим, что q1·q2=1, а учитывая, что q1 и q2 – целые, это возможно лишь при q1=q2=1 или при q1=q2=−1. Отсюда следует, что a=b или a=−b (или, что то же самое, b=a или b=−a).
9. Для любого целого и отличного от нуля числа b найдется такое целое число a, не равное b, которое делится на b.
Таким числом будет любое из чисел a=b·q, где q – любое целое число, не равное единице. Можно переходить к следующему свойству делимости.
10. Если каждое из двух целых слагаемых a и b делится на целое число c, то сумма a+b также делится на c.
Так как a и b делятся на c, то можно записать a=c··q1 и b=c·q2. Тогда a+b=c·q1+c·q2=c·(q1+q2) (последний переход возможен в силураспределительного свойства умножения целых чисел относительно сложения). Так как сумма двух целых чисел является целым числом, то равенство a+b=c·(q1+q2) доказывает делимость суммы a+b на c.
Это свойство можно распространить на сумму трех, четырех и большего количества слагаемых.
Если еще вспомнить, что вычитание из целого числа a целого числа b представляет собой сложение числа a с числом −b (смотрите правило вычитания целых чисел), то данное свойство делимости справедливо и для разности чисел. Например, если целые числа a и b делятся на c, то разность a−b также делится на с.
11. Если известно, что в равенстве вида k+l+…+n=p+q+…+s все члены, кроме какого-то одного, делятся на некоторое целое число b, то и этот один член делится на b.
Допустим, этим членом является p (мы можем взять любой из членов равенства, что не повлияет на рассуждения). Тогда p=k+l+…+n−q−…−s. Выражение, получившееся в правой части равенства, делится на b в силу предыдущего свойства. Следовательно, число p также делится на b.
12. Если целое число a делится на целое число b, то произведение a·k, где k – произвольное целое число, делится на b.
Так как a делится на b, то справедливо равенство a=b·q, где q – некоторое целое число. Тогда a·k=(b·q)·k=b·(q·k) (последний переход осуществлен в силу сочетательного свойства умножения целых чисел). Так как произведение двух целых чисел есть целое число, то равенство a·k=b·(q·k) доказывает делимость произведения a·k на b.
Следствие: если целое число a делится на целое число b, то произведение a·k1·k2·…·kn, где k1, k2, …, kn – некоторые целые числа, делится на b.
13. Если целые числа a и b делятся на c, то сумма произведений a·u и b·v вида a·u+b·v, где u и v – произвольные целые числа, делится на c.
Доказательство этого свойства делимости аналогично двум предыдущим. Из условия имеем a=c·q1 и b=c·q2. Тогда a·u+b·v=(c·q1)·u+(c·q2)·v=c·(q1·u+q2·v). Так как сумма q1·u+q2·v является целым числом, то равенство вида a·u+b·v=c·(q1·u+q2·v) доказывает, что a·u+b·v делится на c.
