Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.06.2024
Просмотров: 49
Скачиваний: 0
1.4. ОЗНАКИ ПОДІЛЬНОСТІ ЧИСЕЛ
ЗАГАЛЬНІ ПРИНЦИПИ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Будь-яке |
|
ціле (n +1) - значне |
число |
можна подати |
у |
|||||||||||||||||
десятковій системі так: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
N = 10n a |
n |
+10n−1 a |
n−1 |
+ ... +102 a |
2 |
+10a + a ; |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
|
|
|
|
|
|
|||
0 £ ai £ 9; i = |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0, n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Застосовують ще один запис числа |
N |
|
як послідовності |
|||||||||||||||||||
цифр: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N = |
|
|
; |
|
0 £ ai |
£ 9; |
i = |
|
. |
|
|
|
|
|||||||
|
|
an an−1...a2 a1ao |
0, n |
|
|
|||||||||||||||||
Вирішити питання подільності числа |
N |
на будь-яке інше |
||||||||||||||||||||
число k можна, |
розглянувши послідовність остач від ділення |
|||||||||||||||||||||
степенів основи числення на k : |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
r0 = a0 - k × q0 ; r1 = 10 - k × q1; |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
r = 102 - k × q |
; ...; r |
= 10n - k × q |
n |
; |
|
|
|
|
|
|
|
|
|
|||||||||
2 |
|
2 |
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
де q - відповідні неповні частки від ділення 10i , i = |
|
|
|
k . |
||||||||||||||||||
0, n |
на |
|||||||||||||||||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ri , i = |
|
|
|
|
|
|
|||||||||||||||
Очевидно, що остачі |
0, n |
|
не перевищують числа |
k |
за |
|||||||||||||||||
значенням. Кількість різних цілих остач менша за k . Відповідно до властивостей такої послідовності остач
відносно k можна вивести відповідне правило подільності цілих чисел на число k .
а) Подільність цілого числа на 2:
N = 10n an +10n−1 an−1 + ... +102 a2 +10a1 + a0 .
Усі доданки, крім останнього діляться на 2, отже для подільності N на 2 необхідно, щоб остання цифра числа a0 ділилася на 2 (була парною).
8
б) Подільність на 3 та на 9: |
|
|
|
|
||||||||
|
N = |
99...9 +1 a |
n |
+ |
99...9 +1 a |
n |
−1 |
+ ... |
||||
|
|
{ |
|
|
|
{ |
|
|
||||
|
|
n |
|
|
|
|
n−1 |
|
|
|
|
|
... + (99 +1) a2 + (9 +1) a1 + a0 = |
|
|
|
|
||||||||
= |
9...9 a |
+ 9...9 a |
n−1 |
+ ... + 99a |
2 |
+ 9a |
|
+ |
|
|||
|
{ n |
{ |
|
|
|
|
1 |
|
|
|
||
|
n |
n−1 |
|
|
|
|
|
|
|
|
|
|
+ (an + an−1 + ... + a2 + a1 + a0 ) .
Перший доданок ділиться на 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 = 20 , 20 ділиться на 4.
г) Подільність на 5:
N = 10n a |
n |
+10n−1 a |
n−1 |
+ ... +102 a |
2 |
+10a + a . |
|
|
|
|
|
1 0 |
|||
Усі доданки, крім останнього, діляться на 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 – для того щоб все
9
число |
N = |
an an−1...a2 a1ao |
ділилося на 8, |
необхідно, щоб число |
||
|
|
ділилося на 8. |
|
|
|
|
|
a2 a1a0 |
|
|
|
||
|
Для |
визначення |
подільності |
на |
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
|
10↔2 |
|
|
|
10↔2 |
2 ×17 + 5 = 39 10 ×3 + 9 |
|||||
10↔2 |
|
10↔2 |
|||
6 + 9 = 15 = 10 ×1+ 5 2 + 5 = 7 . |
|||||
10↔2 |
10↔2 |
||||
За ознакою число 839 не ділиться на 8 без остачі. Остача має |
|||||
значення 7. Отже, вихідне число N = 195347839 при діленні на |
|||||
8 має остачу 7. |
|
|
|
|
|
Дійсно, |
195347839 |
= 24 418 479 |
7 |
. |
|
|
|
||||
8 |
8 |
|
|||
д) Подільність на 7
Для формулювання ознаки подільності на 7 дослідимо послідовність остач від ділення степенів числа 10 на 7:
10 = 7 ×1+ 3, q1 = 1, r1 = 3;
102 = 100 = 7 ×14 + 2, q |
2 |
= 14, |
r = 2; |
|
|
2 |
10
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
