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

Очень часто возникает потребность, не производя самого деления, ответить на вопрос о делимости одного числа на другое. Критерий, устанавливающий необходимое и достаточное условие делимости произвольного натурального числа а на данное натуральное число m, называется признаком делимости на m. Различают общие признаки, имеющие силу для любого m, и частные — для отдельных значений m. Общий признак делимости выражает правило, посредством которого по цифрам числа а, записанного в системе счисления с основанием g, можно судить о делимости его на другое число m.

Французский математик Блез Паскаль (1623-1662) нашел общий признак делимости, который в терминах сравнений может быть сформулирован следующим образом:

Т е о р е м а 1 (общий признак делимости Паскаля). Для того чтобы Число а, записанное в произвольной g-ичной системе счисления в виде:

а=a_n gⁿ + a_n-1 g^n-1+…+ a₁ g+a₀, делилось на число m, необходимо и достаточно, чтобы число b = a_n r_n + a_n-1 r_n-1+…+ a₁ r₁ +a₀, делилось на m.

Доказательство. Пусть gⁱ ≡r_i, (mod m), где r_i - абсолютно наименьший вычет числа gⁱ по модулю m (i=1, 2,..., n). Тогда а=a_n gⁿ + a_n-1 g^n-1+…+ a₁ g+a₀ ≡ a_n r_n + a_n-1 r_n-1+…+ a₁ r₁ +a₀ (mod m). (1)

Число а делится на m тогда и только тогда, когда a_n gⁿ + a_n-1 g^n-1+…+ a₁ g+a₀ ≡ 0 (mod m). (2)

Из сравнений (1) и (2) и транзитивности отношения сравнимости получаем условие, равносильное условию (2): b = a_n r_n + a_n-1 r_n-1+…+ a₁ r₁ +a₀ ≡ 0 (mod m). (3)

Из доказанного следует вывод: для того, чтобы а делилось на m, необходимо и достаточно, чтобы b делилось на m. Теорема доказана.

Замечание. В процессе доказательства теоремы получен более сильный результат. Так как а ≡ b (mod m), то остатки от деления чисел а и b на m совпадают. В качестве следствий из общего признака Паскаля вытекают различные частные признаки делимости. Рассмотрим некоторые из них (наиболее часто ислодьзуемые на практике).

Следствие 1 Пусть m — делитель числа g -1. Для того чтобы число, записанное в g-ичной системе счисления, делилось на m, необходимо и достаточно, чтобы сумма его цифр делилась на m.

Доказательство. В данном случае gⁱ ≡1 (mod (g -1)), a g -1⁞ m тогда gⁱ ≡ 1 (mod m), т.е. r_i = 1, а потому:

b = a_n + a_n-1 +…+ a₁ +a_0.

Таким образом, для того чтобы а делилось на m, необходимо и достаточно, чтобы сумма цифр этого числа делилась на m.

Для чисел, записанных в десятичной системе, из сформулированного признака вытекают известные признаки делимости на 9 и 3. Для того чтобы число а делилось на 3 (на 9), необходимо и достаточно, чтобы сумма его цифр делилась на 3 (на 9).

Пример. Выяснить, делится ли число 36 452 712 на 9. Если нет, найти остаток от деления его на 9.

Найдём сразу остаток от деления на 9 (смотри замечание): r ≡ (3 + 6) + (4 + 5) + (2 + 7) + (1 + 2) ≡ 3 (mod 9). Остаток r равен 3.

Следствие 2. Пусть m — делитель числа g +1. Для того чтобы число, записанное в g-ичной системе счисления, делилось на т, необходимо и достаточно, чтобы разность между суммами цифр на четных и нечетных местах делилась на т.

Доказательство. В данном случае gⁱ≡(-1)ⁱ(mod(g+1)), a g+1⁞m; тогда gⁱ≡(-l)ⁱ(mod т),т.е.. r_i =(-1)ⁱ, а

