Объяснение и обоснование
1. Делимость целых чисел. Говорят, что целое число a делится (нацело) на целое число b (где b ≠ 0), если существует такое целое число c, что справедливо равенство a = bc.
Часто утверждение «a делится на b» записывают так .
Числа b и c называют делителями числа a (а число а называют кратным числам b и c). Например, поскольку 6 = 1⋅6 = (–1)⋅(–6) = 2⋅3 =
= (–2) ⋅ (–3), то делителями целого числа 6 являются целые числа: 1; –1; 2; –2; 3; –3; 6; –6 (и следовательно, целое число 6 кратно этим числам).
Наименьшее натуральное число, которое делится на каждое из натуральных чисел а и b, называют наименьшим общим кратным (НОК) чисел а и b.
Наибольшее из натуральных чисел, являющихся одновременно делителями натуральных чисел а и b, называют наибольшим общим делителем (НОД) чисел а и b.
Например, для чисел а = 40 и b = 24 их НОД равен 8, а НОК равен 120.
Два натуральных числа называют взаимно простыми, если их наибольший общий делитель равен 1. Например, числа 6 и 55 взаимно просты, так как натуральными делителями числа 6 являются числа 1, 2, 3, 6, а натуральными делителями числа 55 являются числа 1, 5, 11, 55, то есть
НОД (6; 55) = 1.
Для решения задач приходится использовать свойства делимости целых чисел, которые приведены в таблице 15.

Рассмотрим, например, доказательство свойства 2:


если каждое из чисел делится на c, то их сумма или разность
тоже делится на c.
Рассматривая только натуральные целые числа, можно отметить, что у каждого натурального числа a > 1 есть два натуральных делителя: 1 и a. Если у натурального числа а > 1 нет других натуральных делителей, кроме 1 и а, то это число называют простым. Если у натурального числа а > 1 есть натуральные делители, отличные от 1 и а, то это число называют составным. Число 1 не относится ни к простым, ни к составным числам.
Справедлива основная теорема арифметики.
Теорема. Любое натуральное число, большее единицы, можно разложить на произведение простых чисел, причем это разложение1 единственное с точностью до порядка множителей:
— простые числа.
Например, 35 = 5 ⋅ 7, 17 = 17, 36 = 2 ⋅ 2 ⋅ 3 ⋅ 3 = 22 ⋅ 32.
Запись  называют каноническим разложением числа — различные простые числа, — натуральные числа).
Заметим, что если  — каноническое разложение числа а, то число а может делиться только на такое натуральное число d, в каноническом разложении которого на простые множители нет других простых множителей, кроме , и степени соответствующих простых множителей не могут превышать соответствующую степень в каноническом разложении числа а. Поэтому натуральными делителями числа а будут только числа
 
Если  — целое число, то может принимать всего значений . Аналогично может принимать всего значений, …, βk может принимать всего значений. Поэтому количество всех делителей числа а равно (см. пример в табл. 15).
Отметим, что каноническое разложение чисел на простые множители может использоваться для нахождения НОД и НОК двух натуральных чисел.

Покажем это на примере нахождения НОД и НОК чисел 280 и 300.
1) Запишем канонические разложения данных чисел на простые множители:

2) Запишем получившиеся разложения так, чтобы формально у них были одинаковые простые множители (если в разложении первого числа нет множителя 3, то допишем его формально в виде множителя , а в разложении второго числа запишем множитель ). Получаем:

3) Теперь НОД и НОК данных чисел можно записать как произведение степеней полученных простых чисел (2; 3; 5 и 7), причем при записи НОД каждый множитель берется с наименьшим показателем, а при записи НОК — с наибольшим. Получаем:

Заметим, что если найти произведение НОД и НОК заданных чисел, то в полученном произведении будут использованы все множители, входящие в разложение первого числа, и все множители, входящие в разложение второго числа, в результате получим произведение заданных чисел:

В общем случае

2. Деление целых чисел с остатком. Разделить с остатком целое число а на отличное от нуля целое число b — это значит найти два таких целых числа q и r, что

