Татьяна Мельничук | Делимость чисел

Делимость чисел

Одним из основных понятий в математике является делимость целых чисел.

Если для некоторого целого числа $a$ и целого числа $b$ cуществует такое целое число $c$ , что $b\cdot c=a$ , то говорят, что число $a$ делится на $b$ или что $b$ делит $a$ . При этом используют следующую терминологию:

число $b$ является делителем числа $a$ ;
делимое $a$ кратно числу $b$ .

Для обозначения делимости используют специальный символ — три вертикальные точки $(\vdots)$ . Запись $a\vdots b$ означает, что $a$ делится на $b,$ или что число $a$ кратно $b$ .

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

Свойства делимости и связанные определения

Ноль делится на любое натуральное число.
Любое число делится на единицу.
Любое число делится само на себя.
Натуральные числа, имеющие ровно два делителя, называют простыми, а имеющие более двух делителей — составными. Подробнее о простых числах читайте в статье «Простые числа».
Единица имеет ровно один делитель и не является ни простым, ни составным.
Каждое натуральное числа, большее $1$ , имеет хотя бы один простой делитель.
Собственным делителем числа называется всякий его делитель, отличный от самого числа. Каждое простое число имеет ровно один собственный делитель — единицу.
Если $a>0$ и $a \vdots b$ , то $a \ge b$ .
Если $a\vdots b$ и $b \vdots c$ , то $a\vdots c$ .
Если $a\vdots c$ и $b \vdots c$ , то $(a+b)\vdots c$ .
Если $a\vdots (bc)$ , то $a\vdots b$ , $a\vdots c$ и $(a:b)\vdots c$ .
Если $a\vdots b$ и $b\vdots a$ , то $a=b$ .
Если $a\vdots b$ , $k\in\mathbb{N}$ , то $ak \vdots bk$ .
Если $a\vdots c$ и $b \vdots c$ , $m\in\mathbb{N}$ , $n\in\mathbb{N}$ , то $(am+bn)\vdots c$ .
Если $a\vdots c$ и $(a+b)\vdots c$ , то $b\vdots c$ .

Деление с остатком

Для двух любых натуральных чисел $a$ и $b$ найдутся такие целые неотрицательные числа $q$ и $r$ , что $a=b\cdot q+r,$ $0\le r<b$ .

Число $r$ называют остатком от деления $a$ на $b$ . Если $r=0$ , то $a\vdots b$ .

Наибольший общий делитель

Наибольший общий делитель двух чисел $a$ и $b$ — это наибольшее число, на которое оба числа $a$ и $b$ делятся без остатка. Для оозначения наибольшего общего делителя принято использовать обозначение НОД $(a;b)$ . В англоязычной литературе принято также использовать обозначение $\gcd(m;n)$ .

Наибольший общий делитель НОД $(a;b)$ существует и однозначно определён, если хотя бы одно из чисел $a$ и $b$ не равно нулю.

Пример: НОД $(15;10)=5$ .

Для вычисления НОД можно использовать алгоритм Евклида.

Наименьшее общее кратное

Наименьшее общее кратное двух чисел $a$ и $b$ — это такое наименьшее натуральное число, которое делится на $a$ и $b$ без остатка. Для обозначения наименьшего общего кратного используют обозначение НОК $(a;b)$ или, как это принято в англоязычной литературе, $\text{lcm}(a;b)$ .

Пример: НОК $(15;10)=30$ .

Если известен НОД $(a;b)$ , который можно определить, используя алгоритм Евклида, то найти НОК $(a;b)$ особенного труда не составит, поскольку обе эти величины связаны соотношением:

НОК $(a;b)$ $\cdot$ НОД $(a;b)$ = $a\cdot b$ .

Признаки делимости

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

Представим известные признаки делимости в виде таблицы:

