Арифметичні застосування теорії конгруенцій (стр. 3 из 6)

Запишемо N так:

;

звідси отримаємо:

,

чи

З (4) слідує висновок: для того, щоб число N ділилося на 7, або на 11, або на 13, необхідно і достатньо, щоб число n - Q (або Q - n) ділилося на 7, або на 11, або на 13.

Приклади.

1. Чи ділиться число 56 704 на одне з чисел: 7, 11, 13? Знаходимо: Q - n = 704 - 56 = 648. Але число 648 не ділиться ні на 7, ні на 11, ні на 13; отже, і дане число не ділиться ні на одне з чисел: 7, 11, 13.

2. Чи ділиться число 454 111 на 7?

454 - 111 = 343, 343

7; отже, 454 111 7.

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, чи вірний результат множення 73416

8539 = 626 899224.

Знаходимо, що сума цифр першого множника 21=3 (mod 9), а другого 25 = 7 (mod 9). Сума цифр добутку дорівнює 48 і дійсно відрізняється від 3

7 = 21 на число, кратне 9.

2) З допомогою, модуля 11 перевірити результат:

.

Сума цифр основи, узятих поперемінно із знаками „плюс" і „мінус", 7-9+1-3

7 (mod 11). Відповідна сума для результату, рівна - 9, відрізняється від 73 = 343 на число, кратне одинадцяти.

3) Перевірити за допомогою модулів 9 і 11, чи вірно, що:

Сума цифр діленого 42

6 (mod 9), дільника 30 3 (mod 9) і частки 32 5 (mod 9). Добуток 3 5=15 відрізняється від 6 на число, кратне 9. Перевіряємо за допомогою модуля 11. Знакозмінна сума цифр діленого, дільника і частки рівні відповідно 22, 2 і 14. Добуток 2 14 = 28 відрізняється від 22 на число, не кратне 11, так що результат не вірний.

4. Визначення члена цифр періоду при перетворенні звичайного дробу в десятковий

З елементарної арифметики відомо, що звичайний нескоротний дріб у перетворюється в скінченний десятковий дріб тоді і тільки тоді, коли канонічний розклад знаменника не містить простих множників відмінних від 2 і 5.

Нехай

нескоротний дріб і канонічний розклад знаменника містить прості числа, відмінні від 2 і 5; перетворюватимемо такий дріб у десятковий.

Нескінченний десятковий дріб, десяткові знаки якого періодично повторюються, називається періодичним, десятковим дробом. Якщо десяткові знаки повторюються, починаючи з першого, то десятковий дріб називається чистим періодичним, у противному разі він називається мішаним періодичним дробом.

Теорема 1. Якщо

нескоротний дріб і (

,

10) = 1, то цей дріб перетворюється у чистий періодичний десятковий дріб; число цифр у періодідробу дорівнює

, де

- показник, до - якого належить число 10 за модулем

.

Доведення. Справді, не порушуючи загальності міркувань, можна нескоротний дріб

вважати правильним (якщо він неправильний, тобто

, то. ми спочатку виділимо цілу частину); отже, можна вважати рівним одному з чисел, менших і взаємно простих з .

Перетворюватимемо дріб

у десятковий за загальними правилами:

для цього поділимо спочатку 10

на позначаючи через частку і через - остачу від цього ділення, отримаємо:

Тепер поділимо

на :

;

далі ділимо

на :

і т.д. Такий процес нескінченний, бо щоразу будуть остачі

, менші від і взаємно прості з . Справді, , за умовою, тому і ; аналогічно , а тому і т.д.