Пример 6.2

.

3. С помощью алгоритма Евклида.

Алгоритм Евклида применяется для нахождения НОД чисел и . Однако его расширенный вариант можно использовать и для вычисления обратной величины.

Основной вариант.

Даны и , . Алгоритм имеет итерационный характер:

, ;

, ;

, ;

, ;

, ;

,

где , ‑ частное и остаток на ‑м шаге алгоритма. На первом шаге делимое ‑ , делитель ‑ , частное ‑ , остаток ‑ . На ‑м, шаге алгоритма: делимое ‑ делитель ‑го шага, делитель ‑ остаток ‑го шага (), частное ‑ , остаток ‑ .

Пример 6.3. Пусть и . Найти .

То есть на четвертом шаге остаток от деления , следовательно, алгоритм останавливается и .

Доказано, что при неотрицательных и можно найти такие целые числа: , , , что будет выполняться

.

Если выбрать и ‑ взаимно простые числа, т.е. , тогда

,

,

.

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

, .

Алгоритм вычисления имеет следующий вид

1. Начальные установки:

, т.е. , , . При этом , т.е. ,

, т.е. , , . При этом .

2. Проверяем, выполняется ли , если да, то алгоритм заканчивается.

3. Делим на ( на ) и определяем:

и значения векторов: ; .

4. Вернуться к шагу 2.

На каждом шаге при расчетах используются результаты предыдущего:

, , .

При вычисления заканчиваются , где значение , полученное на последнем шаге.

Пример 6.4. Пусть и . Найти число , обратное числу по модулю , т.е. найти .

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

-
				-4
	-4				-1
		-1		-9
-	-9

При , , выполняется уравнение , и .

Итак, .