§ 4. Алгоритъм на Евклид
Алгоритъмът на Евклид се използва в много аритметични задачи. Нека първо проучим приложението му за намиране на най-голям общ делител на ненулеви целиa, b. Помислете сега за следната процедура за деление на цели числа с остатък, която се наричаалгоритъм на Евклид:
който не може да намалява безкрайно. Следователно, след не повече отb – 1стъпки – за някоиs– получаваме нулев остатък и
И така, заr00последният делител в Евклидовия алгоритъм (или последният ненулев остатък, ако броят на стъпките е по-голям от нула) е равен наgcd(a,b). Така доказахме следното.
Теорема (относно намирането наgcd(a, b)с помощта на евклидовия алгоритъм).За всички ненулеви цели числа a, b, техният най-голям общ делител gcd(a, b) може да бъде намерен с помощта на евклидовия алгоритъм в не повече от min(a, b) – 1 стъпки и е равен на последния делител в този алгоритъм (или последния ненулев остатък, ако броят на стъпките е по-голям от нула).
Следствие 1 (при линейно разширениеGCD (A, B)).Най-големият общ дивизатор GCD (a, b) на всякакви ненулеви цели A, B може да бъде представен като линейна комбинация от числа A и B с Coeger Coefficients X и Y: GCD (A A B) с B с B. Такова представяне се нарича линейно разширение на най-големия общ делител на числата a и b.