Наибольший общий делитель двух натуральных чисел $a$ и $b$ — $НОД(a, b)$ — есть наибольшее число, на которое числа $a$ и $b$ делятся без остатка.
Для нахождения $НОД(a, b)$ можно поступить следующим естественным образом: разложить оба числа по степеням простых чисел: $a = 2^{\alpha_1} \cdot 3^{\alpha_2} \cdot \ldots \cdot p^{\alpha_n}_n$, $b = 2^{\beta_1} \cdot 3^{\beta_2} \cdot \ldots \cdot p^{\beta_n}_n$, ($\alpha_k$ и $\beta_k$ могут быть равны нулю). Тогда $$НОД(a, b) = 2^{\min(\alpha_1, \beta_1)} \cdot 3^{\min(\alpha_2, \beta_2)} \cdot \ldots \cdot p^{\min(\alpha_n, \beta_n)}_n.$$ Например, для нахождения наибольшего общего делителя $2625$ и $8100$ получим: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, значит $НОД(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.
Существенный недостаток этого способа в том, что разложить большое число на простые множители не так просто, а точнее — не так быстро.
Евклид в 7 книге «Начал» описывает алгоритм нахождения «общей меры двух чисел». Алгоритм описан геометрически, как нахождение общей меры двух отрезков. Он сводится к «последовательному отнятию» от большего отрезка меньшего отрезка. Теперь этот алгоритм известен как алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел.
Основная идея, на которой основан алгоритм, состоит в том, что $НОД$ чисел $a$ и $b$ равен $НОД$ чисел $b$ и $a-b$. Отсюда следуют, что если поделить $a$ на $b$ с остатком, т.е. представить в виде $a = b \cdot q + r$, то $НОД(a, b) = НОД(b, r)$.
Опишем красивую геометрическую интерпретацию алгоритма, интерактивная реализация которой предложена выше.
В прямоугольнике с длинами сторон $a$ и $b$ закрашиваем максимально возможный квадрат. В оставшемся прямоугольнике снова закрашиваем максимально возможный квадрат. И так далее до тех пор, пока весь исходный прямоугольник не будет закрашен. Длина стороны самого маленького квадрата и будет равна $НОД(a, b)$.
Более подробно геометрическая интерпретация описана ниже, а параллельно приведено арифметическое описание алгоритма Евклида.
| Интерпретация алгоритма | Алгоритм Евклида |
|---|---|
| В прямоугольнике с длинами сторон $a$ и $b$ $(a \gt b)$ закрашивается квадрат максимального размера (со стороной $b$). Эта операция повторяется для не закрашенной части сколько возможно. | Большее число $a$ делится с остатком на меньшее число $b$: $a = b \cdot q_1 + r_1$. |
| Если такие квадраты замощают весь прямоугольник, то число $b$ и есть $НОД$. | Если остаток $r_1$ от деления равен нулю, то меньшее число $b$ и есть $НОД$. |
| Если остаётся прямоугольник (со сторонами $b$ и $r_1$), в нём закрашивается наибольшее возможное число квадратов максимального размера (со стороной $r_1$). | Если остаток $r_1$ не равен нулю, то меньшее число $b$ делится с остатком на $r_1$: $b = r_1 \cdot q_2 + r_2$. |
| Если квадраты со стороной $r_1$ замощают весь прямоугольник, то $r_1$ и есть $НОД$. | Если в результате второго деления остаток $r_2$ равен нулю, то $r_1$ и есть $НОД$. |
| Если остаётся прямоугольник (со сторонами $r_1$ и $r_2$), в нём закрашивается наибольшее возможное число квадратов максимального размера (со стороной $r_2$). | Если остаток $r_2$ при втором делении не равен нулю, то $r_1$ делится на $r_2$: $r_1 = r_2 \cdot q_3 + r_3$. |
| И так далее до тех пор, пока весь исходный прямоугольник не покроется квадратами. (Рано или поздно это произойдёт, поскольку стороны квадратов уменьшаются и в любом случае можно заполнить оставшийся прямоугольник квадратами со стороной единица). | И так далее до тех пор, пока не получится остаток $r_n$ равный нулю (рано или поздно это произойдёт, поскольку остатки уменьшаются). |
| Длина стороны минимального квадрата и есть $НОД$ исходных чисел. | Последний не равный нулю остаток $r_{n-1}$ и есть $НОД$ исходных чисел. |
Алгоритм Евклида является мощным инструментом, используемым при решении различных задач. Например, он используется для решения уравнений в целых числах, представления чисел в виде непрерывных (цепных) дробей, его можно обобщить для нахождения наибольшего общего делителя двух многочленов.
Литература
Евклид. Начала Евклида. Книги VII, X. — М.—Л.: ГИТТЛ, 1950.
Курант Р., Роббинс Г. Что такое математика?: Элементарный очерк идей и методов. — М. : ГИТТЛ, 1947. — [9-e издание, исправленное. — М. : МЦНМО, 2019].