При этом число q называют неполным частным, число r — остатком. Подчеркнем, что в этом определении r — число неотрицательное.
Если r = 0, то говорят, что число а делится на b нацело, и тогда q называют полным частным (или просто «частным»), а число b — делителем числа а.
Для любой пары целых чисел a и b (где b ≠ 0) неполное частное q и остаток r находятся однозначно (обоснуйте это самостоятельно). Например, при делении 42 на 5 — неполное частное q = 8 и остаток r = 2, так как
42 = 5*8 + 2; а при делении (–42) на 5 — неполное частное q = –9 и остаток r = 3, так как –42 = 5*(–9) + 3 (еще раз напомним, что остаток не бывает отрицательным).
При делении целого числа а на натуральное число т может получиться только т остатков: 0, 1, 2, 3, ..., m – 1. Поэтому множество Z всех целых чисел можно разбить на т непересекающихся класcов Kr, где в класс Kr входят те и только те целые числа, которые при делении на т дают остаток r (r = 0, 1, 2, ..., m – 1).
Такое разбиение обычно называют разбиением целых чисел на классы по модулю m.

Заметим, что если к обеим частям равенства прибавить т (или из обеих частей вычесть т), то получим . Это равенство показывает, что
если к заданному числу а прибавить (или из него вычесть) модуль т (или число, кратное т), то остаток при делении на т не изменится. При разбиении целых чисел на классы по модулю т в один класс будут попадать только числа, отличающиеся друг от друга на число, кратное модулю m (обоснуйте это самостоятельно).
Например, если m = 3, то при делении на 3 получаем только остатки 0; 1; 2, и поэтому все целые числа можно разбить на следующие 3 класса по модулю 3:

Рассматривая несколько последовательных целых чисел, замечаем, что при увеличении числа из некоторого класса на единицу мы всегда получаем число, которое находится в следующем классе (для класса будем считать следующим классом класс).
Разбиение целых чисел на классы по модулю т часто применяют при решении задач.
Например, чтобы доказать, что из т последовательных целых чисел одно обязательно делится на m, достаточно разбить все целые числа на m классов по модулю m. Поскольку разность любых двух заданных чисел меньше m, то числа попадают в разные классы, а так как число классов m и количество чисел тоже m, следовательно, в каждом классе будет по одному числу. Но тогда одно из заданных чисел попадает в класс и будет давать остаток 0 при делении на m, то есть будет делиться на m.
3. Сравнения по модулю m. Указанный выше прием разбиения множества целых чисел на классы может быть описан с помощью специального понятия: сравнения по модулю m.
Пусть m — данное натуральное число (). Целые числа а и b называют сравнимыми по модулю т, если они дают одинаковые остатки при делении на m.
Таким образом, целые числа а и b сравнимы по модулю т, если a =
, то есть каждое из чисел а и b при делении на т дает один и тот же остаток r. Отсюда получаем, что целые числа

а и b сравнимы по модулю т тогда и только тогда, когда разность а – b при делении на т дает остаток 0 (делится на m).
Учитывая, что если а – b делится на m, то существует такое целое число t, что а – b = mt и тогда а = b + mt. Следовательно, целые числа а и b сравнимы по модулю т тогда и только тогда, когда выполняется равенство а = b + mt.
Для обозначения того, что целые числа а и b сравнимы по модулю m, используют запись: а ≡ b (mоd m), что читают так: «а сравнимо с b по модулю m». Знак ≡ называют знаком сравнения.
Например, 27 ≡ 12 (mоd 5), так как числа 27 и 12 дают одинаковые остатки (2) при делении на 5;
10 ≡ –1 (mоd 11), так как разность 10 – (–1) = 11 делится на 11.
Основные свойства сравнений похожи на свойства равенств. Сформулируем некоторые из них.

Свойство 4 можно обобщить: если заданное числовое выражение содержит только суммы, произведения и степени целых чисел и вместо соответствующих слагаемых, множителей и оснований степеней подставить числа, сравнимые с заданными по модулю т, то получим число, сравнимое по модулю т с заданным выражением.
Докажем, например, что сравнения по одному модулю можно почленно складывать. Складывая почленно последние равенства, получаем: . Но последнее равенство и означает, что а + c ≡ b + d (mоd m).
Укажем несколько следствий из приведенных свойств.
Например, если задано сравнение а + c ≡ b (mоd m), то складывая почленно это сравнение с верным сравнением –c ≡ –с (mоd m), получаем:
а ≡ b – c (mоd m). Следовательно, члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
Если сравнение а ≡ b (mоd m) почленно сложить с верным сравнением mk ≡ 0 (mоd т), получаем а + mk ≡ b (mоd m). Следовательно, к любой части сравнения можно прибавить (или из нее вычесть) любое число, кратное модулю.
Если сравнение а ≡ b (mоd m) почленно умножить на верное сравнение
с ≡ с (mоd т), получаем ас ≡ bс (mоd m). Следовательно, обе части сравнения можно умножать на любое целое число.
Заметим, что для получения правильного сравнения по данному модулю т делить обе части сравнения можно только на число, взаимно простое с модулем т, то есть имеет место свойство:

