Делимость целых чисел

Натуральное число $n$ делится (нацело) на натуральное $m$, если существует натуральное $q$ такое, что $n = mq$. Числа $m$ и $q$ — делители $n$. У каждого $n > 1$ есть делители $1$ и $n$.

Если других делителей нет, число простое; если есть делители, отличные от $1$ и $n$, — составное. Число $1$ ни простое, ни составное.

Основная теорема арифметики. Каждое натуральное число $n > 1$ можно представить единственным образом (с точностью до порядка множителей) в виде произведения простых чисел: $13 = 13$, $\ 21 = 3 \cdot 7$, $\ 36 = 2^2 \cdot 3^2$.

Если каждое из двух натуральных чисел $a$ и $b$ делится на натуральное число $c$, то их сумма и разность делятся на $c$.

Доказательство. $a = cq_1$, $b = cq_2$. Тогда $a \pm b = c(q_1 \pm q_2)$, и $q_1 \pm q_2$ — целое число.

Следствие. Если $a$ и $a + b$ делятся на $c$, то и $b = (a + b) - a$ делится на $c$. А если $a$ делится на $c$, а $b$ — нет, то $a + b$ на $c$ не делится.

Если наибольший общий делитель чисел $m$ и $n$ равен $d$, пишут $d = (m,\ n)$ или $\text{НОД}(m,\ n) = d$. Если $d = 1$, числа взаимно простые.

Пример. Числа $2005$ и $2011$ взаимно простые. Их общий делитель делит и разность $2011 - 2005 = 6$ (теорема 1), то есть общие делители — среди $1, 2, 3, 6$. Но $2005$ не делится ни на $2$, ни на $3$. Значит, $(2005,\ 2011) = 1$.

НОК и НОД. Если $a = d\,a_1$, $b = d\,b_1$, $d = (a,\ b)$, то $(a_1,\ b_1) = 1$ и $\text{НОК}(a,\ b) = d\,a_1 b_1$. Отсюда $\text{НОД}(a,\ b) \cdot \text{НОК}(a,\ b) = ab$.

Пусть натуральные числа $m$, $n$ и $q$ таковы, что $n = mq$ и $n$ имеет делитель $d$ такой, что $(m,\ d) = 1$. Тогда число $q$ делится на $d$.

Это следует из основной теоремы арифметики: все простые множители $d$ входят в разложение $n = mq$, а в разложение $m$ они не входят — значит, входят в разложение $q$.

Пример. $777$ делится на $7$, а $(7,\ 3) = 1$. Из $777 = 3 \cdot 259$ следует, что $259$ делится на $7$: $\ 259 = 7 \cdot 37$.

Разделить с остатком целое $a$ на целое $b \ne 0$ — найти целые $q$ (неполное частное) и $r$ (остаток), для которых выполнены оба условия. Остаток всегда неотрицателен.

$17 = 5 \cdot 3 + 2$ — остаток $2$. $\ -17 = 5 \cdot (-4) + 3$ — остаток $3$, а не $-2$: запись $-17 = 5 \cdot (-3) - 2$ не годится, потому что $-2 < 0$.

Если $r = 0$, говорят, что $a$ делится на $b$ нацело, $q$ — полное частное, $b$ — делитель $a$.

Для любой пары чисел $a \in \mathbb{Z}$ и $b \in \mathbb{N}$ существует и притом только одна пара целых чисел $q$ и $r$ таких, что $a = bq + r$ и $0 \le r < b$.

• $a \ge 0$. Среди чисел $b \cdot 0,\ b \cdot 1,\ b \cdot 2, \ldots$ (Архимедово свойство) найдётся целое $k \ge 0$ с $bk \le a < b(k + 1)$. Тогда $a = bk + r$, где $r = a - bk \ge 0$ и $r < b(k + 1) - bk = b$.
• $a < 0$. Для $|a|$ есть $|a| = bq_1 + r_1$, то есть $a = -bq_1 - r_1$. Если $r_1 = 0$, берём $q = -q_1$, $r = 0$; если $r_1 > 0$, берём $q = -(q_1 + 1)$, $r = b - r_1$, тогда $0 < r < b$.
• Единственность. Если $a = bq_1 + r_1 = bq_2 + r_2$, то $r_1 - r_2 = b(q_2 - q_1)$. При $q_2 > q_1$ получили бы $r_1 \ge b$ — противоречие; так же при $q_2 < q_1$. Значит, $q_1 = q_2$ и $r_1 = r_2$.

