2. Найбільший спільний дільник. Алгоритм евкліда.

Означення: Ціле число d ≠ 0 називається спільним дільником цілих чисел а і b, якщо кожне з цих чисел ділиться на d.

Ціле число D називається найбільшим спільним дільником чисел а і b, якщо:

1) D — спільний дільник а і b;

2)  D — ділиться на будь-який спільний дільник а і b. Позначається D = (а, b) або НСД (а,b).

Два числа а і b називаються взаємнопростими, якщо (а,b)=1.

Теорема: Найбільший спільний дільник чисел а і b визначається однозначно з точністю до знаку.

Доведення: Нехай і — найбільші спільні дільники чисел а і b. Оскільки = (а,b), то він ділиться на будь-який інший дільник, тобто .Аналогічно . Згідно означення =∙c, тобто || ≥ ||і навпаки =∙c, тобто || ≥ ||.

З цих двох нерівностей випливає, що || = ||,тобто =або =-.

Приклад: Знайдемо НСД чисел а= 135 і b = -180. Множина всіх додатних дільників 135 має вигляд:

А= {1,3, 5,9, 15,27,45, 135},

а для числа 180:

В = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}.

Спільними дільниками є

А∩В= {1,3,5,9, 15,45}.

Отже число 45 є найбільшим спільним дільником цих чисел.

З цього прикладу видно, що шукати таким методом НСД незручно, особливо для великих чисел, найчастіше застосовують для цього спосіб, запропонований видатним давньогрецьким математиком Евклідом.

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

Для обґрунтування алгоритму Евкліда доведемо дві леми:

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

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

Лема 2. Якщо а=b∙q + r, де а, b і r відмінні від 0, то

(а, b) = (b, r).

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

Алгоритм Евкліда для знаходження НСД чисел а і Ь полягає у виконанні наступних дій:

♦   ділимо число а на b, якщо , то за лемою 1 (а;b) = b, якщо , то отримуємо остачу: а = +;

♦   ділимо b на , якщо ,то (b, ) = , і згідно з лемою 2 (а, b) = (b,) = , якщо , то маємо остачу : b = ∙+ ;

♦   ділимо на . І знову можливі два випадки: якщо , то (,) =(b,) = (а,b), або ділиться на з остачею і т. д.

Оскільки остачі, які отримуються в процесі ділення, є спадними натуральними числами, то на якомусь кроці ми отримаємо остачу, рівну 0, а остання, не рівна 0 остача, і буде найбільшим спільним дільником чисел а і b. Це твердження може бути сформульовано у вигляді теореми.

Теорема: Якщо

a = b∙+, 0 ≤ < b,

b = ∙+, 0 ≤ < ,

. . . . . .

= ∙+, 0 ≤ < ,

= ∙,

то (a,b) =

Доведення: На основі леми 2 отримуємо з першого рядка

(а,b) = (b, ), з другого: (b, )= (,) і т.д. Отже, (а,b) = (,). Але і на основі леми 1 (,)=, а тому (а,b) = .

Приклад: Знайдемо (2585, 7975).

Остання, відмінна від 0 остача 55, отже (2585, 7975) = 55.