Наибольший общий делитель

Наи­больший общий дели­тель двух нату­раль­ных чисел $a$ и $b$ — $\gcd(a, b)$ — есть наи­большее число, на кото­рое числа $a$ и $b$ делятся без остатка.

Пример.
Для нахождения НОД(15, 24)
нарисуем прямоугольник 15×24.
Закрасим максимальный квадрат.
В оставшемся прямоугольнике закрасим максимальный квадрат.
НОД(15, 24)=3.
Действительно, 15=3×5, 24=3×8.
Введите два различных натуральных числа от %LOW% до %HIGH%:
,
НОД(%GRIDY%, %GRIDX%)=%NOD%.
Действительно, %GRIDY%=%NOD%×%GRIDYDIV%, %GRIDX%=%NOD%×%GRIDXDIV%.

Для нахож­де­ния $\gcd(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$ могут быть равны нулю). Тогда

$\gcd(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$, зна­чит

$\gcd(2625, 8100) =$ $2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

Суще­ствен­ный недо­ста­ток этого спо­соба в том, что раз­ложить большое число на про­стые множи­тели не так про­сто, а точ­нее — не так быстро.

Евклид в VII книге «Начал» опи­сы­вает алго­ритм нахож­де­ния «общей меры двух чисел». Алго­ритм опи­сан геомет­ри­че­ски, как нахож­де­ние общей меры двух отрез­ков. Он сво­дится к «после­до­ва­тель­ному отня­тию» от большего отрезка меньшего отрезка. Теперь этот алго­ритм изве­стен как алго­ритм Евклида для нахож­де­ния наи­большего общего дели­теля двух нату­раль­ных чисел.

Основ­ная идея, на кото­рой осно­ван алго­ритм, состоит в том, что НОД чисел $a$ и $b$ равен НОД чисел $b$ и $a-b$. Отсюда сле­дуют, что если поде­лить $a$ на $b$ с остат­ком, т. е. пред­ста­вить в виде $a = b \cdot q + r$, то $\gcd(a, b) = $ $\gcd(b, r)$.

Опишем кра­си­вую геомет­ри­че­скую интер­пре­тацию алго­ритма, интер­ак­тив­ная реа­ли­за­ция кото­рой пред­ложена выше.

В прямо­уголь­нике с дли­нами сто­рон $a$ и $b$ закраши­ваем мак­симально возмож­ный квад­рат. В оставшемся прямо­уголь­нике снова закраши­ваем мак­симально возмож­ный квад­рат. И так далее до тех пор, пока весь исход­ный прямо­уголь­ник не будет закрашен. Длина сто­роны самого маленького квад­рата и будет равна $\gcd(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].