Изучение алгоритма евклида в школе. Алгоритм евклида - нахождение наибольшего общего делителя

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

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

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

Определение 2

Если натуральное число a делится на натуральное число $b$, то $b$ называют делителем числа $a$, а число $a$ называют кратным числа $b$.

Пусть $a$ и $b$-натуральные числа. Число $c$ называют общим делителем и для $a$ и для $b$.

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

$НОД \ (a;b) \ или \ D \ (a;b)$

Чтобы найти наибольший общий делитель двух, чисел необходимо:

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

Пример 1

Найти НОД чисел $121$ и $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Выбрать числа, которые входят в разложение этих чисел

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

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

$НОД=2\cdot 11=22$

Пример 2

Найти НОД одночленов $63$ и $81$.

Будем находить согласно представленному алгоритму. Для этого:

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

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Выбираем числа, которые входят в разложение этих чисел

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

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

$НОД=3\cdot 3=9$

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

Пример 3

Найти НОД чисел $48$ и $60$.

Решение:

Найдем множество делителей числа $48$: $\left\{{\rm 1,2,3.4.6,8,12,16,24,48}\right\}$

Теперь найдем множество делителей числа $60$:$\ \left\{{\rm 1,2,3,4,5,6,10,12,15,20,30,60}\right\}$

Найдем пересечение этих множеств: $\left\{{\rm 1,2,3,4,6,12}\right\}$- данное множество будет определять множество общих делителей чисел $48$ и $60$. Наибольший элемент в данном множестве будет число $12$. Значит наибольший общий делитель чисел $48$ и $60$ будет $12$.

Определение НОК

Определение 3

Общим кратным натуральных чисел $a$ и $b$ называется натуральное число, которое кратно и $a$ и $b$.

Общими кратными чисел называются числа которые делятся на исходные без остатка.Например для чисел $25$ и $50$ общими кратными будут числа $50,100,150,200$ и т.д

Наименьшее из общих кратных будет называться наименьшим общим кратным и обозначается НОК$(a;b)$ или K$(a;b).$

Чтобы найти НОК двух чисел, необходимо:

1. Разложить числа на простые множители
2. Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого

Пример 4

Найти НОК чисел $99$ и $77$.

Будем находить согласно представленному алгоритму. Для этого

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

$99=3\cdot 3\cdot 11$

Выписать множители, входящие в состав первого

добавить к ним множители, которые входят в состав второго и не ходят в состав первого

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

$НОК=3\cdot 3\cdot 11\cdot 7=693$

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

Утверждения, на которых основан алгоритм Евклида:

Если $a$ и $b$ --натуральные числа, причем $a\vdots b$, то $D(a;b)=b$

Если $a$ и $b$ --натуральные числа, такие что $b

Пользуясь $D(a;b)= D(a-b;b)$, можно последовательно уменьшать рассматриваемые числа до тех пор, пока не дойдем до такой пары чисел, что одно из них делится на другое. Тогда меньшее из этих чисел и будет искомым наибольшим общим делителем для чисел $a$ и $b$.

Свойства НОД и НОК

1. Любое общее кратное чисел $a$ и $b$ делится на K$(a;b)$
2. Если $a\vdots b$ , то К$(a;b)=a$

Если К$(a;b)=k$ и $m$-натуральное число, то К$(am;bm)=km$

Если $d$-общий делитель для $a$ и $b$,то К($\frac{a}{d};\frac{b}{d}$)=$\ \frac{k}{d}$

Если $a\vdots c$ и $b\vdots c$ ,то $\frac{ab}{c}$ - общее кратное чисел $a$ и $b$

Для любых натуральных чисел $a$ и $b$ выполняется равенство

$D(a;b)\cdot К(a;b)=ab$

Любой общийй делитель чисел $a$ и $b$ является делителем числа $D(a;b)$

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

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

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

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

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

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

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

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

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

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. НОД(108, 72) = 36

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

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. НОД(44, 60) = 4

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

1. Делит ли 44 нацело 60? Нет. 60 - 44 = 16.
2. Делит ли 16 нацело 44? Нет. 44 - 16 = 28.
3. Делит ли 16 нацело 28? Нет. 28 - 16 = 12.
4. Делит ли 12 нацело 16? Нет. 16 - 12 = 4.
5. Делит ли 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, то рано или поздно придем к такому значению меньшего из них, которое нацело делит большее. Меньшее в такой паре будет наибольшим общим делителем для исходной пары натуральных чисел. В этом и заключается алгоритм Евклида.

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

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

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

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

a = b · q 1 + r 1 , 0 < r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Мы можем закончить деление тогда, когда r k + 1 = 0 , при этом r k = НОД (a , b) .

Пример 1

64 и 48 .

Решение

Введем обозначения: a = 64 , b = 48 .

На основе алгоритма Евклида проведем деление 64 на 48 .

Получим 1 и остаток 16 . Получается, что q 1 = 1 , r 1 = 16 .

Вторым шагом разделим 48 на 16 , получим 3 . То есть q 2 = 3 , а r 2 = 0 . Таким образом число 16 – это наибольший общий делитель для чисел из условия.

Ответ: НОД (64 , 48) = 16 .

Пример 2

Чему равен НОД чисел 111 и 432 ?

Решение

Делим 432 на 111 . Согласно алгоритму Евклида получаем цепочку равенств 432 = 111 · 3 + 99 , 111 = 99 · 1 + 12 , 99 = 12 · 8 + 3 , 12 = 3 · 4 .

Таким образом, наибольший общий делитель чисел 111 и 432 – это 3 .

Ответ: НОД (111 , 432) = 3 .

Пример 3

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

Решение

Проведем последовательно деление чисел и получим НОД (661 , 113) = 1 . Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.

Ответ: НОД (661 , 113) = 1 .

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

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

Пример 4

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

Пример 5

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

Решение

Найдем все простые множители чисел 72 и 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 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 .

Пример 6

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

Решение

Введем обозначения: a 1 = 78 , a 2 = 294 , a 3 = 570 , a 4 = 36 .

Начнем с того, что найдем НОД чисел 78 и 294: 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 .

Ответ:

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

Пример 7

Вычислите НОД чисел 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 .

Ответ: НОД (78 , 294 , 570 , 36) = 6 .

Нахождение НОД отрицательных чисел

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

Пример 8

Найдите НОД отрицательных целых чисел − 231 и − 140 .

Решение

Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140 . Запишем это кратко: НОД (− 231 , − 140) = НОД (231 , 140) . Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231 = 140 · 1 + 91 ; 140 = 91 · 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 · 1 + 7 и 42 = 7 · 6 . Получаем, что НОД (231 , 140) = 7 .

А так как НОД (− 231 , − 140) = НОД (231 , 140) , то НОД чисел − 231 и − 140 равен 7 .

Ответ: НОД (− 231 , − 140) = 7 .

Пример 9

Определите НОД трех чисел − 585 , 81 и − 189 .

Решение

Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим НОД (− 585 , 81 , − 189) = НОД (585 , 81 , 189) . Затем разложим все данные числа на простые множители: 585 = 3 · 3 · 5 · 13 , 81 = 3 · 3 · 3 · 3 и 189 = 3 · 3 · 3 · 7 . Общими для трех чисел являются простые множители 3 и 3 . Получается, что НОД (585 , 81 , 189) = НОД (− 585 , 81 , − 189) = 9 .

Ответ: НОД (− 585 , 81 , − 189) = 9 .

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

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

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

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

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

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