Расширенный алгоритм Евклида.

 

С помощью алгоритма Евклида, вычисляя НОД, можно выяснить , обратимо ли число по модулю . Однако встает вопрос, как найти обратный к элемент. Так как алгоритм Евклида – это последовательное деление с остатком , , где , и НОД. Можно выразить все остатки от деления через и . Расширенный алгоритм Евклида позволяет найти НОДчерез сами эти числа.

Теперь найдем обратный элемент для по модулю . Применим сначала расширенный алгоритм Евклида к числам и и получим такие числа , и такие, что . Поэтому . Теперь видно, что уравнение имеет решение только тогда, когда . При этом решение имеет вид .

Пример. Найти обратный элемент к 7 по модулю 19.

Решение. Пусть , . Тогда , , или или . Отсюда .