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

1.1 Применение алгоритма Евклида

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей (a, b). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что

r n = au + bv = (a, b).

Действительно, из цепочки равенств имеем:

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)

Au + bv = (a, b).

Несомненно, описанная Евклидом процедура определения общей меры двух величин применительно к числам (а общая мера двух натуральных чисел, очевидно, есть их наибольший общий делитель) была изобретена задолго до Евклида. Таким же образом находили НОД и древние китайские математики. И только то, что эта процедура стала известна в эпоху Возрождения именно из «Начал, дало ей название « алгоритм Евклида»

Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как

2,99999919 <= 3, 000000261,

Древние вычислители объясняли длинной фразой.

Если бы пришлось сравнить более близкие отношения чисел, например, и, то вычисления были бы более сложными:

71755875 = 61735500 + 10020375;

61735500 = 6 · 10020375 + 1613250;

10020375 = 6 · 1613250 + 340875;

1613250 = 4 · 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 · 91125 + 67500;

91125 = 67500 + 23625;

67500 = 2 · 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 · 3375.

Алгоритм Евклида здесь позволяет определить НОД чисел 71755875 и 61735500, равный 3375 и соответствует разложению отношения 71755875 к 61735500 в цепную дробь:

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

равное дроби, в современной математике называется «подходящей дробью» разложения отношения б= в цепную (или непрерывную) дробь.

Ясно, что

б=1+ < 1 + и б=1 + > 1+ = ,

поскольку

Приведенное сравнение > было выполнено в III в. до н.э. Аристархом Самосским в трактате «О расстоянии и размерах Луны и Солнца».

Сейчас известно, что подходящие дроби разложения любого (рационального или иррационального) числа в цепную дробь представляют собой наилучшие рациональные приближения этого числа.

Алгоритмы с многочленами

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

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

Анализ алгоритма Евклида в Евклидовых кольцах

Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи. Суть последовательности Фибоначчи в том, что начиная с 1,1 следующее число получается сложением двух предыдущих. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …...

История формирования понятия "алгоритм". Известнейшие алгоритмы в истории математики

Алгоритм Евклида является универсальным способом, который позволяет вычислять наибольший общий делитель двух положительных целых чисел. Описание алгоритма нахождения НОД делением: 1. Большее число делим на меньшее 2. Если делится без остатка...

Кольцо целых чисел Гаусса

Мы пользуемся обычным для колец определением наибольшего общего делителя. НОДом двух гауссовых чисел называется такой их общий делитель, который делится на любой другой их общий делитель. Как и во множестве целых чисел...

Математические основы системы остаточных классов

Рассмотрим пример. Пусть р = 6. Тогда имеем шесть классов разбиения множества целых чисел по модулю 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; где через r обозначен остаток от деления целого числа на 6...

Методика изучения многочленов на факультативных занятиях в старших класса средней общеобразовательной школе

Пусть кольцо многочленов над. Определение 1: Пусть и, если существует многочлен, то остаток от деления равен нулю, то называется делителем многочлена и обозначается: ()...

Основные этапы становления и структура современной математики

В III веке до нашей эры в Александрии появилась книга Евклида с тем же названием, в русском переводе "Начала". От латинского названия "Начал" произошёл термин "элементарная геометрия". Несмотря на то...

На территории некого города N размещены заводы и магазины, в которые поставляется продукция с этих заводов. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы...

Применение методов дискретной математики в экономике

Фирме, занимающейся перевозкой скоропортящихся товаров, необходимо доставить товар из Суйфэньхе в Хабаровск, причем маршрутов, по которым можно произвести доставку несколько. Расстояние между Суйфэньхе и городом 2 составляет 15 км...

Развитие понятия "Пространство" и неевклидова геометрия

Специальные методы интегрирования рациональных выражений

Пусть необходимо найти НОД многочленов и. Не ограничивая общности, будем считать, что степень не выше степени. Многочлен представим в виде: где - остаток от деления на. Тогда степень меньше степени делителя. Далее...

Теория остатков

Определение. Число d ??Z , делящее одновременно числа а, b , c , ... , k ??Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = (a , b , c , ..., k) . Теорема. Если (a , b) = d...

Теория остатков

Пусть требуется решить линейное диофантово уравнение: ax + by = c , где a , b , c ??Z ; a и b - не нули. Попробуем порассуждать, глядя на это уравнение. Пусть (a , b) = d . Тогда a = a 1 d ; b = b 1 d и уравнение выглядит так: a 1 d· x + b 1 d· y = c , т.е. d· (a 1 x + b 1 y) = c...

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

Энциклопедичный 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)).}

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

Навигация по странице.

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

