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

Алгоритм Евклида нахождения НОД (наибольшего общего делителя)

Даны два целых неотрицательных числа и . Требуется найти их наибольший общий делитель, т.е. наибольшее число, которое является делителем одновременно и , и . На английском языке "наибольший общий делитель" пишется "greatest common divisor", и распространённым его обозначением является :

(здесь символом "" обозначена делимость, т.е. "" обозначает " делит ")

Когда оно из чисел равно нулю, а другое отлично от нуля, их наибольшим общим делителем, согласно определению, будет это второе число. Когда оба числа равны нулю, результат не определён (подойдёт любое бесконечно большое число), мы положим в этом случае наибольший общий делитель равным нулю. Поэтому можно говорить о таком правиле: если одно из чисел равно нулю, то их наибольший общий делитель равен второму числу.

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

Данный алгоритм был впервые описан в книге Евклида "Начала" (около 300 г. до н.э.), хотя, вполне возможно, этот алгоритм имеет более раннее происхождение.

Алгоритм

Сам алгоритм чрезвычайно прост и описывается следующей формулой:

Реализация

int gcd (int a, int b) { if (b == 0 ) return a; else return gcd (b, a % b) ; }

Используя тернарный условный оператор C++, алгоритм можно записать ещё короче:

int gcd (int a, int b) { return b ? gcd (b, a % b) : a; }

Наконец, приведём и нерекурсивную форму алгоритма:

int gcd (int a, int b) { while (b) { a % = b; swap (a, b) ; } return a; }

Доказательство корректности

Сначала заметим, что при каждой итерации алгоритма Евклида его второй аргумент строго убывает, следовательно, посколько он неотрицательный, то алгоритм Евклида всегда завершается .

Для доказательства корректности нам необходимо показать, что для любых >.

Покажем, что величина, стоящая в левой части равенства, делится на настоящую в правой, а стоящая в правой — делится на стоящую в левой. Очевидно, это будет означать, что левая и правая части совпадают, что и докажет корректность алгоритма Евклида.

Обозначим . Тогда, по определению, и .

Но тогда отсюда следует:

Итак, вспоминая утверждение , получаем систему:

Воспользуемся теперь следующим простым фактом: если для каких-то трёх чисел выполнено: и , то выполняется и: . В нашей ситуации получаем:

Или, подставляя вместо его определение как , получаем:

Итак, мы провели половину доказательства: показали, что левая часть делит правую. Вторая половина доказательства производится аналогично.

Время работы

Время работы алгоритма оценивается теоремой Ламе , которая устанавливает удивительную связь алгоритма Евклида и последовательности Фибоначчи:

Если > и для некоторого , то алгоритм Евклида выполнит не более рекурсивных вызовов.

Широко распространённого в электронной коммерции . Также алгоритм используется при решении линейных диофантовых уравнений , при построении непрерывных дробей , в методе Штурма . Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел , например таких как теорема Лагранжа о сумме четырёх квадратов и основная теорема арифметики .

Энциклопедичный YouTube

1 / 5

✪ Математика. Натуральные числа: Алгоритм Евклида. Центр онлайн-обучения «Фоксфорд»

✪ Алгоритм Евклида

✪ Алгоритм Евклида, быстрый способ найти НОД

✪ Математика 71. Наибольший общий делитель. Алгоритм Евклида - Академия занимательных наук

✪ 20 Цикл while Алгоритм Евклида Python

Субтитры

История

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις - «взаимное вычитание». Этот алгоритм не был открыт Евклидом , так как упоминание о нём имеется уже в Топике Аристотеля . В «Началах» Евклида он описан дважды - в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин . В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Описание

Алгоритм Евклида для целых чисел

Пусть a {\displaystyle a} и b {\displaystyle b} - целые числа, не равные одновременно нулю, и последовательность чисел

a > b > r 1 > r 2 > r 3 > r 4 > … > r n {\displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}>\ \dots \ >r_{n}}

определена тем, что каждое r k {\displaystyle r_{k}} - это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

a = b q 0 + r 1 , {\displaystyle a=bq_{0}+r_{1},} b = r 1 q 1 + r 2 , {\displaystyle b=r_{1}q_{1}+r_{2},} r 1 = r 2 q 2 + r 3 , {\displaystyle r_{1}=r_{2}q_{2}+r_{3},} ⋯ {\displaystyle \cdots } r k − 2 = r k − 1 q k − 1 + r k , {\displaystyle r_{k-2}=r_{k-1}q_{k-1}+r_{k},} ⋯ {\displaystyle \cdots } r n − 2 = r n − 1 q n − 1 + r n , {\displaystyle r_{n-2}=r_{n-1}q_{n-1}+r_{n},} r n − 1 = r n q n . {\displaystyle r_{n-1}=r_{n}q_{n}.}

Тогда НОД(a , b ), наибольший общий делитель a и b , равен r n , последнему ненулевому члену этой последовательности .

Существование таких r 1 , r 2 , ..., r n , то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m .

Корректность этого алгоритма вытекает из следующих двух утверждений :

• Пусть a = b ⋅q + r , тогда НОД (a, b) = НОД (b, r).

Доказательство

• НОД(r , 0) = r для любого ненулевого r (так как 0 делится на любое целое число, кроме нуля).

Геометрический алгоритм Евклида

Пусть даны два отрезка длины a и b . Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы , и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом и реализуется с помощью циркуля и линейки.

Пример

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q 0 = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q 1 = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q 2 = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a > b > r 1 > r 2 > r 3 > … > r n в данном конкретном случае будет выглядеть так:

1071 > 462 > 147 > 21.

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462) = 21.

