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

(Л. В. Лобанова, 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.

Ключові слова: .