Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.06.2024
Просмотров: 52
Скачиваний: 0
ЗАВДАННЯ 2
Використовуючи третю властивість НСД, знайти НСД трьох чисел.
1. |
529, 1541, 1817. |
|
|
2. |
67 283, 122 |
433, 221 703. |
|||||
3. |
549 493, 863 |
489, |
2 |
133 125. |
4. |
738089, 3 082607, 28 303 937. |
|||||
5. |
1767, 2223, 11 |
913. |
|
6. |
476, 1258, 21 114. |
||||||
7. |
3445, 4225, 5915. |
|
|
8. |
572, 5746, 1118. |
||||||
9. |
19 074, 13 566, 8211. |
10. |
1073, 3683, 34 481. |
||||||||
11. |
1012, 1474, |
4598. |
|
12. |
988, 2014, |
42 |
598. |
||||
13. |
2585, 7975, |
13 915. |
14. |
874, 1518, |
20 |
142. |
|||||
15. |
2227, 9911, |
952. |
|
|
16. |
1253, 252, |
406. |
||||
17. |
2743, 3587, |
6963. |
|
18. |
4345, 6523, 10967. |
||||||
19. |
7683, 5161, |
12 909. |
20. |
5174, 12 337, |
13 403. |
||||||
21. |
10 047, 6749, |
16 |
881. |
22. |
6766, 16 133, |
17 527. |
|||||
23. |
11 229, 7543, |
18 |
867. |
24. |
7562, 18 031, |
19 589. |
|||||
25. |
13 593, 9131, |
22 |
839. |
26. |
9154, 21 827, |
23 713. |
|||||
27. |
17 139, 11 513, 28 |
797. |
28. |
11 542, 27 |
521, 29 899. |
||||||
29. |
18 321, 12 307, 30 |
783. |
30. |
12 338, 29 |
419, 31 961. |
||||||
22
ЗАВДАННЯ 3
Використовуючи ознаки подільності чисел, дослідити, чи ділиться число a на число m .
|
m=35. |
m=39. |
m=55. |
|||
|
|
|
|
|
|
|
1. |
|
a=351645 |
6. |
a=437931 |
11. |
a=747615 |
|
|
|||||
|
|
|
|
|
|
|
2. |
|
a=236215 |
7. |
a=294177 |
12. |
a=502205 |
|
|
|||||
|
|
|
|
|
|
|
3. |
|
a=590835 |
8. |
a=735813 |
13. |
a=1256145 |
|
|
|||||
|
|
|
|
|
|
|
4. |
|
a=236810 |
9. |
a=294918 |
14. |
a=503470 |
|
|
|||||
|
|
|
|
|
|
|
5. |
|
a=564655 |
10. |
a=703209 |
15. |
a=1200485 |
|
|
|||||
|
|
|
|
|
|
|
|
m=31. |
m=91. |
m=29. |
|||
|
|
|
|
|
|
|
16. |
|
a=238173 |
21. |
a=1559649 |
26. |
a=394197 |
|
|
|||||
|
|
|
|
|
|
|
17. |
|
a=159991 |
22. |
a=1047683 |
27. |
a=264799 |
|
|
|||||
|
|
|
|
|
|
|
18. |
|
a=400179 |
23. |
a=2620527 |
28. |
a=662331 |
|
|
|||||
|
|
|
|
|
|
|
19. |
|
a=160394 |
24. |
a=1050322 |
29. |
a=265466 |
|
|
|||||
|
|
|
|
|
|
|
20. |
|
a=382447 |
25. |
a=2504411 |
30. |
a=632983 |
|
|
|||||
|
|
|
|
|
|
|
23
ЗАВДАННЯ 4
Раціональне число a / b задане ланцюжком неповних часток. Побудувати відповідне найменше раціональне число a / b і знайти розв’язок рівняння ax + by = 1
|
|
|
a |
= [2,1,3,4,1,2] |
|
|
|
a |
= [2,1,1,6 ,8] |
|
|
|
|
a |
= [0,3,1,2,7 ,1] |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
1. |
|
b |
|
|
|
|
|
. |
2. |
|
b |
. |
3. |
|
b |
. |
|||||||||||||||||
|
|
|
a |
= [1,1,2,4,5] |
|
|
|
|
a |
= [0,3,4,3,2,3] |
|
|
|
a |
= [3,1,1,1,5] |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
4. |
|
b |
|
|
|
|
|
. |
5. |
|
b |
. |
6. |
|
b |
. |
|||||||||||||||||
|
|
|
a |
= [2,1,3,4,2,9] |
|
|
|
a |
= [13,1,4,2,5] |
|
|
|
a |
= [0,4,1,3,2,5] |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
7. |
|
b |
|
|
|
|
|
. |
8. |
|
b |
. |
9. |
|
b |
. |
|||||||||||||||||
|
|
|
|
|
a |
= [22,3,1,4,7] |
|
|
|
|
|
a |
= [2,1,30,2,3] |
|
|
|
|
|
a |
= [1,24,3,4,5] |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
10. |
|
b |
. |
11. b |
. |
12. b |
. |
||||||||||||||||||||||||||
|
|
|
|
a |
= [1,25,1,2,3,1,1] |
|
|
|
|
a |
= [11,2,3,5,1,1] |
|
|
|
|
a |
= [31,5,2,3,1,5] |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
13. b |
. |
14. b |
. |
15. b |
. |
||||||||||||||||||||||||||||
16. |
|
|
|
|
|
|
|
17. |
|
|
|
|
|
|
|
|
|
|
a |
= [2,8,1,2,3,1,2] |
|||||||||||||
|
a |
= [1,25,1,2,3,1,1] |
|
a |
= [1,13,1,2,5,1,1] |
|
|
|
|
|
|||||||||||||||||||||||
|
|
18. b |
|
||||||||||||||||||||||||||||||
|
|
|
|
||||||||||||||||||||||||||||||
|
b |
|
|
|
|
|
|
|
. |
|
b |
|
|
|
|
|
|
. |
. |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
a |
= [2,7 ,2,1,1,1,4] |
|
|
|
|
a |
= [3,7 ,2,5,1,1,2] |
|
|
|
|
|
a |
= [2,41,2,3,1] |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
19. |
|
b |
. |
20. b |
|
21. b |
. |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
= [2,17 ,1,5,1] |
|
|
|
|
|
a |
= [3,19,1,1,3] |
|
|
|
|
a |
= [2,1,1,3,5,1,1] |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
22. |
|
b |
. |
23. b |
. |
24. b |
. |
||||||||||||||||||||||||||
25. |
|
|
|
|
|
|
|
26. |
|
|
|
|
|
|
27. |
|
|
|
|
|
|
|
|
|
|||||||||
|
a |
= [2,11,3,19,1,1,3] |
|
a |
= [5,9,3,11,1,1,2] |
|
a |
= [21,1,3,7 ,1,1,3] |
|||||||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||||||||
|
b |
|
|
|
|
|
|
|
. |
|
b |
|
|
|
|
|
|
. |
|
b |
|
|
|
|
|
|
|
|
|
. |
|||
|
|
|
|
a |
= [2,23,1,2,3,1,2] |
|
|
|
|
a |
= [3,29,1,1,2,2] |
30. |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
a |
= [1,47 ,1,1,2,1,2] |
|||||||||||||||||||||
28. b |
|
29. b |
|
. |
|||||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||||||
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b |
|
|
|
|
|
|
|
|
|
. |
||
24
ТЕМА 2. НАЙВАЖЛИВІШІ ФУНКЦІЇ В ТЕОРІЇ ЧИСЕЛ
2.1.Функції виділення цілої та дробової частини дійсного
числа.
2.2.Мультиплікативні функції.
2.3.Приклади мультиплікативних функцій.
Ключові терміни
Функція виділення цілої частини, функція виділення дробової частини, мультиплікативні функції, кількість дільників, сума додатних дільників, функція Ейлера.
2.1. ФУНКЦІЇ ВИДІЛЕННЯ ЦІЛОЇ ТА ДРООСКІЛЬКИВОЇ ЧАСТИНИ ДІЙСНОГО ЧИСЛА
1. Функція виділення цілої частини дійсного числа x повертає найбільше ціле число, яке не перевищує x :
[ x] = N; x = N + q; N Z; 0 < q < 1 .
Приклади |
|
|
|
[− 100] = −100; |
[45,9] = 45; [− 5,1] = −6 . |
|
|
2. Функція виділення дрооскількивої частини дійсного |
|||
числа x повертає різницю між числом |
x |
та його цілою |
|
частиною [ x] : |
|
|
|
{x} = x − [x] = q; |
0 < q < 1 . |
|
|
Приклади |
|
|
|
{− 100} = 0; {45,9} = 0,9; {− 5,1} = 0,9 . |
|
|
|
Приклад застосування функції виділення цілої частини |
|||
Визначити степінь α простого числа |
p , |
з яким це число |
|
входить до числа n!. |
|
|
|
25
Розв’язання |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
||
У числі |
n! множників, які кратні |
p , |
буде |
|
. Серед них |
|||||||||||||
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
кратних p 2 , |
|
|
|
|
|
n |
|
|
|
|
доки pk £ n , |
||||
множників, |
буде |
|
|
|
, |
і т. |
д. доти, |
|||||||||||
|
2 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|
а pk +1 > n . Отже, загальна кількість входжень p до n! буде |
||||||||||||||||||
n |
|
n |
|
|
n |
|
|
|
|
|
|
|
|
|||||
a = |
|
|
+ |
|
|
+ ... + |
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
2 |
|
k |
|
|
|
|
|
|
|
|
||||||
p |
p |
|
|
p |
|
|
|
|
|
|
|
|
|
|
||||
Приклад
Знайти з яким степенем число p = 2 входить до числа 11!
Розв’язання
a = |
11 |
|
+ |
11 |
|
+ |
11 |
|
= 5 + 2 +1 = 8 . |
|
|
|
|||||||
2 |
4 |
8 |
|
||||||
Дійсно, 11! = 1× 2 ×3× 4 ×5 ×6 ×7 ×8 ×9 ×10 ×11 =
= 1× 21 ×3× 22 ×5 ×(21 ×3)×7 × 23 ×9 ×(21 ×5)×11 .
Порахувавши усі степені 2, побачимо, що 2 входить у число 11! дійсно у степені 1 + 2 +1 + 3 +1 = 8 .
2.2. МУЛЬТИПЛІКАТИВНІ ФУНКЦІЇ
Функція f (a) називається мультиплікативною, якщо для неї виконуються 2 умови:
1. f (a) визначена для усіх a = 0,1,2... і хоча б для одного a0 f (a0 ) = 0 ;
2. Для будь-яких a1 , a2 : (a1 , a2 ) = 1 виконується таке: f (a1 × a2 ) = f (a1 )× f (a2 )
26