Признак делимости на 2	Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной.
Признак делимости на 3	Число делится на 3 тогда и только тогда, когда сумма его всех цифр делится на 3.
Признак делимости на 4	Число делится на 4 только тогда, когда две его последние цифры – нули или составляют число, которое делится на 4.
Признак делимости на 5	Число делится на 5 тогда и только тогда, когда последняя цифра делится на 5, т. е. если она 0 или 5.
Признак делимости на 6	Число делится на 6 тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3). Другой признак делимости: число делится на 6 тогда и только тогда, когда учетверённое число десятков, сложенное с числом единиц делится на 6.
Признак делимости на 7	Признак 1. число делится на 7 тогда и только тогда, когда утроенное число десятков, сложенное с числом единиц, делится на 7. Признак 2. число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 7.
Признак делимости на 8	Число делится на 8 тогда и только тогда, когда число, образованное тремя его последними цифрами, делится на 8. Трёхзначное число делится на 8 тогда и только тогда, когда число единиц, сложенное с удвоенным числом десятков и учетверённым числом сотен, делится на 8.
Признак делимости на 9	Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
Признак делимости на 10	Число делится на 10 тогда и только тогда, когда оно оканчивается на нуль.
Признаки делимости на 11	Признак 1: число делится на 11 тогда и только тогда, когда модуль разности между суммой цифр, занимающих нечётные позиции, и суммой цифр, занимающих чётные места делится на 11. Признак 2: число делится на 11 тогда и только тогда, когда на 11 делится сумма чисел, образующих группы по две цифры (начиная с единиц).
Признак делимости на 13	Число делится на 13 если сумма числа десятков с учетверенным числом единиц делится на 13.
Признак делимости на 17	Число делится на 17 если модуль разности числа десятков и пятикратного числа единиц делится на 17.
Признак делимости на 19	Число делится на 19 тогда и только тогда, когда число десятков, сложенное с удвоенным числом единиц, делится на 19.
Признак делимости на 20	Число делится на 20 тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 20.
Признаки делимости на 23	Признак 1: число делится на 23 тогда и только тогда, когда число сотен, сложенное с утроенным числом, образованным двумя последними цифрами, делится на 23. Признак 2: число делится на 23 тогда и только тогда, когда число десятков, сложенное с семикратным числом единиц, делится на 23. Признак 3: число делится на 23 тогда и только тогда, когда число сотен, сложенное с семикратным числом десятков и утроенным числом единиц, делится на 23.
Признак делимости на 25	Число делится на 25 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 25.
Признак делимости на 27	Число делится на 27 тогда и только тогда, когда на 27 делится сумма чисел, образующих группы по три цифры (начиная с единиц).
Признак делимости на 29	Число делится на 29 тогда и только тогда, когда число десятков, сложенное с утроенным числом единиц, делится на 29.
Признак делимости на 30	Число делится на 30 тогда и только тогда, когда оно заканчивается на 0 и сумма всех цифр делится на 3.
Признак делимости на 31	Число делится на 31 тогда и только тогда, когда модуль разности числа десятков и утроенного числа единиц делится на 31.
Признак делимости на 37	Признак 1: число делится на 37 тогда и только тогда, когда при разбивании числа на группы по три цифры (начиная с единиц) сумма этих групп кратна 37. Признак 2: число делится на 37 тогда и только тогда, когда на 37 делится модуль утроенного числа сотен, сложенного с учетверённым числом десятков, за вычетом числа единиц, умноженного на семь. Признак 3: число делится на 37 тогда и только тогда, когда на 37 делится модуль суммы числа сотен с числом единиц, умноженного на десять, за вычетом числа десятков, умноженного на 11.
Признак делимости на 41	Признак 1: число делится на 41 тогда и только тогда, когда модуль разности числа десятков и четырёхкратного числа единиц делится на 41. Признак 2: чтобы проверить, делится ли число на 41, его следует справа налево разбить на грани по 5 цифр в каждой. Затем в каждой грани первую справа цифру умножить на 1, вторую цифру умножить на 10, третью — на 18, четвёртую — на 16, пятую — на 37 и все полученные произведения сложить. Если результат будет делиться на 41, тогда и только тогда само число будет делиться на 41.
Признак делимости на 50	Число делится на 50 тогда и только тогда, когда число, образованное двумя его младшими десятичными цифрами, делится на 50.
Признак делимости на 59	Число делится на 59 тогда и только тогда, когда число десятков, сложенное с числом единиц, умноженное на 6, делится на 59.
Признак делимости на 79	Число делится на 79 тогда и только тогда, когда число десятков, сложенное с числом единиц, умноженное на 8, делится на 79.
Признак делимости на 99	Число делится на 99 тогда и только тогда, когда на 99 делится сумма чисел, образующих группы по две цифры (начиная с единиц).
Признак делимости на 101	Число делится на 101 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по две цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 101.