При делении на натуральное $m$ возможны только $m$ остатков: $0, 1, \ldots, m - 1$. Поэтому все целые числа разбиваются на $m$ непересекающихся классов: $mn,\ mn + 1,\ \ldots,\ mn + (m - 1)$, $n \in \mathbb{Z}$.

Это главный приём ЕГЭ №20: чтобы доказать свойство для всех целых чисел, достаточно проверить его для каждого класса остатков.

1. Разобьём целые числа на $6$ классов по остаткам от деления на $6$: $6n,\ 6n + 1,\ \ldots,\ 6n + 5$.
2. Остаток от деления на $2$ и на $3$ определяется классом: $6n + r$ даёт те же остатки, что $r$.
3. Из $r = 0, 1, \ldots, 5$ условиям подходит только $r = 5$: $5 = 3 \cdot 1 + 2 = 2 \cdot 2 + 1$.

1. а) Из двух последовательных чисел одно чётное: $n$ даёт остаток $0$ или $1$ при делении на $2$, и в последнем случае $n + 1$ чётно.
2. б) Среди $n,\ n + 1,\ n + 2$ есть чётное (пункт а) и есть кратное $3$: если $n = 3k + 1$, то $n + 2 = 3k + 3$; если $n = 3k + 2$, то $n + 1 = 3k + 3$.
3. Произведение делится на $2$ и на $3$, а $(2,\ 3) = 1$ — по лемме оно делится на $6$.

1. Пусть $d = \text{НОД}(x,\ y)$. Сумма $x + y = 17$ делится на $d$ (теорема 1), а $17$ — простое, значит, $d = 1$ (оба числа меньше $17$).
2. Для взаимно простых чисел $\text{НОК}(x,\ y) = xy$, поэтому $xy = 70$.
3. $x + y = 17$, $xy = 70$: по теореме Виета $x$ и $y$ — корни $t^2 - 17t + 70 = 0$, то есть $10$ и $7$.

1. а) Да: $N = 2015 \cdot 2016 - 1$. Действительно, $N = 2015 \cdot 2015 + 2014 = 2016 \cdot 2014 + 2015$.
2. б) Нет: остаток $6$ при делении на $10$ означает, что число оканчивается на $6$, тогда при делении на $5$ остаток $1$, а не $4$.
3. в) Остаток каждый раз на $1$ меньше делителя, значит, $N + 1$ делится на $2, 3, \ldots, 10$, то есть на их НОК $= 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$.
4. Наименьшее: $N + 1 = 2520$, $N = 2519$.

1. а) Да: простые $7, 11, 13, 17$ — любой НОД равен $1$, любая разность не меньше $2$.
2. б) Разобьём числа на пары $(1, 2), (3, 4), \ldots, (2023, 2024)$ и число $2025$. В паре $(a,\ a + 1)$ разность $1$ и НОД равен $1$: общий делитель делит разность $1$. Из каждой пары — не больше одного числа, всего не больше $1012 + 1 = 1013 < 1200$. Нет.
3. в) Возьмём все нечётные числа — их $1013$. НОД двух нечётных нечётен, а разность чётна, поэтому они не равны.
4. Оценка из пункта б) и пример дают ответ $1013$.

• Каждое $n > 1$ единственным образом раскладывается на простые множители.
• Общий делитель двух чисел делит их сумму и разность — главный инструмент для НОД.
• $\text{НОД} \cdot \text{НОК} = ab$; для взаимно простых $\text{НОК} = ab$.
• $a = bq + r$, $0 \le r < b$: пара $q,\ r$ существует и единственна; остаток неотрицателен.
• Целые числа делятся на $m$ классов остатков — свойство проверяют для каждого класса.