2015-04-01
517
.
3. С помощью алгоритма Евклида.
Алгоритм Евклида применяется для нахождения НОД чисел 
и 
. Однако его расширенный вариант можно использовать и для вычисления обратной величины.
Основной вариант.
Даны и , 
. Алгоритм имеет итерационный характер:
, 
;
, 
;
, 
;
, 
;
, 
;
,
где 
, 
‑ частное и остаток на 
‑м шаге алгоритма. На первом шаге делимое ‑ , делитель ‑ , частное ‑ 
, остаток ‑ 
. На ‑м, 
шаге алгоритма: делимое ‑ делитель 
‑го шага, делитель ‑ остаток ‑го шага (
), частное ‑ , остаток ‑ .
Пример 6.3. Пусть 
и 
. Найти 
.
То есть на четвертом шаге остаток от деления 
, следовательно, алгоритм останавливается и 
.
Доказано, что при неотрицательных и можно найти такие целые числа: 
, 
, 
, что будет выполняться
.
Если выбрать 
и 
‑ взаимно простые числа, т.е. 
, тогда
,
,
.
То есть для нахождения обратной величины необходимо вычислить 
. Эта задача решается в ходе вычисления 
в соответствии с алгоритмом Евклида. Дополнительно на каждом шаге вычисляются координаты двух векторов:
|
|
|
, 
.
Алгоритм вычисления имеет следующий вид
1. Начальные установки:
, т.е. 
, 
, 
. При этом 
, т.е. ,
, т.е. 
, 
, 
. При этом 
.
2. Проверяем, выполняется ли 
, если да, то алгоритм заканчивается.
3. Делим 
на ( на 
) и определяем:
и значения векторов: 
; 
.
4. Вернуться к шагу 2.
На каждом шаге при расчетах используются результаты предыдущего:
, 
, 
.
При вычисления заканчиваются , где значение , полученное на последнем шаге.
Пример 6.4. Пусть 
и 
. Найти число 
, обратное числу по модулю , т.е. найти 
.
Используя расширенный алгоритм Евклида, выполним вычисления.
|
|
|
| 
| 
|
|
| - |
|
| ||||
| -4 | ||||||
| -4 | -1 | |||||
| -1 | -9 | |||||
| - | -9 |
При 
, 
, выполняется уравнение , 
и 
.
Итак, 
.
