Материал: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi
103 |
= 1000 = 7 ×142 + 6, q = 142, r = 6 , |
||||||
|
|
3 |
|
|
3 |
|
|
àáî 103 =1000 = 7 ×143 -1, |
|
q = 143, |
r = -1; |
||||
|
|
|
|
3 |
|
|
3 |
104 |
= 10 000 = 7 ×1428 + 4 , q |
4 |
= 1428, r |
|
= 4; |
||
|
|
|
|
4 |
|
||
105 |
=100 000 = 7 ×14285 + 5, |
q |
= 14285, r = 5; |
||||
|
|
|
|
5 |
|
|
5 |
106 |
=1000 000 = 7 ×142857 +1, r = 1 . |
|
|
||||
|
|
|
|
|
6 |
|
|
|
Після r6 |
значення остач будуть повторюватися, починаючи з |
|||||
r1 = 3 . Тим |
самим отримана |
послідовність вміщує у собі усі |
|||||
можливі ненульові остачі від ділення довільного степеня числа
10 на 7.
На увагу заслуговують 2 остачі – остача від ділення на 7
числа 103 r = −1 і остача від ділення на 7 числа 106 |
r = 1. |
3 |
6 |
Якщо цифрову послідовність довільного натурального числа N = an an−1...a2 a1a0 розбити на трійки, починаючи з наймолодших позицій, то число набере вигляду:
N= ... +106 a8 a7 a6 +103 a5a4a3 + a2 a1a0 = ... + (7 × q6 +1) a8a7 a6 +
+(7 ×q3 -1) a5a4 a3 + a2 a1a0 = 7 × N1 + ... + a8a7 a6 - a5 a4 a3 + a2 a1a0 ,
де 7 × N1 - доданок всіх елементів розкладання числа, які мають у собі множник 7;
... + a8a7 a6 - a5a4a3 + a2 a1a0 - сума остач від ділення числа
103k , k Î N на 7.
З такого подання числа можна вивести ознаку ділення на 7.
Для того щоб узнати чи ділиться конкретне число N на 7 без остачі, необхідно попередньо числову послідовність даного числа розбити на трійки, починаючи з правого краю, понумерувати трійки, скласти отримані тризначні числа з непарними номерами окремо, з парними – окремо. Далі від суми тризначних чисел з непарними номерами відняти суму тризначних чисел з парними номерами.
Якщо отримане число ділиться на 7, то вихідне число
11
ділиться на 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:
Прикладом |
таких |
чисел |
можуть |
бути |
числа |
|||||
19 = 10 × 2 -1, 31 = 10 ×3 +1, 29 = 10 ×3 -1 і т. ін. |
|
|
||||||||
Для |
визначення |
ознаки |
подільності |
цілого |
числа |
|||||
N = |
|
|
10k ±1 |
|
|
|
|
|||
an an−1...a2 a1a0 |
на |
подамо вихідне |
число |
таким |
||||||
|
N =10 A + a0 , |
A = |
|
. |
|
|
||||
способом: |
an an−1...a2 a1 |
|
|
|||||||
Якщо |
число |
N |
ділиться |
на |
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 ділиться на це число.
Отриману умову подільності можна записати так:
1. Довільне число N =10 A + a0 , |
A = |
an an−1...a2 a1 |
ділиться на |
число 10k +1, якщо A - ka0 ділиться на це число. |
|
||
2. Довільне число N =10 A + a0 , |
A = |
|
|
an an−1...a2 a1 |
ділиться на |
||
13
число 10k -1, якщо A + ka0 ділиться на це число.
Для прикладу складемо умову подільності довільного числа N на число 19.
19 = 10 × 2 -1.
Тут k = 2 , число 19 підходить під умову 2, тобто довільне
число N = 10 A + a0 , |
A = |
an an−1...a2 a1 |
ділиться на |
число 19, |
якщо число A + 2a0 ділиться на 19. |
|
|||
Приклад |
|
|
|
|
Перевірити, чи ділиться число 12 345 687 на 19. |
|
|||
Розв’язання |
|
|
|
|
N = 12345 687; A = 1234568, a0 = 7, |
|
|||
A + 2a0 = 1234568 +14 = 1234582; |
|
|||
Отримали велике число N1 = 1234582 , яке теж |
необхідно |
|||
дослідити на подільність на 19: |
|
|||
A = 123458, a0 = 2, |
A + 2a0 = 1234 58 + 4 = 123462 . |
|
||
Отримане число завелике, його подільність на 19 не |
||||
очевидна. Робимо ще один крок: |
|
|||
A = 12346, a0 = 2, |
A + 2a0 = 12346 + 4 = 12350 . |
|
||
Процес виконується до тих пір, поки не стане очевидно, що отримане число або ділиться на 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
неперервний дріб за допомогою алгоритму Евкліда:
a= bq1 + r1;
b= r1q2 + r2 ;
r1 = r2 q3 + r3 ;
a = q + 1 ; b 1 b
r1
b |
|
= q + |
1 |
; |
||
|
|
|
||||
r |
2 |
|
r1 |
|
|
|
|
|
|
|
|
||
1 |
|
|
|
|
|
|
|
|
|
r2 |
|
|
|
|
|
|
|
|
|
|
r1 |
|
= q + |
1 |
|
|
|
|
|
|
|
|
||
r |
3 |
|
r2 |
|
|
|
|
|
|
|
|
||
2 |
|
|
|
|
|
|
|
|
|
r3 |
|
|
|
|
|
|
|
|
|
|
..................................... |
|
|
|
|
|
|
|
|
|
|
||||||||||
r |
= r q + r ; |
|
|
|
rn−2 |
= q + |
1 |
; |
||||||||||||
|
|
|
|
|
|
|||||||||||||||
n−2 |
|
n−1 n n |
|
|
|
rn−1 |
n |
|
rn−1 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rn |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
r |
= r q |
n+1 |
; |
|
|
|
|
rn−1 |
= q |
. |
|
|
||||||||
|
|
|
|
|
|
|||||||||||||||
n−1 |
|
n |
|
|
|
|
|
rn |
|
|
|
n+1 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Тоді |
a |
= q + |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
||||||
|
|
b |
1 |
|
+ |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
q2 |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
q3 |
+ ... |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
M |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
... + |
|
|
1 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
q |
|
+ |
1 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
n |
qn+1 |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Використовуючи розкладання числа за алгоритмом Евкліда, неперервний дріб можна подати, як скінчену послідовність неповних часток
15