Делимость

Пусть ${\displaystyle a}$ и ${\displaystyle b}$ — целые числа, причём ${\displaystyle b\neq 0}$. Говорят, что ${\displaystyle a}$ делится нацело на ${\displaystyle b}$ (или что ${\displaystyle b}$ делит ${\displaystyle a}$), если существует такое целое число ${\displaystyle q}$, что

${\displaystyle a=bq.}$

Число ${\displaystyle b}$ называется делителем числа ${\displaystyle a}$, число ${\displaystyle a}$ — кратным числа ${\displaystyle b}$, а число ${\displaystyle q}$ — частным от деления ${\displaystyle a}$ на ${\displaystyle b}$^[2]. Условие ${\displaystyle b\neq 0}$ входит в определение в стандартных руководствах. Оно обеспечивает единственность частного: если ${\displaystyle b\neq 0}$ и ${\displaystyle a=bq_{1}=bq_{2}}$, то ${\displaystyle b(q_{1}-q_{2})=0}$, а поскольку кольцо целых чисел не имеет делителей нуля, отсюда ${\displaystyle q_{1}=q_{2}}$. Употребительны две записи: ${\displaystyle b\mid a}$ — «${\displaystyle b}$ делит ${\displaystyle a}$» (международное обозначение); ${\displaystyle a\vdots b}$ — «${\displaystyle a}$ делится на ${\displaystyle b}$» (распространено в русскоязычной школьной литературе)^[3]. Отрицание обозначается перечёркнутым символом: ${\displaystyle b\nmid a}$. Например, ${\displaystyle 3\mid 12}$, но ${\displaystyle 5\nmid 12}$.

Вне зависимости от того, делится ли ${\displaystyle a}$ на ${\displaystyle b\neq 0}$ нацело, всегда возможно деление с остатком: для любых целых ${\displaystyle a}$ и ${\displaystyle b\neq 0}$ существуют единственные целые числа ${\displaystyle q}$ (неполное частное) и ${\displaystyle r}$ (остаток) такие, что

${\displaystyle a=bq+r,\qquad 0\leqslant r<|b|.}$

Делимость нацело равносильна случаю, когда остаток ${\displaystyle r=0}$. Например, при делении ${\displaystyle 17}$ на ${\displaystyle 5}$ получаем ${\displaystyle 17=5\cdot 3+2}$, где частное ${\displaystyle q=3}$, а остаток ${\displaystyle r=2}$.

Всюду в этом разделе ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$, ${\displaystyle d}$ — целые числа; там, где число выступает делителем, оно предполагается отличным от нуля^[4]. Нуль делится на любое ненулевое число: ${\displaystyle 0=a\cdot 0}$. Любое целое число делится на ${\displaystyle 1}$ и на ${\displaystyle -1}$. Если ${\displaystyle b\mid a}$ и ${\displaystyle a\neq 0}$, то ${\displaystyle |a|\geqslant |b|}$. Отсюда следует, что у любого ненулевого числа лишь конечное число делителей.

Транзитивность: если ${\displaystyle b\mid a}$ и ${\displaystyle c\mid b}$, то ${\displaystyle c\mid a}$.

Линейность (свойство линейной комбинации): если ${\displaystyle d\mid a}$ и ${\displaystyle d\mid b}$, то ${\displaystyle d}$ делит любую целочисленную линейную комбинацию: ${\displaystyle d\mid (xa+yb)}$ для любых целых ${\displaystyle x,y}$. В частности, ${\displaystyle d}$ делит сумму ${\displaystyle a+b}$ и разность ${\displaystyle a-b}$. Если ${\displaystyle b\mid a}$, то ${\displaystyle bc\mid ac}$ для любого ${\displaystyle c}$. Обратно, если ${\displaystyle bc\mid ac}$ и ${\displaystyle c\neq 0}$, то ${\displaystyle b\mid a}$ (правило сокращения делителей). Если ${\displaystyle a\mid c}$, ${\displaystyle b\mid c}$ и числа ${\displaystyle a}$ и ${\displaystyle b}$ взаимно просты (то есть ${\displaystyle \gcd(a,b)=1}$), то ${\displaystyle ab\mid c}$.

