Докато "нормално" Алгоритъм на Евклид просто намира най-големият общ делител на две числа и разширен Алгоритъм на Евклид е в допълнение към НОД и коефициентите и такива, че:
Т.е. той намира коефициентите, с което НОД на две числа се изразяват чрез тези номера.
Направете изчисление на тези коефициенти в алгоритъм на Евклид е проста, достатъчно, за да донесе формулата, по който те се променят от чифт за сдвояване (знак за процент ще означаваме като се остатъка от деление).
Така че, нека да се намери решение на проблема за новата двойка:
и ние искаме да се получи решение за нашите двойки:
За това ние се превърне стойност:
Заместването на тази в експресията с и получават дадените по-горе:
и извършване пренареждане на термини, получаваме:
Сравнявайки тази на оригиналния израз на неизвестното, и се получи необходимата израз:
изпълнение
Рекурсия база - случай. След GCD е и очевидно, желаното съотношение и равно на и съответно. В други случаи, обичайната разтвор се работи и коефициентите са преизчислени от горните формули.
Разширено Алгоритъм на Евклид в това изпълнение работи правилно дори и за отрицателни числа.
литература
Свързани статии