Для нахождения наибольшего общего делителя (НОД) двух чисел можно использовать алгоритм Евклида. Начнем с вычисления НОД(252, 198).

Алгоритм Евклида заключается в том, что мы вычитаем меньшее число из большего, пока одно из них не станет равным нулю. Однако более эффективно применять модульное деление.

Найдем остаток от деления 252 на 198:
[
252 = 198 \cdot 1 + 54
]
(остаток 54)

Теперь применим алгоритм к числам 198 и 54:
[
198 = 54 \cdot 3 + 36
]
(остаток 36)

Далее продолжим с числами 54 и 36:
[
54 = 36 \cdot 1 + 18
]
(остаток 18)

Продолжим с числами 36 и 18:
[
36 = 18 \cdot 2 + 0
]
Когда остаток стал равен 0, значит, последнее ненулевое значение (18) и есть НОД.

Таким образом, НОД(252, 198) = 18.

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

Расширенный алгоритм Евклида не только находит НОД двух чисел, но и может предоставить коэффициенты (x) и (y), такие что:
[
ax + by = \text{НОД}(a, b)
]
Для нахождения обратного элемента по модулю (m), если (a) и (m) являются взаимно простыми (т.е. НОД(a, m) = 1), то можно найти такие (x) и (y), что:
[
ax + my = 1
]
В данном случае (x) будет являться обратным элементом к (a) по модулю (m).

Таким образом, чтобы найти обратное число к (a) по модулю (m), необходимо выполнить расширенный алгоритм Евклида для чисел (a) и (m). Получив решение, мы можем взять (x) (если оно отрицательное, то добавим (m), чтобы получить положительный остаток) — это и будет искомое обратное число.

Например, если мы сейчас рассматриваем, что нам нужно найти обратное число к (a = 3) по модулю (m = 11):

Применяем расширенный алгоритм Евклида:
[
11 = 3 \cdot 3 + 2
]
[
3 = 2 \cdot 1 + 1
]
[
2 = 1 \cdot 2 + 0
]
Теперь мы можем выразить 1 в виде линейной комбинации 11 и 3:
[
1 = 3 - 1 \cdot 2
]
Подставим 2:
[
2 = 11 - 3 \cdot 3
]
Следовательно:
[
1 = 3 - 1 \cdot (11 - 3 \cdot 3) = 4 \cdot 3 - 1 \cdot 11
]
Таким образом, коэффициент для 3 равен 4, что означает, что (4) является обратным числом к (3) по модулю (11).

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