Пусть нам расширенный алгоритм не извнстен, но мы можем вычислить НОД(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.
Добрый день. Меня заинтересовал ваш ответ "Пусть нам расширенный алгоритм не извнстен, но мы можем вычислить НОД(3220,79)=1 путем цепочки неско..." на вопрос http://www.liveexpert.org/topic/view/70626-. Можно с вами обсудить этот ответ?