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

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

В школьном курсе рассматривались лишь простейшие из них: признаки делимости на 2, 3, 5, 9, 10. Другие признаки лежат за пределами школьного курса.

Рассмотрим признаки делимости целых чисел, записанных в десятичной системе счисления на 3, 9, 11.

Пусть а _k, a_k-1, …, а₁, а₀ – цифры десятичной записи натурального числа n = ).

Теорема 10.5 (признаки делимости на 3 и 9). Натуральное число n, записанное в десятичной системе счисления, делится на d такое, что d {3, 9} тогда и только тогда, когда сумма цифр числа n делится на d.

Доказательство. Заметим, что 10¹ º 1 (mod d), 10² º 1 (mod d), …,

10^k º 1 (mod d). Тогда, используя свойства сравнений, получим:

n = a_k · 10^k + a_k-1 · 10^k-1 + … + а₁ · 10 + а₀ º a_k + a_k-1 + … + а₁ + а₀ (mod d)

Теорема 10.6 (признак делимости на 11). Натуральное число n, записанное в десятичной системе счисления, делится на 11 тогда и только тогда, когда знакочередующаяся сумма цифр числа n делится на 11 т.е.

n = (a_k · 10^k + a_k-1 · 10^k-1 +…+ а₁ · 10 + а₀) 11 (а₀ – а₁ + а₂ – …+ (–1)^k · a_k) 11

Доказательство. Заметим, что 10¹ º -1 (mod 11), 10² º 1 (mod 11), …,

10^k º (-1)^k (mod 11). Тогда, используя свойства сравнений, получим:

n = a_k · (-1)^k + a_k-1 · (-1)^k-1 + … + а₁ · (-1) + а₀ º a₀ – a₁ + …+ (–1)^k · a_k (mod 11)

Примеры: 1)2457 делится на 3 и на 9,т.к. 2 + 4 + 5 + 7=18 делится и на 3 и на 9.

2) 234712 не делится на 11, т.к. 2 – 1 + 7 – 4 + 3 – 2 = 5, а 5 не делится на 11.

3) 2132438 делится на 11, т.к. 8 – 3 + 4 – 2 + 3 – 1 + 2 = 11 делится на 11.