потому b = a_n (-1)ⁿ + a_n-1 (-1)^n-1 +…+ a₂ (-1)² +a₁ (-1) +a₀. Отсюда вытекает утверждение следствия.

Для чисел, записанных в десятичной системе, получаем известный признак делимости на 11: для того чтобы число делилось на 11, необходимо и достаточно, чтобы разность между суммами цифр на четных и нечетных местах делилась на 11.

Например, число 25 697058 не делится на 11, так как разность

(2 + 6 + 7 + 5) - (5 + 9 + 0 + 8) = 20 - 22 = -2 не делится на 11.

Число 905784 делится на 11,т.к. 4-8 + 7- 5+0-9 ⁞11.

Часто удобен признак делимости на 11 в следующей формулировке:
Число a_n 10ⁿ + a_n-1 10^n-1+…+ a₁ 10+a₀ делится на 11 тогда и только тогда, когда знакопеременная сумма a₀ - a₁ + a₂ - a₃+… делится на 11.

Следствие 3. Пусть т — делитесь числа g^k. Для того чтобы число, записанное в g-ичной системе счисления, делилось на т, необходимо и достаточно, чтобы число, записанное последними к цифрами данного числа, делилось на т.

Доказательство. В данном случае gⁱ ≡ 0(mod g^к) для i>=k, а потому a = a_n gⁿ +…+ a_k g^k + a_k-1 g^k-1 +…+a₁ g+a₀ ≡ a_k-1 g^k-1 +…+a₁ g+a₀ (mod g^k).

Но так как g^k ⁞ m, то

a ≡ a_k-1 g^k-1 +…+a₁ g+a₀ (mod m)

или a_k-1 …a₁ a_0g ≡0 (mod m). (*)

Из (*) вытекает утверждение следствия.

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

1) Основание 10¹ (здесь k = 1) делится на 2,5,10.

В этом случае получим признаки делимости на 2,5,10.

а) Для делимости числа на 2 необходимо и достаточно, чтобы последняя цифра была четной.

б)Для делимости числа на 5 необходимо и достаточно, чтобы последняя цифра делилась на 5 (последняя цифра 0 или 5).

в)Для делимости числа на 10 необходимо и достаточно, чтобы оно оканчивалось нулем.

Делителем числа 10² (здесь k = 2) являются числа 4,25,50,100. Применяя следствие 3, получаем известные признаки делимости на 4,25,50,100.

Для того чтобы число делилось на 4, необходимо и достаточно, чтобы число, записанное последними двумя (k=2) цифрами, делилось на 4.

Для того чтобы число делилось на 25, необходимо и достаточно, чтобы его последние две цифры составляли числа 00,25,50 или 75.

Аналогично можно вывести признаки делимости на делители числа 10³(k=3), на числа 8,125,.... Здесь надо рассматривать число, записанное последними тремя цифрами данного числа. В заключение выведем общий признак делимости на 7,11,13. Признак делимости на 7 и на 13 можно получить и непосредственно из общего признака Паскаля, но он получается неудобным для практического использования. Мы воспользуемся другим приемом и сразу для десятичной системы.

Теорема 2.Для того чтобы число делилось на 7, или на 11, или на 13, необходимо и достаточно, чтобы разность между числом, записанным последними тремя цифрами, и числом, записанным остальными цифрами данного числа (или наоборот), делилась на 7, или на 11, или на 13.

Доказательство. Любое число а можно представить в виде а = n* 1000 + q, где q - число, записанное последними тремя цифрами числа а, а n - всеми остальными цифрами (пример: 21829 296 = 21829 *1000 + 296). Заметим также, что 7*11*13 = 1001. Запишем далее так: а =n*1001-n+q=n*1001+(q-n); отсюда получим: a ≡q — n (mod 1001), (4) или a ≡q - n (mod 7 * 11 * 13). Из (4) следует вывод: для того чтобы число а делилось на 7, или на 11, или на 13, необходимо и достаточно, чтобы число q - n (или n-q) делилось на 7, или на 11, или на 13.

