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

Наи­боль­ший об­щий де­ли­тель двух на­ту­раль­ных чи­сел $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.

Р. Ку­рант, Г. Ро­бинс. Что та­кое ма­те­ма­ти­ка? — М.: МЦНМО, 2010.

Обсуждение (сообщений: 3)

Другие проекты фонда «Математические этюды»

При поддержке