5. Если аk ≡ bk (mоd m) и числа k и т взаимно простые, то а ≡ b (mоd m). Если аk ≡ bk (mоd m), то аk – bk = k (а – b) делится на m. Но k и m — взаимно простые числа (и m ≠ 1), следовательно, а – b делится на m. А это и означает, что а ≡ b (mоd m).
Рассмотрим применение свойств сравнений к доказательству признаков делимости, приведенных в таблице 15.
Пусть задано натуральное число N, записанное в десятичной системе счисления так:
цифр числа N, то получаем, что число N и сумма его цифр дают одинаковые остатки при делении на 3 (или на 9). В частности, если сумма цифр делится на 3 (или на 9), то и само число N делится на 3 (или на 9), то есть признаки делимости на 3 и на 9 доказаны.
Так как 10 ≡ 0 (mоd 2 или 5), то по обобщенному свойству 4: (mоd 2 или 5), то есть число N и его последняя цифра а0 дают одинаковые остатки при делении на 2 (или на 5). В частности, если последняя цифра а0 — четная (делится на 2), то и само число N делится на 2. А если последняя цифра а0 равна 0 или 5 (делится на 5), то и само число N делится на 5, то есть признаки делимости на 2 и на 5 доказаны.
если разность между суммой цифр, стоящих на нечетных местах (считая справа налево), и суммой цифр, стоящих на четных местах, делится на 11, то и само число делится на 11 (и полученное число дает тот же остаток при делении на 11, что и число N).

Приведенные свойства сравнений и признаки делимости можно использовать при нахождении остатков при делении заданных чисел.
Например, найдем остаток при делении на 3.
Учитывая признак делимости на 3, получаем 2012 ≡ 2 + 0 + 1 + 2 ≡
≡ 5 ≡ 2 (mоd 3). Вычитая из правой части последнего сравнения модуль 3, имеем 2012 ≡ –1 (mоd 3). . Поскольку остаток при делении на 3 не бывает отрицательным, то прибавляем к правой части последнего сравнения модуль 3 и получаем, что ≡ 2 (mоd 3). Следовательно, остаток от деления на 3 равен 2.
4. Решение уравнений в целых числах. Выясним, можно ли, используя только монеты по 2 р. и по 5 р., заплатить за покупку точно 21 р.
Если обозначить через х число монет по 2 р., через у — число монет по 5 р., которые надо уплатить за покупку, то по условию задачи получаем равенство
2х + 5у = 21 (1)
и задача сводится к нахождению целых решений уравнения (1).
Уравнение (1) имеет бесконечно много решений в целых числах:
I) х = –2, у = 5; 2) х = 3, у = 3; 3) х = 8, у = 1; 4) х = 13, у = –1; ... .
Заметим, что условие задачи можно понимать по-разному: 1) можно считать, что монеты по 2 р. и по 5 р. имеются только у покупателя, и он этими монетами должен набрать ровно 21 р. (тогда условию задачи удовлетворяют только неотрицательные целые решения уравнения (1), например х = 3, у = 3; или х = 8, у = 1); 2) можно также считать, что у продавца тоже есть такие монеты и он может ими давать сдачу покупателю (тогда условию задачи удовлетворяют любые целые решения уравнения (1), причем отрицательное значение х (или у) означает, что покупатель получил сдачу в | х | мо-
нет по 2 р. (или в | у | монет по 5 р.)).
Уравнение (1) является примером диофантова уравнения — уравнения с несколькими переменными, решения которого ищут в целых числах. Подобные уравнения возникают в некоторых задачах математики, физики, экономики и т. д. Название «диофантовы» дано таким уравнениям по имени древнегреческого математика Диофанта (III в.).
Отметим, что нет общих методов решения диофантовых уравнений, однако можно выделить некоторые частные приемы, связанные с использованием свойств делимости, которые позволяют решать некоторые из таких уравнений. Рассмотрим применение этих приемов на конкретных примерах.
1. Пробуем представить заданное уравнение в виде u ⋅ v = a и рассматриваем все возможные варианты разложения целого числа а на целые множители.
Пример Решить в целых числах уравнение
ху + х + у = 2. (2)
 Решение. Преобразуем данное уравнение так, чтобы выражение в левой части можно было разложить на множители: х (у + 1) + у + 1 = 2 + 1.