Заметим, что если бы мы с самого начала обратились к таблице простых чисел , то выяснили бы, что числа 661 и 113 – простые, откуда можно было бы сразу сказать, что их наибольший общий делитель равен 1 .

Ответ:

НОД(661, 113)=1 .

Нахождение НОД с помощью разложения чисел на простые множители

Рассмотрим еще один способ нахождения НОД. Наибольший общий делитель может быть найден по разложениям чисел на простые множители . Сформулируем правило: НОД двух целых положительных чисел a и b равен произведению всех общих простых множителей, находящихся в разложениях чисел a и b на простые множители .

Приведем пример для пояснения правила нахождения НОД. Пусть нам известны разложения чисел 220 и 600 на простые множители, они имеют вид 220=2·2·5·11 и 600=2·2·2·3·5·5 . Общими простыми множителями, участвующими в разложении чисел 220 и 600 , являются 2 , 2 и 5 . Следовательно, НОД(220, 600)=2·2·5=20 .

Таким образом, если разложить числа a и b на простые множители и найти произведение всех их общих множителей, то этим будет найден наибольший общий делитель чисел a и b .

Рассмотрим пример нахождения НОД по озвученному правилу.

Пример.

Найдите наибольший общий делитель чисел 72 и 96 .

Решение.

Разложим на простые множители числа 72 и 96 :

То есть, 72=2·2·2·3·3 и 96=2·2·2·2·2·3 . Общими простыми множителями являются 2 , 2 , 2 и 3 . Таким образом, НОД(72, 96)=2·2·2·3=24 .

Ответ:

НОД(72, 96)=24 .

В заключение этого пункта заметим, что справедливость приведенного правила нахождения НОД следует из свойства наибольшего общего делителя, которое утверждает, что НОД(m·a 1 , m·b 1)=m·НОД(a 1 , b 1) , где m – любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a 1 , a 2 , …, a k равен числу d k , которое находится при последовательном вычислении НОД(a 1 , a 2)=d 2 , НОД(d 2 , a 3)=d 3 , НОД(d 3 , a 4)=d 4 , …, НОД(d k-1 , a k)=d k .

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

Пример.

Найдите наибольший общий делитель четырех чисел 78 , 294 , 570 и 36 .

Решение.

В этом примере a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .

Сначала по алгоритму Евклида определим наибольший общий делитель d 2 двух первых чисел 78 и 294 . При делении получаем равенства 294=78·3+60 ; 78=60·1+18 ; 60=18·3+6 и 18=6·3 . Таким образом, d 2 =НОД(78, 294)=6 .

Теперь вычислим d 3 =НОД(d 2 , a 3)=НОД(6, 570) . Опять применим алгоритм Евклида: 570=6·95 , следовательно, d 3 =НОД(6, 570)=6 .

Осталось вычислить d 4 =НОД(d 3 , a 4)=НОД(6, 36) . Так как 36 делится на 6 , то d 4 =НОД(6, 36)=6 .

Таким образом, наибольший общий делитель четырех данных чисел равен d 4 =6 , то есть, НОД(78, 294, 570, 36)=6 .

Ответ:

НОД(78, 294, 570, 36)=6 .

Разложение чисел на простые множители также позволяет вычислять НОД трех и большего количества чисел. В этом случае наибольший общий делитель находится как произведение всех общих простых множителей данных чисел.

Пример.

Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.

Решение.

Разложим числа 78 , 294 , 570 и 36 на простые множители, получаем 78=2·3·13 , 294=2·3·7·7 , 570=2·3·5·19 , 36=2·2·3·3 . Общими простыми множителями всех данных четырех чисел являются числа 2 и 3 . Следовательно, НОД(78, 294, 570, 36)=2·3=6 .

Ознакомить с понятием «алгоритм Евклида».
Научить находить наиболее общие делители разными математическими способами.

Ход урока

Понятие Алгоритм Евклида

Является одним из древнейших математических , которой уже более 2000 лет.

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

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

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

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

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

Описание алгоритма нахождения наибольшего общего делителя делением

Большее число делится на меньшее

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

Если есть остаток, то большее число заменяем на остаток от деления

Переход к пункту 1.

Пример:

Найти наибольший общий делитель для 300 и 180.

300/180 = 1 (остаток 120)

180/120 = 1 (остаток 60)

120/60 = 2 (остаток 0).

Конец: наибольший общий делитель – это 6.

В цикле «a» или «b» фиксируется остаток от деления. Когда остатка нет (мы не знаем в «а» он или «b,» поэтому проверяем оба условия ), то цикл завершается.

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

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

Описание алгоритма нахождения наибольшего общего делителя вычитанием

Из большего числа вычитается меньшее

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

Если результат вычитания не равен 0, то большее число заменяется на результат вычитания

Переход к пункту 1.

Пример: Найти для чисел 300 и 180.

