Решение. Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r1 = 26 и r2 = 11

Пример

Решение

Мы используем таблицу, аналогичную одной из тех, которые мы уже применяли прежде при данных r₁ = 26 и r₂ = 11. Нас интересует только значение t.

q	r1	r2	r	t1	t2	t
						-2
					-2
				-2		-7
					-7
				-7

НОД (26, 11) = 1, что означает, что мультипликативная инверсия 11 существует. Расширенный алгоритм Евклида дает t₁ = (–7).

Мультипликативная инверсия равна (–7) mod 26 = 19. Другими словами, 11 и 19 — мультипликативная инверсия в Z₁₉. Мы можем видеть, что .

Найти мультипликативную инверсию 23 в Z₁₀₀.

Мы используем таблицу, подобную той, которую применяли до этого при r₁ = 100 и r₂ = 23. Нас интересует только значение t.

q	r1	r2	r	t1	t2	t
						-4
					-4
				-4		-13
					-13

НОД (100, 23) — 1, что означает, что инверсия 23 существует. Расширенный Евклидов алгоритм дает t₁ =-13. Инверсия — (–13) mod 100 = 87. Другими словами, 13 и 87 — мультипликативные инверсии в Z₁₀₀. Мы можем видеть, что .

Дата добавления: 2014-01-03