Тогда (у + 1)(х + 1) = 3. Так как по условию х и у - целые числа, то
х + 1 и у + 1 - тоже целые числа. Но целое число 3 можно представить в виде произведения двух целых чисел лишь одним из четырех способов: 3 = 3*1 = 1*3 = (– 3)*(– 1) = (– 1)*(– 3). Получаем четыре системы:

Решая эти системы, находим все решения заданного уравнения в целых числах:

Ответ: (0; 2), (2; 0), (–2; –4), (–4; –2). 
2. Пробуем выполнить равносильные преобразования заданного уравнения так, чтобы записать его в виде равенства с дробным выражением и, если возможно, выделить целую часть в полученной дроби.
Решим этим способом в целых числах уравнение (2): ху + х + у = 2. Для этого выразим из заданного уравнения переменную х через переменную у.
 Решение. х (у + 1) = 2 – у. При у + 1 = 0 (то есть у = –1) решений нет
(0 ≠ 3). При у + 1 ≠ 0 (то есть у ≠ –1) получаем . Тогда: , . По условию х — целое число, тогда левая часть последнего уравнения тоже целое число, следовательно, и число  - целое. Но это возможно только в случае, когда у + 1 - делитель числа 3. Но у числа 3 только 4 целых делителя: ±1; ±3. Следовательно, у + 1 = 1, или у + 1 = –1, или у + 1 = 3, или у + 1 = –3. Определяя из этих равенств значение у, а затем соответствующее значение х из равенства xyy=−+21, получаем:
3. Использование свойств сравнений
Решим этим способом в целых числах уравнение (1): 2х + 5у = 21.
 Решение. Из данного уравнения получаем: 2х = 21 – 5у. Это равенство означает, что 2х ≡ 21 (mod 5). Последнее сравнение останется правильным, если коэффициент 2 (или число 21) заменить сравнимым по модулю 5 числом (так, чтобы левая и правая части нового сравнения имели общий множитель). Поскольку 2 ≡ 7 (mod 5), то правильным будет также сравнение 7х ≡ 21 (mod 5). Учитывая, что числа 7 и 5 взаимно простые, обе части последнего сравнения можно разделить на 7 и получить верное сравнение х ≡ 3 (mod 5). Тогда x = 3 + 5t (где t  целое число). Подставляя в уравнение (1), получаем: 2æ(3 + 5t) + 5у = 21. Отсюда у = 3 – 2t.

Следовательно, все целые решения уравнения (1) задаются формулами: x = 3 + 5t, у = 3 – 2t, где t - любое целое число. 
Замечание. Если по условию задачи требуется найти решение уравнения (1) в натуральных числах, то из полученных формул видно, что натуральные решения мы получим только при t = 0 и t = 1. Следовательно, уравнение (1) имеет только два решения в натуральных числах: х = 3, у = 3 и х = 8, у = 1.
Заметим, что, используя свойства делимости, можно исследовать существование и общий вид решения диофантова уравнения первой степени
ax + by = c, (3)
где a, b, c - целые числа.
В частности, можно показать, что если a и b - взаимно простые числа (то есть НОД (a; b) = 1), то уравнение (3) всегда имеет решение. Причем, если (х0; у0) - одно из решений уравнения (3), то все его решения задаются формулами
(где t - любое целое число). (4)
Покажем, что если (х0; у0)  одно из решений уравнения (3), то все его решения действительно задаются формулами (4). Пусть уравнение (3) имеет решения . Тогда справедливы равенства
, откуда получаем, что , и поэтому
. (5)
Левая часть равенства (5) делится на b, следовательно, и правая его часть делится на b. Но поскольку НОД делится на b, то есть существует такое целое число t, что, а значит,
. Но тогда из равенства (5) следует, что . Следовательно, все решения уравнения (3) задаются формулами (4).
Если целые числа a и b имеют наибольший общий делитель d ≠ 1, то число ax + by делится на d. Но тогда равенство (3) может выполняться только в том случае, когда c = ax + by делится на d. Если же с не делится на d, то уравнение (3) не имеет решений. Например, уравнение 6x + 15y = 32 не имеет решений, так как НОД (6, 15) = 3, а 32 не делится на 3.
Если же целые числа a и b имеют наибольший общий делитель d ≠ 1 и с делится на d, то обе части уравнения (3) можно разделить на d и получить равносильное уравнение, в котором
НОД (a1; b1) = 1 и которое всегда имеет решения.