В табличной форме шаги были следующие:

Применения

Расширенный алгоритм Евклида и соотношение Безу

Формулы для r i {\displaystyle r_{i}} могут быть переписаны следующим образом:

r 1 = a + b (− q 0) {\displaystyle r_{1}=a+b(-q_{0})} r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) {\displaystyle r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})} ⋮ {\displaystyle \vdots } НОД (a , b) = r n = a s + b t {\displaystyle (a,b)=r_{n}=as+bt}

Здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу , а числа s и t - коэффициентами Безу . Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики .

Цепные дроби

Алгоритм Евклида достаточно тесно связан с цепными дробями . Отношение a /b допускает представление в виде цепной дроби:

a b = [ q 0 ; q 1 , q 2 , ⋯ , q n ] {\displaystyle {\frac {a}{b}}=} .

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t /s , взятому со знаком минус:

[ q 0 ; q 1 , q 2 , ⋯ , q n − 1 ] = − t s {\displaystyle =-{\frac {t}{s}}} .

Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N {\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&{}\ \vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&{}\ \vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\end{aligned}}}

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме:

a b = q 0 + 1 q 1 + r 1 r 0 {\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}}

Третье равенство может быть использовано, чтобы заменить знаменатель выражения r 1 /r 0 , получим:

a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 {\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}}

Последнее отношение остатков r k /r k −1 всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] {\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=}

Обобщённый алгоритм Евклида для многочленов

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k [x ] от одной переменной над произвольным полем k , поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS) .

Пример для кольца Z [x ]

Пусть cont(f) по определению - НОД коэффициентов многочлена f(x) из Z[x] - содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)). Эти определения понадобятся для нахождения НОД двух многочленов p 1 (x) и p 2 (x) в кольце Z[x]. Для многочленов над целыми числами верно следующее:

C o n t ({\displaystyle cont(} НОДНОД { c o n t (p 1 (x)) , c o n t (p 2 (x)) } , {\displaystyle \{cont(p_{1}(x)),cont(p_{2}(x))\},}

P r i m p a r t ({\displaystyle primpart(} НОД { p 1 (x) , p 2 (x) }) = {\displaystyle \{p_{1}(x),p_{2}(x)\})=} НОД { p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) } . {\displaystyle \{primpart(p_{1}(x)),primpart(p_{2}(x))\}.}

Таким образом, задача поиска НОД двух произвольных многочленов сводится к задаче поиска НОД примитивных полиномов.

Пусть есть два примитивных многочлена p 1 (x) и p 2 (x) из Z[x], для которых выполняется соотношение между их степенями: deg(p 1 (x)) = m и deg(p 2 (x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p 1 (x) {\displaystyle p_{1}(x)} на (l c (p 2 (x))) m − n + 1 {\displaystyle (lc(p_{2}(x)))^{m-n+1}} , то есть

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg ⁡ (r (x)) < deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

где q (x) {\displaystyle q(x)} и r (x) {\displaystyle r(x)} - соответственно псевдочастное и псевдоостаток.

Итак, p 1 (x) , p 2 (x) ∈ Z [ x ] {\displaystyle p_{1}(x),p_{2}(x)\in Z[x]} , причём deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 {\displaystyle \deg(p_{1})=n_{1}\geq \deg(p_{2})=n_{2}} . Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

C:= {\displaystyle c:=} НОД { c o n t (p 1) , c o n t (p 2) } {\displaystyle \{cont(p_{1}),cont(p_{2})\}} .

2. Вычисление примитивных частей:

P 1 ′ (x) := p r i m p a r t (p 1 (x)) ; {\displaystyle p_{1}"(x):=primpart(p_{1}(x));}

P 2 ′ (x) := p r i m p a r t (p 2 (x)) . {\displaystyle p_{2}"(x):=primpart(p_{2}(x)).}

3. Построение последовательности полиномиальных остатков:

P 1 ′ (x) , {\displaystyle p_{1}"(x),}

P 2 ′ (x) , {\displaystyle p_{2}"(x),}

P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , {\displaystyle p_{3}(x):=prem(p_{1}"(x),p_{2}"(x)),}

P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , {\displaystyle p_{4}(x):=prem(p_{2}"(x),p_{3}(x)),}

P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , {\displaystyle p_{5}(x):=prem(p_{3}(x),p_{4}(x)),}

. . . {\displaystyle ...}

P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . {\displaystyle p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).}

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Алгоритм нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.
2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

Алгоритм Евклида

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

Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

НОД(12, 18) = 6.

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида .

Идея алгоритма Евклида

Идея этого алгоритма основана на том свойстве, что если M>N, то

НОД(М, N) = НОД(М - N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Легко доказать это свойство. Пусть К - общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

Второе очевидное свойство:

НОД(М, М) = М.

Для "ручного" счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М=32, N=24:

Структура алгоритма - цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.

Шаг	Операция	M	N	Условие
1	ввод М	32
2	ввод N		24
3	M ¹ N			32 ¹ 24, да
4	M>N			32>24, да
5	M:=M-N	8
6	M ¹ N			8 ¹ 24, да
7	M>N			8>24, нет
8	N:=N-M		16
9	M ¹ N			8 ¹ 16, да
10	M>N			8>16, нет
11	N:=N-M		8
12	M ¹ N			8 ¹ 8, нет
13	вывод M	8
14	конец

В итоге получился верный результат.

Программа на АЯ и на Паскале

Запишем алгоритм на АЯ и программу на Паскале.

Вопросы и задания

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.

2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

НОД(А, B, С) = НОД(НОД(А, В), С).

3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А × В = НОД(А, В) × НОК(А, В).