Алгоритм Евклида

Алгоритм Евклида применяется для нахождения НОД, а так же для вывода его важнейших свойств. Он состоит в следующем. Пусть a и b – натуральные числа, причем a > b. Запишем ряд равенств

, ,

, ,

, ,

………………………………..…… (1)

, ,

,

заканчивающийся, когда получится некоторое . Последнее неизбежно, так как числа целые положительные и убывают, значит этих чисел не более чем b штук. Рассматривая равенства (1), идя сверху вниз, убеждаемся что общие делители a и b одинаковы с общими делителями чисел b и далее одинаковы с общими делителями чисел и , чисел и ,…, чисел и , наконец с делителями одного числа , являющегося последним не равным нулю остатком алгоритма Евклида. Одновременно с этим имеем (a,b) = (b, ) = ( , ) =…= ( , ) = . Мы приходим к следующим результатам

1. Совокупность общих делителей чисел a и b совпадает с совокупностью делителей их общего наибольшего делителя.

2. Этот наибольший общий делитель равен последнему, не равному 0 остатку алгоритма Евклида.