Учеба и наука

• Всего ответов: 1


Владимир Чепурных
30-й в Учебе и науке
4.9 26 отзывов
Пусть нам расширенный алгоритм не извнстен, но мы можем вычислить НОД(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.
май 2, 2011 г.
Ответ понравился автору
Лучший ответ по мнению автора