Пример 1. Делится ли число 56 704 на одно из чисел: 7, 11, 13?

Находим: q-n=704-56 = 648. Но число 648 не делится ни на 7; ни на 11, ни на 13; следовательно, и данное число не делится ни на одно из чисел: 7,11,13.

Пример 2. Делится ли число 454111 на 7? 454 -111 = 343,343⁞7, следовательно, 454111 7.

Если т — составное число, то разлагаем его в произведение взаимно простых чисел. Затем для множителей применяем признаки делимости.

Пример 3. Делится ли число: а) 2 856 312 на 6? б) 2 856 375 на 75?

Р е ш е н и е. а) 6 = 2*3,(2,3) = 1. Сумма цифр числа 2856312 равна 273. Значит, число делится на 3. А так как его последняя цифра 2 - четная, то оно делится и на 2. Значит, оно делится на 6.

б)75=3*25,(3,25=1). Далее, применяя иризнаки делимости на 3 и на 25, убеждаемся, что число делится на 75.

§3. Проверка результатов арифметических действий

С помощью сравнений легко указать необходимые признаки правильности и достаточные признаки неправильности результатов выполнения арифметических действий сложения, вычитания и умноженияцелых чисел.

Результат действия сложения, вычитания и умножения есть целая рациональная функция компонент, а потому если вместо данных чисел взять наименьшие положительные или наименьшие по абсолютной величине вычеты этих чисел по какому-либо модулю, то результат действий над этими вычетами должен быть сравним по тому же модулю с наименьшим вычетом проверяемого результата. Если сравнение не имеет места, то результат получен неверно. В качестве модуля удобнее брать число, наименьшие вычеты по которому легко вычисляются (например, для десятичной системы счисления: 9,11 или 5). В случае 9 можно брать вместо наименьших вычетов просто сумму цифр, в случае 11 § разность между суммами цифр, стоящих на четных и нечетных местах (считая справа налево).

Следует отметить, что неправильность соответствующего сравнения гарантирует неправильность выполнения действий. Правильность соответствующего сравнения лишь подтверждает, но не гарантирует
правильность результата. Дело в том, что проверкой с помощью 9 или 11 не может быть обнаружена ошибка на число, кратное 9 или 11, соответственно. Поэтому чаще всего проверяют одновременно числами 9 и 11. В этом случае возможна ошибка на число, кратное 99, но вероятность такой ошибки очень мала.

Пример 1. Проверим правильность выполнения действий (с помощью 9 и 11):

3740 297 - 561245 = 8179 052.

а)Проверка девяткой. Заменяем числа суммами их цифр:

37 - 23 ≡ 32 (mod 9), 14 ≡ 32 (mod 9).

Сравнение подтверждает, но не гарантирует правильности выполнения действий.

б)Проверка числом 11.

8740 297 ≡ (7+ 2 + 4 +8)-(9 + 0 +7) ≡5 (mod 11),

561245 ≡ (5 + 2 + 6) - (4 +1 + 5) ≡ 3 (mod 11),

8179 052 ≡ (2 + 0 + 7 + 8) - (5 + 9 +1) ≡ 2 (mod 11).

Получим: 5 - 3 ≡ 2 (mod 11), 2 ≡ 2 (mod 11).

Проверка одиннадцатью подтверждает правильность получения результата (хотя абсолютной гарантии нет, так как возможна ошибка на число, кратное 99).

Пример 2. Проверим правильность выполнения действий (с помощью 9):

375 426*3846 = 1443 888 276. Заменяем числа суммами их цифр:

27*21≡51 (mod 9).

Сравнение неверное, следовательно, действие выполнено неправильно. Результат деления проверяется с помощью контроля умножения (делимое равно делителю, умноженному на частное, плюс остаток). Вообще следует иметь в виду, что соблюдение контроля при неверных вычислениях связано, по меньшей мере, с двукратной ошибкой в вычислениях, поэтому следует признать контроль (даже одним числом) действенным.