Пример
Решение
Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r1 = 26 и r2 = 11. Нас интересует только значение t.
q
| r1
| r2
| r
| t1
| t2
| t
|
|
|
|
|
|
| -2
|
|
|
|
|
| -2
|
|
|
|
|
| -2
|
| -7
|
|
|
|
|
| -7
|
|
|
|
| | -7
|
| |
НОД (26, 11) = 1, что означает, что мультипликативная инверсия 11 существует. Расширенный алгоритм Евклида дает t1 = (–7).
Мультипликативная инверсия равна (–7) mod 26 = 19. Другими словами, 11 и 19 — мультипликативная инверсия в Z19. Мы можем видеть, что
.
Найти мультипликативную инверсию 23 в Z100.
Мы используем таблицу, подобную той, которую применяли до этого при r1 = 100 и r2 = 23. Нас интересует только значение t.
q
| r1
| r2
| r
| t1
| t2
| t
|
|
|
|
|
|
| -4
|
|
|
|
|
| -4
|
|
|
|
|
| -4
|
| -13
|
|
|
|
|
| -13
|
|
|
|
| |
|
| |
НОД (100, 23) — 1, что означает, что инверсия 23 существует. Расширенный Евклидов алгоритм дает t1 =-13. Инверсия — (–13) mod 100 = 87. Другими словами, 13 и 87 — мультипликативные инверсии в Z100. Мы можем видеть, что
.