Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

ділиться на 7.

Якщо отримане число при діленні на 7 має ненульову остачу, то таку остачу буде мати і вихідне число.

Приклад

Перевірити, чи ділиться на 7 число 24 135 897 155.

Розв’язання

Розбиваючи число на трійки, починаючи з правого краю, маємо цифри 155, 897, 135, 24. Трійки з непарними номерами 1, 3 – 155 і 135, з парними номерами 2, 4 – 897 і 24. Сумуємо окремо трійки з парними і непарними номерами. 155+135=290 – сума трійок з непарними номерами; 897+24=921 – сума трійок з парними номерами, різниця цих сум 290 − 921 = −631 – число яке на 7 не ділиться. Має остачу r = −1 або r = 6 . Отже, вихідне число має остачу від ділення на 7 теж 6 (або –1).

Дійсно 24135897155 = 3447985307 6 , 7 7

або 24135897155 = 3447985308 − 1 . 7 7

е) Такою самою є ознака подільності на 13. Перевірте самі:

знайдіть залишки від ділення на 13 чисел 103 та 106 . Порівняйте з остачами від ділення на 7.

Приклад

Перевірити, чи ділиться на 13 число 24 135 897 162.

Розв’язання

Розбиваючи число на трійки, починаючи з правого краю, маємо цифри: 162, 897, 135, 24. Трійки з непарними номерами 1, 3 – 162 і 135, з парними номерами 2, 4 – 897 і 24. Сумуємо окремо трійки з парними і непарними номерами. 162+135=297 – сума трійок з непарними номерами; 897+24=921 – сума трійок з парними номерами, різниця цих сум 297 − 921 = −624 . Число 624 на 13 ділиться.

12

Отже, вихідне число 24 135 897 162 ділиться на 13.

24135897162 =

1856607474 .

13

ж) Подільність на числа, які подаються у вигляді 10k ±1:

10 A + a0 = (10k ±1)× q , де q Î Z - повна частка.

Не порушуючи співвідношення і з метою виділення у лівій частині отриманої рівності частини, що ділиться на 10k ±1, множимо її на k з урахуванням, що (10k +1, k ) =1:

k (10 A + a0 ) = (10k ±1)× q ×k; q ×k = q1 Î Z , 10kA + ka0 = (10k ±1)× q1 .

10kA ± A m A + ka0 = (10k ±1)× q1; A(10k ±1) m A + ka0 = (10k ±1)× q1 .

В останній рівності права частина ділиться на 10k ±1, перший доданок у лівій частині - A(10k ±1) - теж ділиться на

10k ±1. Отже з урахуванням властивостей подільності цілих чисел число лівої частини буде ділитися на 10k ±1 тільки в тому разі, коли m A + ka0 ділиться на це число.

Отриману умову подільності можна записати так:

13

число 10k -1, якщо A + ka0 ділиться на це число.

Для прикладу складемо умову подільності довільного числа N на число 19.

19 = 10 × 2 -1.

Тут k = 2 , число 19 підходить під умову 2, тобто довільне

Процес виконується до тих пір, поки не стане очевидно, що отримане число або ділиться на 19, або не ділиться на нього.

A = 1235, a0 = 0, A + 2a0 = 1235 + 0 = 1235; A = 123, a0 = 5, A + 2a0 = 123 +10 = 133; A = 13, a0 = 3, A + 2a0 = 13 + 6 = 19.

Остання сума ділиться на 19, отже, вихідне число ділиться на 19.

Висновок: число 12 345 687 ділиться на 19.

Дійсно 12345687 = 649773 . 19

14

1.5. НЕПЕРЕРВНІ ДРОБИ

Будь-яке дійсне число α = a Q можна подати як b

неперервний дріб за допомогою алгоритму Евкліда:

Використовуючи розкладання числа за алгоритмом Евкліда, неперервний дріб можна подати, як скінчену послідовність неповних часток

15

16

..............................................................................................................

Останні 2 стовпчики використовуються тільки у разі, коли

дріб α = a такий, що не скорочується. b

Приклад

Розкласти у неперервний дріб 151 . 13

Розв’язання

151 дріб такий, що не скорочується. Розкладемо за

13

17