Лемма Евклида. Если простое число ${\displaystyle p}$ делит произведение ${\displaystyle ab}$, то оно делит хотя бы один из сомножителей (${\displaystyle p\mid a}$ или ${\displaystyle p\mid b}$). Это ключевое утверждение для доказательства единственности разложения на простые множители^[5].

Простое число — натуральное число, большее 1, имеющее ровно два натуральных делителя: 1 и само себя.

Составное число — натуральное число, большее 1, имеющее более двух натуральных делителей.

Тривиальные делители числа ${\displaystyle a}$ — это ${\displaystyle 1}$ и ${\displaystyle a}$ (а также ${\displaystyle -1}$ и ${\displaystyle -a}$ в целых числах). Все остальные делители называются собственными.

Наибольший общий делитель (${\displaystyle \gcd(a,b)}$ или ${\displaystyle {\text{НОД}}(a,b)}$) — наибольшее натуральное число, делящее одновременно ${\displaystyle a}$ и ${\displaystyle b}$. Если ${\displaystyle \gcd(a,b)=1}$, числа называются взаимно простыми.

Наименьшее общее кратное (${\displaystyle \operatorname {lcm} (a,b)}$ или ${\displaystyle {\text{НОК}}(a,b)}$) — наименьшее натуральное число, которое делится и на ${\displaystyle a}$, и на ${\displaystyle b}$. Для любых натуральных ${\displaystyle a,b}$ справедливо тождество: ${\displaystyle \gcd(a,b)\cdot \operatorname {lcm} (a,b)=a\cdot b}$.

Всякое натуральное число, большее единицы, представимо в виде произведения простых множителей, и такое представление единственно с точностью до порядка сомножителей:

${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}},\qquad p_{1}<p_{2}<\dots <p_{k}.}$

Из канонического разложения непосредственно получаются формулы для числа делителей ${\displaystyle \tau (n)}$ и суммы делителей ${\displaystyle \sigma (n)}$:

${\displaystyle \tau (n)=(\alpha _{1}+1)(\alpha _{2}+1)\cdots (\alpha _{k}+1),}$

${\displaystyle \sigma (n)={\frac {p_{1}^{\alpha _{1}+1}-1}{p_{1}-1}}\cdot {\frac {p_{2}^{\alpha _{2}+1}-1}{p_{2}-1}}\cdots {\frac {p_{k}^{\alpha _{k}+1}-1}{p_{k}-1}}.}$

Также через разложения выражаются НОД и НОК:

${\displaystyle \gcd(a,b)=\prod _{i}p_{i}^{\min(\alpha _{i},\beta _{i})},\qquad \operatorname {lcm} (a,b)=\prod _{i}p_{i}^{\max(\alpha _{i},\beta _{i})}.}$

Наибольший общий делитель можно найти без разложения на множители, с помощью последовательного деления с остатком:

${\displaystyle a=bq_{1}+r_{1},\quad b=r_{1}q_{2}+r_{2},\quad r_{1}=r_{2}q_{3}+r_{3},\ \ldots }$

Процесс конечен, так как остатки строго убывают. Последний ненулевой остаток и есть ${\displaystyle \gcd(a,b)}$. Расширенный алгоритм Евклида позволяет найти не только НОД, но и целые числа ${\displaystyle u,v}$, удовлетворяющие соотношению Безу:

${\displaystyle au+bv=\gcd(a,b).}$

В частности, ${\displaystyle a}$ и ${\displaystyle b}$ взаимно просты тогда и только тогда, когда существуют целые ${\displaystyle u,v}$, для которых ${\displaystyle au+bv=1}$.

Признаки делимости позволяют определить, делится ли число на заданный делитель, анализируя его запись в определённой системе счисления, без выполнения фактического деления. В десятичной системе наиболее употребительны следующие признаки:

На 2: последняя цифра числа чётная (0, 2, 4, 6, 8).

