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

Озн. Нехай дано 2 числа а і b. Число D наз. НСД чисел а і b, якщо виконуються умови:

1) а D, b D, тобто це число є дільником а і b;

2) с маємо а с, b D, то D d ( інший спільний дільник є дільником даного числа)

Позначають НСД (а; b) або D = (а; b).

Приклад. Нехай а = 72, b = 48.

Виписуємо всі дільники числа 72:

Аналогічно всі дільники числа 48:

НСД (а; b) = 24.

Озн. Якщо НСД двох чисел = 1, то такі числа наз. взаємопрості.

Лема1. Якщо а b, то (а; b) = b.

Доведення. Якщо а b, b b, то b – спільний дільник а і b. Візьмемо довільний спільний дільник а і b – с. Очевидно, що b c, тому за означенням b є НСД а і b.

Лема 2. Якщо число а ділиться на b без остачі, тобто а = b·q + r, 0 ≤ r < ׀b׀, то (a, b) = (b, r).

Доведення. Нехай d – спільний дільник а і b, тоді а d, b d. За умовою а = b·q + r, а - b·q = r. Якщо зменшуване і від’ємник d, то і різниця r d. Тому спільний дільник а і b буде також і дільником r. Аналогічно, спільний дільник b і r буде також і дільником а і b. А це означає, що множина всіх дільників а і b співпадає з множиною всіх дільників b і r, а, отже, будуть співпадати і їх НСД.