Решение
Пример
Решение
Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных 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. Мы можем видеть, что .