НОД(а, 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).