На 3: сумма цифр числа делится на 3.

На 4: число, образованное двумя последними цифрами, делится на 4 (или последние две цифры — нули).

На 5: последняя цифра числа 0 или 5.

На 6: число делится одновременно на 2 и на 3.

На 8: число, образованное тремя последними цифрами, делится на 8.

На 9: сумма цифр числа делится на 9.

На 10: последняя цифра числа равна 0.

На 11: знакопеременная сумма цифр числа (сумма цифр на нечётных местах минус сумма цифр на чётных местах) делится на 11.

На 25: число, образованное двумя последними цифрами, делится на 25 (00, 25, 50, 75). Обоснование этих признаков опирается на свойства сравнений по модулю. Например, поскольку ${\displaystyle 10\equiv 1{\pmod {3}}}$, то ${\displaystyle 10^{k}\equiv 1{\pmod {3}}}$ для любого ${\displaystyle k}$, откуда число сравнимо с суммой своих цифр по модулю 3.

Пример 1. Доказать, что для любого натурального ${\displaystyle n}$ число ${\displaystyle n^{3}-n}$ делится на 6. Решение: Разложим выражение на множители: ${\displaystyle n^{3}-n=n(n^{2}-1)=(n-1)n(n+1)}$. Это произведение трёх последовательных натуральных чисел. В любых трёх последовательных числах ровно одно делится на 3, и хотя бы одно делится на 2. Поскольку 2 и 3 взаимно просты, их произведение (6) делит всё произведение.

Пример 2. Найти все целые значения ${\displaystyle n}$, при которых дробь ${\displaystyle {\frac {n^{2}+3}{n+1}}}$ является целым числом. Решение: Выделим целую часть, разделив многочлен в числителе на знаменатель (или преобразовав выражение): ${\displaystyle {\frac {n^{2}+3}{n+1}}={\frac {n^{2}-1+4}{n+1}}={\frac {(n-1)(n+1)+4}{n+1}}=n-1+{\frac {4}{n+1}}.}$ Чтобы всё выражение было целым, дробь ${\displaystyle {\frac {4}{n+1}}}$ должна быть целой, то есть ${\displaystyle n+1}$ должно быть делителем числа 4. Делители числа 4: ${\displaystyle \pm 1,\pm 2,\pm 4}$. Приравнивая ${\displaystyle n+1}$ к этим значениям, получаем возможные ${\displaystyle n}$: ${\displaystyle 0,-2,1,-3,3,-5}$.

Пример 3. Делимость степеней (алгебраическое преобразование). Доказать, что для любого натурального ${\displaystyle n}$ число ${\displaystyle 2^{3n}-1}$ делится на 7. Решение: Преобразуем выражение, используя свойства степеней: ${\displaystyle 2^{3n}-1=(2^{3})^{n}-1=8^{n}-1.}$ Воспользуемся формулой разности ${\displaystyle n}$-х степеней: ${\displaystyle x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\dots +x+1)}$. Подставив ${\displaystyle x=8}$, получаем: ${\displaystyle 8^{n}-1=(8-1)(8^{n-1}+8^{n-2}+\dots +8+1)=7\cdot (8^{n-1}+8^{n-2}+\dots +1).}$ Поскольку второй множитель является целым числом, исходное выражение кратно 7.

Пример 4. Метод перебора остатков. Доказать, что число ${\displaystyle n^{2}+1}$ не делится на 3 ни при каком целом ${\displaystyle n}$. Решение: При делении на 3 любое целое число ${\displaystyle n}$ может давать только три возможных остатка: 0, 1 или 2. Рассмотрим все три случая: Если ${\displaystyle n=3k}$ (остаток 0), то ${\displaystyle n^{2}+1=(3k)^{2}+1=9k^{2}+1=3(3k^{2})+1}$. Остаток от деления на 3 равен 1. Если ${\displaystyle n=3k+1}$ (остаток 1), то ${\displaystyle n^{2}+1=(3k+1)^{2}+1=9k^{2}+6k+1+1=3(3k^{2}+2k)+2}$. Остаток равен 2. Если ${\displaystyle n=3k+2}$ (остаток 2), то ${\displaystyle n^{2}+1=(3k+2)^{2}+1=9k^{2}+12k+4+1=9k^{2}+12k+3+2=3(3k^{2}+4k+1)+2}$. Остаток равен 2. Ни в одном случае остаток от деления ${\displaystyle n^{2}+1}$ на 3 не равен нулю, следовательно, число никогда не делится на 3.

