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

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

Для нахож­де­ния $\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)$.

Более подробно геомет­ри­че­ская интер­пре­тация опи­сана ниже, а парал­лельно при­ве­дено арифме­ти­че­ское опи­са­ние алго­ритма Евклида.

Алго­ритм Евклида явля­ется мощ­ным инструмен­том, исполь­зу­емым при реше­нии раз­лич­ных задач. Напри­мер, он исполь­зу­ется для реше­ния урав­не­ний в целых чис­лах, пред­став­ле­ния чисел в виде непре­рыв­ных (цеп­ных) дро­бей, его можно обобщить для нахож­де­ния наи­большего общего дели­теля двух много­чле­нов.