Эта статья про нахождение наибольшего общего делителя (НОД) двух и большего количества чисел. Сначала рассмотрим алгоритм Евклида, он позволяет находить НОД двух чисел. После этого остановимся на методе, позволяющем вычислять НОД чисел как произведение их общих простых множителей. Дальше разберемся с нахождением наибольшего общего делителя трех и большего количества чисел, а также приведем примеры вычисления НОД отрицательных чисел.
Навигация по странице.
Алгоритм Евклида для нахождения НОД
Заметим, что если бы мы с самого начала обратились к таблице простых чисел , то выяснили бы, что числа 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 .
Рассмотрим два основных метода нахождения НОД двумя основными способами: с использованием алгоритма Евклида и путем разложения на простые множители. Применим оба метода для двух, трех и большего количества чисел.
Алгоритм Евклида для нахождения НОД
Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».
Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:
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
Наи-боль-ший об-щий де-ли-тель двух на-ту-раль-ных чи-сел $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.
- Ознакомить с понятием «алгоритм Евклида».
- Научить находить наиболее общие делители разными математическими способами.
Ход урока
Понятие Алгоритм Евклида
Является одним из древнейших математических , которой уже более 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, то рано или поздно придем к такому значению меньшего из них, которое нацело делит большее. Меньшее в такой паре будет наибольшим общим делителем для исходной пары натуральных чисел. В этом и заключается алгоритм Евклида.