Алгоритм Евкліда
(Л. В. Лобанова, 1989)
Щоб знайти найбільший спільний дільник двох чисел, є дуже простий спосіб, відомий під назвою алгоритму Евкліда, або способу послідовного ділення.
Алгоритм Евкліда, або алгоритм послідовного ділення, полягає ось у чому. Нехай дано натуральні числа a і b, a > b.
Поділимо перше число на друге, дістанемо остачу r1 (r1 < b). Тепер b поділимо на r1, дістанемо остачу r2 (r2 < r1), далі поділимо r1 на r2 і т. д.
Оскільки після кожного наступного кроку утворюється остача, менша від попередньої, то через скінченну кількість кроків дістанемо остачу, яка дорівнює нулю: ділення відбудеться націло і процес припиниться.
Остання відмінна від нуля остача rk, на яку націло ділиться остача rk-1, буде найбільшим спільним дільником чисел a і b.
Справді, запишемо сказане як ланцюжок рівностей:
a = bq + r1,
b = r1q1 + r2,
r1 = r2q2 + r3,
...
rk-2 = rk-1qk-1 + rk,
rk-1 = rkqk.
З останньої рівності випливає, що rk є дільником rk-1, rk = (rk; rk-1). Через (n; т) позначено найбільший спільний дільник чисел n і m. З передостанньої рівності випливає, що rk ділить також rk-2 і rk = (rk-1; rk-2).
Так, послідовно піднімаючись кроками вгору, дістанемо, що rk = (a; b).
Приклад. Знайти НСД чисел 9765 і 6944.
Розв'язання.
9765 = 6944 · 1 + 2821,
6944 = 2821 · 2 + 1302,
2821 = 1302 · 2 + 217,
1302 = 217 · 6.
Відповідь. 217.
Джерело: У світі математики. Випуск 19. За редакцією М. Й. Ядренка. Київ 1989.