Понятие НОД целых чисел

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

Определение 8.2. Целое число d Z (d 0) называется наибольшим общим делителем чисел a₁, a₂, …, a_k, если

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

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

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

Теорема 8.1. Наибольший общий делитель целых чисел а и b определяется однозначно с точностью до знака.

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

Пусть d₁ = (a, b) d₂ = (a, b) d₁ d₂ d₂ d₁ [(d₁ = d₂) (d₁ = – d₂)].

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

Пример. Даны числа: 9, 18, 27, 54. Числа 3 и 9 являются общими делителями этих чисел, т.е. НОД (9, 18, 27, 54) = 9.

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

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

Лемма 8.3. Если а = bq + r, где а, b, r отличны от 0, то (а, b) = (b, r).