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

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

Если для некоторого целого числа 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.

Вернуться назад...

МЕТКИ >, ,