Задача 3
Вычислить 43/65 в кольце вычетов по модулю 71.
Решение
Требуется решить сравнение
.
(2)
Это эквивалентно диофантову уравнению
Применим обобщенный алгоритм Евклида для чисел 65 и 71 (табл.1)
Получили
Это означает
Таким образом, число -12 является решением сравнения
(3)
Но
тогда и
является решением этого сравнения
(4)
Чтобы получить решение сравнения (2) надо (4) умножить на 46
Вычислим
остаток от деления числа
на 71:
Таблица 1
s |
65 |
71 |
65 |
6 |
5 |
1 |
0 |
r |
65 |
71 |
65 |
6 |
5 |
1 |
0 |
q |
|
|
0 |
1 |
10 |
1 |
5 |
x |
1 |
0 |
1 |
-1 |
11 |
-12 |
71 |
y |
0 |
1 |
0 |
1 |
-10 |
11 |
-65 |
Это
означает
,
что и требовалось.
Ответ: 16.
Задача 4
Найти
наименьшее натуральное число
,
удовлетворяющее сравнениям
Решение
Вычислим числа
Решим сравнение
s |
323 |
24 |
11 |
2 |
1 |
0 |
r |
323 |
24 |
11 |
2 |
1 |
0 |
q |
|
|
13 |
2 |
5 |
2 |
x |
1 |
0 |
1 |
-2 |
11 |
-24 |
y |
0 |
1 |
-13 |
27 |
-148 |
323 |
Получили
.
Решим сравнение
s |
456 |
17 |
14 |
3 |
2 |
1 |
0 |
r |
456 |
17 |
14 |
3 |
2 |
1 |
0 |
q |
|
|
26 |
1 |
4 |
1 |
2 |
x |
1 |
0 |
1 |
-1 |
5 |
-6 |
17 |
y |
0 |
1 |
-26 |
27 |
-134 |
161 |
-456 |
Получили
.
Решим сравнение
s |
408 |
19 |
9 |
1 |
0 |
r |
408 |
19 |
9 |
1 |
0 |
q |
|
|
21 |
2 |
9 |
x |
1 |
0 |
1 |
-2 |
19 |
y |
0 |
1 |
-21 |
43 |
-408 |
Получили
Вычислим число
Ответом
является остаток от деления этого числа
на сводный модуль
.
Вычисляем
остаток
Ответ: 2463.