Найбільший спільний дільник та методи його знаходження

Будь-які два числа імають спільні дільники, наприклад, 1 і – 1.

Нехай хоча б одне з чисел івідмінне від нуля. Виявляється, що в цьому випадку числаімають такий додатний спільний дільник який ділиться на будь-який спільник дільник цих чисел. Його називаютьнайбільшим спільним дільником чисел і . Числа імають тільки один найбільший спільний дільник.

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

Приклад. Зайти найбільший спільний дільник чисел 4171 і 18527 за алгоритмом Евкліда.

Розв’язок.

Число на яке ділили на останньому кроці — 97.

Це шуканий найбільший спільний дільник.