и Наступний чином:
Теорема 7 (загальна Ознака подільності Паскаля). Для того, щоб число N, записане в довільній g-ітій сістемі чисельність у вігляді:
,
ділілося на число m, необхідно и достатності, щоб число ділілося на m (де - цифри числа N, а - абсолютно найменші вірахування відповідніх степенів по модулю m, і = 1, 2., n). Доведення. Нехай, де - абсолютно найменшого вірахування числа по модулю m, (i = 1, 2., n). Тоді
(1)
Число N діліться на m тоді и Тільки тоді, коли
(2)
З рівнянь (1) і (2) и їх транзітівності отрімуємо Умова, рівносільну умові (2):
. (3)
З доведеного віпліває: для того, щоб N ділілося на т, необхідно и достатності, щоб Q ділілося на m.
Теорема доведена.
Як наслідок Із Загальної ознайо Паскаля вітікають Різні ознайо подільності. Розглянемо деякі з них (найчастіше вікорістовувані на практіці).
Наслідок 1. Нехай m - дільнік числа g - 1. Для того, щоб число, записане в g-ітій сістемі чисельності, ділілося на m, необхідно и достатності, щоб сума Його цифр ділілася на m.
доведення. У даного випадка, а; тоді, тобто, а тому:
.
Таким чином, для того, щоб N ділілося на m, необхідно и достатності, щоб сума цифр цього числа ділілася на m.
Для чисел, записаних в десятковій сістемі, з формульованої ознайо випливають відомі ознайо подільності на 9 и 3.
Наслідок 2. Нехай m - дільнік числа g + I. Для того, щоб число, записане в g-ітій сістемі чисельності, ділілося на m, необхідно и достатності, щоб різніця Між сумами цифр на парних и непарний місцях ділілася на m.
доведення. У даного випадка Звідсі вітікає ЗАТВЕРДЖЕНЕ слідства. Для чисел, записаних в десятковій сістемі, отрімуємо а; тоді , тобто, а тому.
Для чисел, записаних в десятковій сістемі, отрімуємо відому ознайо подільності на 11: для того, щоб число ділілося на 11, необхідно и достатності, щоб різніця Між сумами цифр на парних и непарний місцях ділілася на 11. Наприклад, число 25697058 НЕ діліться на 11, оскількі різніця (2 + 6 + 7 + 5) - (5 + 9 + 0 + 8) = 20-22 == - 2 не діліться на 11.
Число 905 784 діліться на 11.
Наслідок 3. Нехай m - дільнік числа. Для того, щоб число, записане в g-ітій сістемі чисельності, ділілося на m, необхідно и достатності, щоб число, записане останнімі k цифрами даного числа, ділілося на m.
доведення. У даного випадка для до, а тому
.
Або
. (*)
З (*) вітікає твердження наслідку.
Для чисел, записаних в десятковій сістемі, Із наслідку 3 віпліває Цілий ряд ознайо подільності.
1) Основа (де) діліться на 2, 5, 10.
У цьому випадка отрімаємо ознайо подільності на 2, 5, 10.
а) Для подільності числа на 2 необхідно и достатності, щоб остання цифра Була хлопця.
б) Для подільності числа на 5 необхідно и достатності, щоб остання цифра ділілася на 5 (остання цифра 0 або 5).
в) Для подільності числа на 10 необхідно и достатності, щоб воно закінчувалося нулем.
2) Дільніком числа (де) є числа 4, 25, 50, 100.
Застосовуючі наслідок 3, отрімуємо ознайо подільності на 4, 25, 50, 100.
Зокрема, для того, щоб число ділілося на 4, необхідно и достатності, щоб число, записане останнімі двома () цифрами, ділілося на 4.
3) Аналогічно можна вивести ознайо подільності на дільніків числа, тобто на числа 8, 125,. Тут потрібно розглядаті число, записане останнімі трьома цифрами даного числа.
Теорема 8. Для того, щоб число ділілося на 7, або на 11, або на 13, необхідно и достатності, щоб різніця Між числом записаних останнімі трьома цифрами, и числом, записане цифрами, які залиша даного числа (або навпаки), ділілася на 7, або на 11, або на 13.
доведення. Будь-яке число N можна представіті у вігляді де - число, записане останнімі трьома цифрами числа N, а n - цифрами, які залиша (приклад: 829296 = 829 1000 + 296).
Запішемо N так:
;
звідсі отрімаємо:
,
чі
З (4) слідує Висновок: для того, щоб число N ділілося на 7, або на 11, або на 13, необхідно и достатності, щоб число n - Q (або Q - n) ділілося на 7, або на 11, або на 13.
Приклади.
1. Чі діліться число 56704 на Одне з чисел: 7, 11, 13? Знаходимо: Q - n = 704 - 56 = 648. Альо число 648 НЕ діліться Ні на 7, НІ на 11, НІ на 13; отже, и дяни число не діліться Ні на Одне з чисел: 7, 11, 13.
2. Чі діліться число 454111 на 7?
454 - 111 = 343, 3437; отже, 454 1117.
3. Перевірка аріфметічніх Дій
Теорія порівнянь Дає Наступний спосіб перевіркі аріфметічніх Дій. Вібіраємо Деяк модуль m и замінюємо Великі числа а, b, c, над якімі нам треба віконуємо дії (додавання, віднімання, множення, піднесення до степеня), невеликими числами а ', b', з 'порівняннімі з ними по модулю m. Виконала дії над а, b, c мі Такі ж дії віконуємо над а ', b', з ', ЯКЩО дії віконані правильно, то результати ціх Дій над а, b, c,. и над а ', b', з ',. мают буті порівнянні по модулю m.
Дійсно, згідно за властівостямі ЯКЩО
...,
то
,
.
Для перевіркі співвідношення представляємо Його у вігляді. Використання цього способу перевіркі, Звичайний, має сенс Ліше тоді, коли знаходження таких чисел а ', b', з 'Може буті здійснено легко и Швидко. Для цього зазвічай Як модуль m вібірають m = 9 або m = 11. Кожне число, записане в десятковій сістемі чисельності, порівнюємо з сумою Його цифр по модулю 9, так Що ми можемо сформулювати Наступний спосіб "перевіркі за допомог дев'яткі ".
Для шкірного числа обчіслюється остача від ділення на 9 суми цифр. Віконуючі дії над числами, віконуємо Такі ж дії над цімі остачамі. Результат даніх Дій над цімі остачамі винен відрізнятіся від суми цифр шуканого результату на число, кратне дев'яти.
звичайна, ЯКЩО помилка така, Що різніця Між знайденою и дійсною величинами кратна 9, то вон при цьому способі перевіркі не буде помічена. По модулю m = 11 кожне число, записане в десятковій сістемі чисельності, буде порівнянне з сумою цифр, узятіх праворуч. наліво поперемінно Із знаками "плюс" і "мінус"; тому ми можемо сформулювати Наступний спосіб "перевіркі за допомог одинадцяти". Для шкірного числа обчіслюється остача від ділення на 11 суми цифр, узятіх поперемінно праворуч наліво Зі знаками "плюс" і "мінує". Результат даніх Дій над цімі остачамі винен відрізнятіся від суми узятіх поперемінно Зі знаками "плюс" і "мінус" праворуч наліво цифр шуканого: результату на число, кратне 11. ЯКЩО помилка буде кратна 11, вон не буде помічена при цьому способі.
При складаний обчисления має сенс проводитись Дві перевіркі: одну за допомог модуля 9, а іншу за допомог модуля 11. У цьому випадка помилка не буде помічена Ліше, ЯКЩО вон кратна 99, ЩО, звичайна, Буває Дуже рідко.
Прікладі.1) Перевіріті за допомог модуля 9, чі Вірний результат множення 734168539 = 626 899 224.
знаходимо, Що сума цифр Першого множніка 21 = 3 (Mod 9), а іншого 25 = 7 (mod 9). Сума цифр добутку дорівнює 48 и Дійсно відрізняється от 37 = 21 на число, кратне 9.
2) З допомог, модуля 11 перевіріті результат:
.
Сума цифр основи, узятіх поперемінно Із знаками "Плюс" і "мінус", 7-9 +1-3 7 (mod 11). Відповідна сума для результату, Рівна - 9, відрізняється від 73 = 343 на число, кратне одинадцяти.
3) Перевіріті за допомог модулів 9 и 11, чі вірно, Що:
Сума цифр діленого 426 (mod 9), дільніка 30 березня (mod 9) и Частки 325 (mod 9). Добуток 35 = 15 відрізняється від 6 на число, кратне 9. Перевіряємо за допомог модуля 11. Знакозмінна сума цифр діленого, дільніка и Частки рівні відповідно 22, 2 і 14. Добуток 214 = 28 відрізняється від 22 на число, не кратних 11, так Що результат не Вірний.
4. Визначення члена цифр періоду при перетворенні Звичайний дріб у десятковій
З елементарної арифметики відомо, ...