Конец: Наиболее общий делитель чисел 300 и 180 – 60.

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

При нахождении наибольшей общей меры двух отрезков поступают такими же способами, что и выше.

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

Если отрезки a иb соизмерыми, то последний не нулевой остаток даст наибольшую общую меру отрезков.

В случае их несоизмеримости полученная последовательность не нулевых остатков будет бесконечной.

Пример:

В качестве отрезков возьмём сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°.

В качестве первого остатка мы получим отрезок AD (CD-биссектриса угла C), и, как легко видеть, последовательность и нулевых остатков будет бесконечной.

Значит, отрезки AB и AC не соизмеримы.

Вопросы

1. Что представляет собой алгоритм Евклида?

2. Что такое наибольший общий делитель?

Список использованных источников

1. Урок на тему: «Алгоритм Эвклида», Корчевой П. И., г. Луцк

2. Щетников А. И. Алгоритм Евклида и непрерывные дроби. - Новосибирск: АНТ, 2003 г.

3. Коунтинхо С. Введение в теорию чисел. Алгоритм RSA, – М., 2001 г.

4. Кострикин А.И. Введение в алгебру, – М., 2000 г.

Отредактировано и выслано преподавателем Киевского национального университета им. Тараса Шевченко Соловьевым М. С.

Над уроком работали

Корчевой П. И.

Соловьев М. С.

Поставить вопрос о современном образовании, выразить идею или решить назревшую проблему Вы можете на Образовательном форуме

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

Вычисление НОД делением

Наибольший общий делитель пары чисел – это самое большое число, которое нацело делит оба числа пары. Пусть требуется вычислить НОД для чисел 108 и 72. Алгоритм вычисления делением будет таковым:

Разделим большее число (делимое) на меньшее (делитель): 108 / 72 = 1, остаток 36.
Поскольку остаток не был равен нулю, то сделаем делитель делимым, а остаток – делителем: 72 / 36 = 2, остаток 0.
Когда остаток равен нулю, то делитель является искомым НОД для пары заданных чисел. То есть НОД(108, 72) = 36. Действительно, 108 / 36 = 3 и 72 / 36 = 2.

В данном алгоритме деление повторяется до тех пор, пока остаток не станет равным нулю . Когда он таковым становится, НОДом является делитель последнего деления . Например, требуется найти НОД(106, 16):

106 / 16 = 6, остаток 10
16 / 10 = 1, остаток 6
10 / 6 = 1, остаток 4
6 / 4 = 1, остаток 2
4 / 2 = 2, остаток 0
НОД(106, 16) = 2

Вычисление НОД вычитанием

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

Пусть требуется найти НОД(108, 72):

108 - 72 = 36
72 - 36 = 36
36 - 36 = 0
НОД(108, 72) = 36

Найдем НОД(44, 60):

60 - 44 = 16
44 - 16 = 28
28 - 16 = 12
16 - 12 = 4
12 - 4 = 8
8 - 4 = 4
4 - 4 = 0
НОД(44, 60) = 4

Данный алгоритм иногда описывают по-другому. Вычитание заканчивают раньше, на шаге, когда одно число нацело делит другое. То есть комбинируют вычитание с проверкой делимости. Тогда нахождение НОД для 44 и 60 будет выглядеть так:

Делит ли 44 нацело 60? Нет. 60 - 44 = 16.
Делит ли 16 нацело 44? Нет. 44 - 16 = 28.
Делит ли 16 нацело 28? Нет. 28 - 16 = 12.
Делит ли 12 нацело 16? Нет. 16 - 12 = 4.
Делит ли 4 нацело 12? Да. Значит, НОД(44, 60) = 4.

Обратите внимание, НОДом является не частное, а делитель . Если в примере мы разделим 12 на 4, то получим частное 3. Но это не НОД.

Доказательство алгоритма Евклида

Примем во внимание факт, что если одно натуральное число из пары нацело делит другое, то их НОД будет равен меньшему из них. Записать это можно так:

если a / b нацело, то НОД(a, b) = b. Например, НОД(15, 5) = 5.

Таким образом, если в конечном итоге мы приходим к паре чисел, одно из которых делит нацело другое, то меньшее будет для обоих наибольшим общим делителем. Именно такая пара чисел ищется алгоритмом Евклида: одно число нацело делит другое.

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

если a < b, то НОД(a, b) = НОД(a, b - a).

Доказать, что НОД(a, b) = НОД(a, b - a) можно следующим образом. Пусть b - a = c. Если какое-либо число x делит нацело a и b, то оно будет также делить нацело c. Ведь если a и b различны, то делитель в них укладывается целое, но разное число раз. И если вычесть одно из другого, то делитель также должен укладываться целое число раз в полученную разность.

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