Задача 2 Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 натуральных делителя (включая единицу и само число).
Комментарий
Для решения достаточно вспомнить определение делимости натуральных чисел (если , то п = 42*m) и формулу для числа делителей натурального числа, для которого мы знаем его каноническое разложение на простые множители. Поскольку 42 = 2*3*7 и п = 42*m, то п = 2*3*7*т. Следовательно, в разложении числа п на простые множители обязательно будут присутствовать простые числа. Поэтому общий вид канонического разложения числа п на простые множители запишется так: , а число делителей: . (1)
Дальнейшие рассуждения связаны с тем, что количество натуральных делителей искомого числа тоже равно 42 = 2*3*7, и поэтому в записи (1) может быть только три множителя (поскольку при натуральных значениях тоже натуральные и не меньше 2).
Решение
 Если искомое число п делится на 42 = 2*3*7, то его каноническое разложение на простые множители будет иметь вид: , где натуральные числа, а число делителей:
(1)
(причем ).
Учитывая, что по условию число делителей числа п равно 42 = 2*3*7, получаем, что в формуле (1) (а значит, и в каноническом разложении числа п) может быть только три множителя. Следовательно, , где (и каждый из множителей в последнем равенстве не меньше 2). Получаем всего шесть возможных случаев:

Решая эти системы и подставляя результат в формулу, получаем, что условию задачи удовлетворяют только шесть натуральных чисел со следующими каноническими разложениями:

Вопросы для контроля
1. Дайте определение делимости целых чисел. Сформулируйте свойства делимости. Приведите пример их доказательства.
2. Дайте определение делимости целых чисел с остатком. Объясните на примере разбиение целых чисел на классы по модулю т.
3. Дайте определение сравнения целых чисел по модулю т. Сформулируйте свойства сравнений. Приведите пример их доказательства.
4. Сформулируйте и докажите признаки делимости на 2; 5; 3; 9; 11; 4; 8.
Упражнения
1. Докажите, что приведенные пары чисел являются взаимно простыми.
1) 2009 и 2003; 2) 1354 и 1357; 3) 2006 и 2011.
2. Докажите, что произведение:
1) двух последовательных целых чисел делится на 2;
2) трех последовательных целых чисел делится на 6;
3) четырех последовательных натуральных чисел делится на 24.
3. Докажите, что сумма кубов трех последовательных натуральных чисел делится на 9.
4. При делении натурального числа N на 3 и на 37 получаются соответственно остатки 1 и 33. Найдите остаток от деления N на 111.

5. Не выполняя деления, определите остаток от деления числа
100 320 052 006 200 720 087
1) на 3; 2) на 4; 3) на 5; 4) на 8; 5) на 9; 6) на 11.
6. Найдите остаток от деления числа на: 1) 10; 2) 11; 3) 13.
7. Определите последнюю цифру числа:
8. Докажите, что квадрат любого натурального числа при делении на 4 не может давать остатки, равные 2 и 3.
9. Докажите, что квадрат любого натурального числа либо делится на 9, либо при делении на 3 дает остаток 1.
10. Найдите все пары натуральных чисел, наименьшее общее кратное которых равно 78, а наибольший общий делитель равен 13.
11. Найдите все пары натуральных чисел, разность которых 66, а их наименьшее общее кратное равно 360.
12. Найдите все пары натуральных чисел, разность квадратов которых равна 55.
13. Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей (включая единицу и само число).
14. Найдите двузначное число, которое на 19 больше суммы квадратов его десятичных цифр и на 44 больше удвоенного произведения его цифр.
15. Натуральные числа а, b и с таковы, что НОК (a, b) = 60, НОК (a, с) =
= 270. Найдите НОК (b, с).
16. Каким может быть наибольший общий делитель натуральных чисел a и b, если при увеличении числа a на 6 он увеличивается в четыре раза?
17. Доказать, что при любом натуральном n число делится на 7.
18. Произведение натурального числа и числа, записанного теми же цифрами в обратном порядке, равно 2430. Найдите все такие числа.
19. Решите в целых числах уравнение: 1)
20. Решите в натуральных числах уравнение:
1) 19x + 99y = 2002; 2) xy – 3x + 5y = 25; 3)
21 (МГУ, хим. ф-т). Найдите все пары целых чисел (x; y), удовлетворяющих уравнению.