Расширенный алгоритм Евклида и mod - вопрос №70626

Пусть нам расширенный алгоритм не извнстен, но мы можем вычислить НОД(3220,79)=1 путем цепочки нескольких делений

3220=79*40+60

79=60*1+19

60=19*3+3

19=3*6+1,

составляющей алгоритм Евклида.

Но мы знаем, что тогда должно существовать равенство

1=3220*u+79*v

Если по этой цепочке подниматься снизу вверх, начиная с последнего деления

1=19-3*6,

и заменяя остатки 3, 19, 60 соотношениями последовательно

3=60-19*3,

19=79-60,

60=3220-79*40,

то в силу линейности всех соотношений  получается равенство

1=3220*(-25)+79*1019.

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

Из полученного равенства следует сравнение

1=79*1019(mod 3220).

Из сравнения следует требуемое решение

d= 1019. 

Вычисления можно сократить, если в первой цепочке делений в качестве остатков выбирать абсолютно наименьшие значения, т.е. первую цепочку делений заменить следующей

3220=79*41-19,

79=19*4+3,

19=3*6+1.

Тогда первая подстановка

1=19-3*6=19-(79-19*4)*6=19-79*6+19*24=19*25-79*6

и вторая

1=(79*41-3220)*25-79*6=3220*(-25)+79*(41*25-6)

снова приводит к одному и тому же результату

1=3220*(-25)+79*1019.