Свойства НОД

1. Если a⁞b, то (a, b) = |b |. Действительно, - натуральный общий делитель а и b, который делится на любой их общий делитель (так как на него делится b).

2. НОД двух чисел линейно выражается через эти числа. То есть если (a, b)=d, то существуют u, v €Z, что d=аu + bv (линейная форма НОД).

Доказательство. Из первого равенства алгоритма Евклида . Подставив вместо это выражение во второе равенство, получим: Подставив вместо полученные выражения в третье равенство, выразим через а и b. Продолжая так дальше, получим выражение = (a,b) через а и b.

Заметим, что можно было получить это выражение, начиная с конца алгоритма. Из предпоследнего равенства . Последовательно двигаясь снизу вверх, выражаем через предыдущие остатки, пока ни получим выражение его через а и b.

Примеры. Найдём НОД чисел а и b и выразим его линейно через эти числа. 1) а = 1173, b = 323; а = b *3 + , =204; b = , =119;

Итак, (a, b)= d = 17. Выразим его линейно через а и b. Из первого равенства . Подставив в равенство для b, находим . Далее:

2)

НОД чисел а и b равен 23. 23 = 1058-345*3 = 1058-(l 403-1058)*3 =-3*1403 + +4*1058 = -За + 4 b.

3. Если (а,b)= d, n€N, то (na;nb)= nd.

Верность утверждения следует из алгоритма Евклида для чисел а и b, если каждую строчку его умножить на n.

4. Если (a,b)=d, а⁞n, b⁞n, n€N, то . Для доказательства

достаточно каждую строчку алгоритма Евклида для чисел а и b разделить на n. В частности, .

5.

Доказательство. Пусть

делятся на . Следовательно, и поэтому их НОД .

Так как делятся и на и их наибольший общий делитель )= . Получили, что .

6. Наибольший общий делитель чисел , где не все , равны нулю, существует, и единственный.

Существование следует из теоремы о последнем, не равном нулю остатке в алгоритме Евклида и свойства 5. Единственность - из определения НОД и свойства 6 делимости чисел.