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

курсовая работа

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 899224.

Знаходимо, що сума цифр першого множника 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 3 (mod 9) і частки 325 (mod 9). Добуток 35=15 відрізняється від 6 на число, кратне 9. Перевіряємо за допомогою модуля 11. Знакозмінна сума цифр діленого, дільника і частки рівні відповідно 22, 2 і 14. Добуток 214 = 28 відрізняється від 22 на число, не кратне 11, так що результат не вірний.

Делись добром ;)