Файл: Теорія чисел в криптографії.pdf

Питання 5. Ознаки подільності чисел. Загальні принципи:

Будь-яке ціле (n +1)-значне число можна подати у десятковій системі так:

Застосовують ще один запис числа N як послідовності цифр:

N = an an−1 ...a2 a1ao ; 0 £ ai £ 9; i = 0,n

Розв’язати питання подільності такого числа на будь-яке інше число k можна розглянувши послідовність залишків від ділення степенів основи числення на k :

Відповідно до властивостей такої послідовності відносно k можна вивести відповідне правило подільності.

а) Подільність цілого числа на 2:

Перший доданок ділиться на 3 та на 9, отже для подільності N на 3 або на 9 необхідно, щоб сума цифр числа N ділилася на 3 або на 9 відповідно.

в) Подільність на 4:

N = (10n an +10n−1 an−1 + ...+102 a2 + 8a1 )+ (2a1 + a0 )

Отже для подільності N на 4 необхідно, щоб другий доданок 2a1 + a0 ділився на 4. Наприклад 183 546 976 ділиться на 4 бо 7 × 2 + 6 = 20M4

в) Подільність на 5:

N =10n an +10n−1 an−1 + ...+102 a2 +10a1 + a0

Усі доданки крім останнього діляться на 5, отже для подільності N на 5 необхідно, щоб остання цифра числа a0 ділилася на 5.

г) Подільність на 8:

N = (10n an +10n−1 an−1 + ...+ 96a2 + 8a1 )+ (4a2 + 2a1 + a0 )

Отже для подільності N на 8 необхідно, щоб другий доданок 4a2 + 2a1 + a0 ділився на 8. Відома і інша ознака подільності на 8 – для того, щоб все число N = an an−1 ...a2 a1ao

ділилося на 8 необхідно, щоб число a2 a1a0 ділилося на 8.

11

Для визначення подільності на 8 тризначного числа зручно розглянути його, як

10(10a2 + a1 )+ a0 = 8(10a2 + a1 )+ 2(10a2 + a1 )+ a0

Якщо 2(10a2 + a1 ) + a0 ділиться на 8, то і все число ділиться на 8.

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

Приклад: Дослідити число 195 347 839 на подільність на 8.

Розв’язання

Визначимо, чи ділиться 839 на 8:

839 =10 ×83 + 9 2 ×83 + 9 =175 = 10 ×17 + 5 2 ×17 + 5 = 39 10 ×3 + 9

За ознакою число 839 не ділиться на 8 без залишку. Залишок має значення 7. Отже і вихідне число N = 195347839 при діленні на 8 має залишок 7.

Дійсно, 195347839 = 24 418 479 7 8 8

д) Подільність на 7:

Для формулювання ознаки подільності на 7 дослідимо послідовність залишків від ділення степенів числа 10 на 7:

отримана послідовність вміщує у собі усі можливі ненульові залишки від ділення довільного степеня числа 10 на 7.

= 7 × N1 + ...+ a8 a7 a6 - a5 a4 a3 + a2 a1a0

Тут 7 × N1 - доданок всіх елементів розкладення числа, які мають у собі множник 7,

... + a8 a7 a6 - a5 a4 a3 + a2 a1a0 - сума залишків від ділення степенів числа 10, кратних 3, на 7. З такого подання числа можна вивести ознаку ділення на 7:

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

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

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

12

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

Розв’язання

Розбиваючи число на трійки з правого боку, маємо цифри: 155, 897, 135, 24. З них непарні: 155 і 135, парні – 897 і 24. Сумуємо їх: 155+135=290 – сума непарних трійок; 897+24=921 – сума парних трійок, 290 − 921 = −631- число на 7 не ділиться. Має залишок r = −1 або r = 6

Отже вихідне число має залишок від ділення на 7 теж 6 (або -1).

Дійсно 24135897155 = 3447985307 6 або 24135897155 = 3447985308 - 1

Якщо число N ділиться на 19, то можна записати: 10 A + a0 = 19 × q , де q - повна частка.

Не порушуючи рівності і з ціллю виділення ліворуч частини, що ділиться на 19 умножимо отриману рівність на 2:

2(10 A + a0 ) =19 × q × 2; 19 A + (A + 2a0 ) = 19 × q × 2

Отже, для того, щоб число N = an an−1 ...a2 a1a0 ділилося на 19 необхідно, щоб число (A + 2a0 ) ділилося на 19, A = an an−1 ...a2 a1 .

Приклад

Перевірити, чи ділиться число 12 345 687 на 19.

Розв’язання

N =12345687; A = 1234568, a0 = 7, A + 2a0 =1234568 +14 = 1234582; A = 123458, a0 = 2, A + 2a0 = 123458 + 4 =123462

A = 12346, a0 = 2, A + 2a0 =12346 + 4 = 12350; 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

13

Питання 6 Неперервні дроби.

Будь-яке дійсне число α R можна подати, як неперервний дріб. Нехай q1 - найбільше

Якщо α - ірраціональне число, то таке подання буде безкінечним.

Якщо ж α = a Q , то неперервний дріб буде скінчений і розкладення можна отримати за b

допомогою алгоритму Евкліда:

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

a = [q1 ,q2 , ...,qn ,qn+1 ] b

14

Зробимо позначення: