Наибольший общий делитель (НОД). Алгоритм Евклида

Определение. Целое число D называется общим делителем (ОД) целых чисел a и b, если каждое из этих чисел делится на D.

Целое число d называется наибольшим общим делителем целых чисел a и b, если 1) d - ОД этих чисел; 2) d делится на любой ОД чисел a и b.

Обозначение. Натуральный НОД целых чисел a и b обозначим через (a, b).

Теорема 3.1 (Об определяющих свойствах НОД). Пусть - целые числа. Тогда 1)Если НОД двух целых чисел существует, то он определён с точностью до знака.

2)Если a⋮b и b >0, то(a, b)= b. Если a⋮b и b≠0, то (a,b)=| b |.

3)Если a = b∙c+d и a,b,c,d – целые числа, b≠0, то (a, b)=(b, d).

4)Если хотя бы одно из целых чисел a или b не равно 0, то их НОД существует.

Замечания. 1) Пара имеет единственный наибольший общий делитель целое число 0, удовлетворяющее всем свойствам НОД. 2) В школьном курсе математики понятие НОД обычно рассматривается только для натуральных чисел.

Алгоритм Евклида или метод последовательного деления с остатком. Пусть a и b –ненулевые целые числа. Делим a на b с остатком r₁. Если r₁≠0, то делим b с остатком r₂ на r₁. Если r₂≠0, то делим r₁ на r₂ с остатком r₃ и т.д. до тех пор, пока очередной остаток r_n+1 не станет равным нулю:

a=b∙q₀+r₁, где q₀, r₁ - целые числа и 0<r₁ <| b |,

b=r₁∙q₁+r₂, где q₁, r₂ - целые числа и 0<r₂<r₁,

………………

r_n-2=r_n-1∙q_n-1+r_n, где q_n-1, r_n - целые числа и 0<r_n<r_n-1,

r_n-1=r_n∙q_n+0, где q_n - целое число.

Теорема 4.1. Последний ненулевой остаток в алгоритме Евклида для целых ненулевых чисел a и b равен их наибольшему натуральному делителю (a, b).

Следствие. Для любых целых чисел a и b существуют целые числа x и y такие, что a∙x+b∙y=(a,b) (линейное выражение наибольшего общего делителя двух целых чисел через эти числа).

Пример 2. Найти наибольший общий делитель чисел a =1134 и b =768 и линейное выражение их НОД.

Применим к числам 1134 и 768 алгоритм Евклида.

1134=768∙1+366: a=b∙q₀+r₁; q₀=1, r₁=366.

768=366∙2+36: b=r₁∙q₁+r₂; q₁=2, r₂=36.

366=36∙10+6: r₁=r₂∙q₂+r₃; q₂=10, r₃=6.

36=6∙6+0: r₂=r₃∙q₃+0; q₃=6, r₄=0.

Итак, r₄=0, а т.к. r₃=6≠0, то (1134,768)=(a,b)=6.

Теперь из предпоследнего равенства выражаем r₃: r₃=r₁-r₂ ∙ q₂ или r₃=r₁-r₂∙10. Далее из следующего вверх равенства выражаем r₂, подставляем в полученное ранее равенство и т.д.: r₃=r₁-r₂∙10=r₁-(b-r₁∙2)∙10=21∙r₁-10∙b=21∙(a-b∙1)-10∙b=21∙a+(-31)∙b. (a,b)=6=21∙a+(-31)∙b.