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

Щоб знайти найбільший спільний дільник двох чисел, є дуже простий спосіб, відомий під назвою алгоритму Евкліда, або способу послідовного ділення.

Алгоритм Евкліда, або алгоритм послідовного ділення, полягає ось у чому. Нехай дано натуральні числа a і b, a > b.

Поділимо перше число на друге, дістанемо остачу r₁ (r₁ < b). Тепер b поділимо на r₁,дістанемо остачу r₂ (r₂ < r₁), далі поділимо r₁ на r₂ і т. д.

Оскільки після кожного наступного кроку утворюється остача, менша від попередньої, то через скінченну кількість кроків дістанемо остачу, яка дорівнює нулю: ділення відбудеться націло і процес припиниться.

Остання відмінна від нуля остача r_k, на яку націло ділиться остача r_k-1, буде найбільшим спільним дільником чисел a і b.

Справді, запишемо сказане як ланцюжок рівностей:

a = bq + r₁,

b = r₁q₁ + r₂,

r₁ = r₂q₂ + r₃,

...

r_k-2 = r_k-1q_k-1 + r_k,

r_k-1 = r_kq_k.

З останньої рівності випливає, що r_k є дільником r_k-1, r_k = (r_k; r_k-1). Через (n; т) позначено найбільший спільний дільник чисел n і m. З передостанньої рівності випливає, що r_k ділить також r_k-2 і r_k = (r_k-1; r_k-2).

Так, послідовно піднімаючись кроками вгору, дістанемо, що r_k = (a; b).

Приклад. Знайти НСД чисел 9765 і 6944.

Розв'язання.

9765 = 6944 · 1 + 2821,

6944 = 2821 · 2 + 1302,

2821 = 1302 · 2 + 217,

1302 = 217 · 6.

Відповідь. 217.

Джерело: У світі математики. Випуск 19. За редакцією М. Й. Ядренка. Київ 1989.