§2.Нод(а, b), hok(a, b). Алгоритм Евклида.

Определение 1. Целое число dZ, (d¹0) называется общим делителем чисел a₁,а₂,..a_k, если каждое a_i(i=1,2,..., к) делится на d.

Определение 2. Целое число dZ, (d¹0) называется наибольшим общим делителем чисел a₁,а₂,... ,а_к если:

1 d - общий делитель всех а_i

2. d - делится на любой другой общий делитель этих чисел

Обозначение: НО Д (a₁ ,а₂,. . a_k)= d или (а₁ ,а₂,…,a_k) = d

Пример 1. Даны числа: 4, 8, 12, 16, 20, 24, 48

Числа 2 и 4 являются общими делителями этих чисел Число 4 является наибольшим общим делителем данных чисел, т е НОД (4, 8, 12, 16, 20, 24, 48) = 4

Задача 1. Доказать, что d = (a, b) определяется однозначно с точностью до знака.

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

Пусть d₁ = (a, b) & d₂ = (a, b) => (d₁ / d₂)&(d₂ / d₁) => [(d₁ = d₂) v (d₁ = -d₂)].

Замечание 1. Обычно берется положительное значение d = (a,b).

Существует метод, который позволяет доказать существование НОД (а, b) и находить его для любой пары целых чисел, его называют алгоритмом Евклида. Он основан на двух леммах:

Лемма 1. Если (а /b), то (a,b)=b.

Лемма 2. Если а = bq + г, где а, b, r  0, то (а, b) = (b, r).

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

1 Шаг. Делим а на (b¹0), если а /b, то (a, b) = b по лемме 1, если а = bq₀ + r₁, то (a, b)=(b, r₁)

2 Шаг. Делим b на r₁ если (b /r₁) => (b, r₁) = r₁, если b = r₁q₁+r₂, то (b, r₁) = (r₁, r₂).

3 Шаг. Делим r₁ на r₂ и т. д.

Поскольку остатки, получаемые в процессе деления, убывают и являются натуральными числами, то на каком-то шаге получим остаток, равный нулю, т.е. r_n-1 = r_nq_n и тогда (r_n-1, r_n) = r_n.

Задача 2. Доказать, что последний неравный нулю остаток в алгоритме Евклида является наибольшим общим делителем чисел (а) и (b).

Решение: Применим к числам (а) и (b) алгоритм Евклида:

a = bq_o+r₁ 0r₁<b

b = r₁q₁ + r₂ 0 r₂ <r₁

. . . . . . . . . . . . . . . . . . . . .

r_n-2=r_n-1•q_n-1 +r_n 0r_n<r_n-1

r_n-1 =r_nq_n + 0

Из первого равенства по лемме 2 будем иметь:

(a, b) = (b, r₁)

Из второго равенства алгоритма Евклида тоже по лемме 2 будем иметь (b, r₁) = (r₁ г₂) и т. д.

Из последнего равенства (r_n-1 , r_n) = r_n по лемме 1. Т.е. получили цепочку равенств (а, b) = (b, r₁) = (r₁, r₂) = (r₂, r₃) = …..

=(r_n-2, r_n-1) = (r_n-1, r_n) = r_n

Итак, (а, b)=r_n.

Пример 2. Найти d = (3220,1550) с помощью алгоритма Евклида

Решение:

Итак, (3220, 1550) = 10 = r₂

Задача 3. Доказать, что если d=(а,b), то х, уZ :

d = ах + by.

Решение:

Применим к числам а и b алгоритм Евклида:

а = bq₀ + r₁

b = r₁ q₁ + r₂

r_i = r₂q₂ + r₃

_{……………………}

r_n-3 = r_n-2q_n-2 + r_n-1

r_n-2 = r_n-1q_n + d, (d = r_n)

Тогда, последовательно выражая, из последнего равенства, d = r_n-2 - r_n-1 q_n (*) из предпоследнего r_n-1 = r_n-3 – r_n-2q_n-2 и т.д.

Из первого r₁ = а-bq_o и последовательно подставляя их в равенство (*) получаем: d = ах + by.