

Делимость чисел
Одним из основных понятий в математике является делимость целых чисел.
Если для некоторого целого числа и целого числа
cуществует такое целое число
, что
, то говорят, что число
делится на
или что
делит
. При этом используют следующую терминологию:
- число
является делителем числа
;
- делимое
кратно числу
.
Для обозначения делимости используют специальный символ — три вертикальные точки . Запись
означает, что
делится на
или что число
кратно
.
Хотя свойство делимости является определённым на всём множестве целых чисел, обычно рассматривается лишь делимость целых неотрицательных чисел. В дальнейшем мы также будем рассматривать делимость лишь для целых неотрицательных чисел.
Свойства делимости и связанные определения
- Ноль делится на любое натуральное число.
- Любое число делится на единицу.
- Любое число делится само на себя.
- Натуральные числа, имеющие ровно два делителя, называют простыми, а имеющие более двух делителей — составными. Подробнее о простых числах читайте в статье «Простые числа».
- Единица имеет ровно один делитель и не является ни простым, ни составным.
- Каждое натуральное числа, большее
, имеет хотя бы один простой делитель.
- Собственным делителем числа называется всякий его делитель, отличный от самого числа. Каждое простое число имеет ровно один собственный делитель — единицу.
- Если
и
, то
.
- Если
и
, то
.
- Если
и
, то
.
- Если
, то
,
и
.
- Если
и
, то
.
- Если
,
, то
.
- Если
и
,
,
, то
.
- Если
и
, то
.
Деление с остатком
Для двух любых натуральных чисел и
найдутся такие целые неотрицательные числа
и
, что
.
Число называют остатком от деления
на
. Если
, то
.
Наибольший общий делитель
Наибольший общий делитель двух чисел и
— это наибольшее число, на которое оба числа
и
делятся без остатка. Для оозначения наибольшего общего делителя принято использовать обозначение НОД
. В англоязычной литературе принято также использовать обозначение
.
Наибольший общий делитель НОД существует и однозначно определён, если хотя бы одно из чисел
и
не равно нулю.
Пример: НОД.
Для вычисления НОД можно использовать алгоритм Евклида.
Наименьшее общее кратное
Наименьшее общее кратное двух чисел и
— это такое наименьшее натуральное число, которое делится на
и
без остатка. Для обозначения наименьшего общего кратного используют обозначение НОК
или, как это принято в англоязычной литературе,
.
Пример: НОК.
Если известен НОД, который можно определить, используя алгоритм Евклида, то найти НОК
особенного труда не составит, поскольку обе эти величины связаны соотношением:
НОК
НОД
=
.
Признаки делимости
Признаками делимости называют алгоритмы, позволяющие определить, является ли данное число кратным другому числу.
Представим известные признаки делимости в виде таблицы:
Признак делимости на 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. |