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

Найдавнішим нетривіальним алгоритмом є спосіб знаходження найбільшого спільного дільника двох цілих чисел - алгоритм Евкліда. Він був викладений у працях давньогрецького математика Евкліда - сьомої книги "Начал" - близько 2300 років тому. Звичайно, можна заперечити – а як же давні єгиптяни? Вавилоняни? Невже вони не змогли запропонувати більш давній алгоритм? Обчислення стародавніх єгиптян і вавилонян знайдено, вони старші за грецькі на півтори тисячі років, але алгоритм Евкліда має одну істотну різницю – він є ітераційним, тобто має неодноразове повторення певних дій.

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

"Нехай А і С - два даних позитивних цілих числа. Треба знайти їх найбільший спільний дільник. Якщо С ділить А, то С є спільним дільником чисел С і А, тому що ділить і саме себе. Очевидно, що С буде найбільшим дільником, оскільки немає числа, більшого С, яке ділило б С.

Якщо ж С не ділить А, то починаємо безперервно віднімати менше з чисел А і С з більшого до тих пір, поки не отримаємо деяке число, яке націло ділить попереднє число яке віднімалось. Рано чи пізно таке число вийде, тому що якщо різниця дорівнюватиме одиниці, то одиниця буде ділити попереднє віднімане.

Отже, нехай Е - позитивний залишок від поділу А на С, F – позитивний залишок від поділу С на Е, F ділить Е. Оскільки F ділить Е, а Е ділить С – F, то F також ділить С – F, але F ділить саме себе, отже, F ділить С. Але С ділить А - Е; тому F також ділить А – Е. Але воно також ділить Е, тому воно ділить і А. Отже, F – спільний дільник чисел А та С.

Тепер я стверджую, що він є найбільшим таким дільником. Справді, якщо F – не найбільший загальний дільник чисел А і С, то деяка більше число ділитиме їх обоє. Нехай таким числом буде B.

Оскільки B ділить С, яке, своєю чергою, ділить А – Е, то B ділить А – Е; B ділить також все А, отже, воно ділить і залишок Е. Але Е ділить С - Е, тому B ділить С - Е. Але B ділить також все С, отже, воно ділить і залишок F; таким чином, більше число ділить менше, а це неможливо.

Тому немає такого числа, більшого, ніж F, яке ділило б числа А і С, і, отже, F – їхній найбільший спільний дільник.

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