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