Материал: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi
цих чисел. Найменше з чисел, кратних поданому набору чисел,
називається їх найменшим спільним кратним (НСК).
Позначення НСК
m = [a1 , a2 ,..., am ] .
|
|
Нехай |
(a, b) = d , |
|
|
тоді |
|
|
a = a1d , |
b = b1d |
і |
(a1 , b1 ) = 1 |
|||||||||||||
(властивості НСД, 2) Нехай |
M |
- |
|
деяке кратне a та b , тобто |
|||||||||||||||||||||
|
M = ka |
і |
M |
= |
ka |
= |
ka1d |
= |
ka1 |
Î Z . Оскільки |
(a , b ) = 1, то k |
||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
b b b1d |
|
|
|
b1 |
|
|
|
|
|
1 |
1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
повинно ділитися на b1 , |
|
тобто k = b1t . |
Для СК буде правильна |
||||||||||||||||||||||
формула |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
M = ka = ak = ab1t = |
ab1d |
= |
a ×b |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
t |
|
|
|
t . |
|
|
|
|
|||||||||
|
|
|
|
d |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
d |
|
|
|
|
|
|
|
|
|||||
|
|
Найменше значення СК буде за умови, що t = 1, |
тобто для |
||||||||||||||||||||||
НСК виконується формула |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
[a, b] = m = |
|
ab |
, |
|
|
(1) |
||||||||
|
|
|
|
|
|
|
|
|
|
|
(a, b) |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
тоді M = m ×t . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Приклад 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
Знайти d = (648, 261) |
|
та |
m = [648, 261] . |
|
|
|
|||||||||||||||||
Розв’язання |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
1. Шукаємо НСД: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
648 |
: |
648 = 261× 2 +126, |
|
|
|
a = bq |
+ r , r = 126, 0 < 126 < 261; |
|||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||
261 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
261 |
: 261 = 126 × 2 + 9, |
|
|
|
b = r q + r r = 9, |
0 < 9 < 126; |
||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||
126 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
2 |
2 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
126 |
: |
126 |
= 9 ×14 + 0, r = |
0 / |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
9 |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Остання ненульова остача r2 = 9 .
6
Отже, d = (648, 261) = 9 .
2. m = [648, 261] знайдемо, використавши формулу (1),
= [ ] = 648 × 261 = 169128 =
m 648, 261 18792 .
d |
9 |
Відповідь: d = (648, 261) = 9, m = [648, 261] = 18792 .
Приклад 2
Знайти d = (420,126, 525) .
Розв’язання
Для знаходження найбільшого спільного дільника трьох чисел використаємо властивість 3.
а) Найменшим з чисел 420, 126 і 525 є число 126. Ділимо два інших числа на 126 і визначаємо остачу від ділення:
|
420 |
= 3×126 + 42; |
r = 42 < 126 ; |
|
|
|
|||
126 |
|
|
1 |
|
|
|
|
||
|
525 |
= 4 ×126 + 29; |
r = 29 < 126. |
|
|
||||
126 |
|
|
2 |
|
|
|
|
||
б) За властивістю 3 (525, 420, 126) = (126, 42, 29) .
Найменше число – 29.
126 = 4 × 29 +10 ;
29
42 = 1× 29 +13.
29 в) За властивістю 3 (525, 420, 126) = (126, 42, 29) = (29,13,10) .
Оскільки числа 29 і 13 – прості, то (29,13,10) =1. А це означає, що (525, 420, 126) =1 .
Відповідь: задані числа є взаємно простими.
7
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