Пример 5. Доказательство признака делимости. Доказать признак делимости на 9: число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Решение: Пусть натуральное число ${\displaystyle N}$ записывается в десятичной системе как ${\displaystyle {\overline {a_{k}a_{k-1}\dots a_{1}a_{0}}}}$. Его можно разложить по степеням десятки: ${\displaystyle N=a_{k}\cdot 10^{k}+a_{k-1}\cdot 10^{k-1}+\dots +a_{1}\cdot 10+a_{0}.}$ Заметим, что ${\displaystyle 10=9+1}$, ${\displaystyle 100=99+1}$ и так далее. В общем виде ${\displaystyle 10^{m}=\underbrace {99\dots 9} {m}+1}$, где число из девяток делится на 9. Перепишем ${\displaystyle N}$, выделив части, кратные 9: ${\displaystyle N=a_{k}(99\dots 9+1)+a{k-1}(99\dots 9+1)+\dots +a_{1}(9+1)+a_{0}=}$ ${\displaystyle =9\cdot (a_{k}\cdot 11\dots 1+\dots +a_{1}\cdot 1)+(a_{k}+a_{k-1}+\dots +a_{1}+a_{0}).}$ Первое слагаемое всегда делится на 9. Следовательно, всё число ${\displaystyle N}$ делится на 9 тогда и только тогда, когда на 9 делится второе слагаемое — сумма его цифр.

Пример 6. Практическая задача на НОК. Три автобуса отправляются от одной остановки с интервалами 12, 18 и 24 минуты. В 8:00 утра они отправились одновременно. Через какое наименьшее время они снова встретятся на этой остановке и во сколько это произойдет? Решение: Чтобы автобусы встретились, должно пройти время, которое кратно интервалам движения всех трех автобусов. Нам нужно найти наименьшее общее кратное (НОК) чисел 12, 18 и 24. Разложим числа на простые множители: ${\displaystyle 12=2^{2}\cdot 3}$ ${\displaystyle 18=2\cdot 3^{2}}$ ${\displaystyle 24=2^{3}\cdot 3}$ Чтобы найти НОК, нужно взять каждый простой множитель в наибольшей степени, в которой он встречается в разложениях: ${\displaystyle \operatorname {lcm} (12,18,24)=2^{3}\cdot 3^{2}=8\cdot 9=72{\text{ минуты}}.}$ 72 минуты = 1 час 12 минут. Следовательно, автобусы снова встретятся через 1 час 12 минут, то есть в 9:12 утра.

Внутри математики. Делимость — фундамент элементарной теории чисел. Критерий разрешимости линейного диофантова уравнения ${\displaystyle ax+by=c}$ в целых числах формулируется целиком в терминах делимости: оно разрешимо тогда и только тогда, когда ${\displaystyle \gcd(a,b)\mid c}$.

Криптография. Схема шифрования RSA использует делимость на этапе построения ключей: открытый и закрытый ключи связаны сравнением ${\displaystyle ed\equiv 1{\pmod {\varphi (n)}}}$, которое решается с помощью расширенного алгоритма Евклида.

Информатика и программирование. Хеш-таблицы используют остаток от деления (${\displaystyle {\text{key}}{\bmod {m}}}$) как индекс корзины. При выборе модуля ${\displaystyle m}$ часто берут простое число, чтобы минимизировать коллизии.

Контрольные цифры. Алгоритмы проверки номеров банковских карт (алгоритм Луна), паспортов и кодов ISBN основаны на проверке делимости взвешенной суммы цифр на заданный модуль (10 или 11).