Как найти наибольший общий делитель уравнения

Наибольший общий делитель (НОД), свойства и формулы

О чем эта статья:

5 класс, 6 класс

Понятие наибольшего общего делителя

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

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

Общий делитель нескольких целых чисел — это такое число, которое может быть делителем каждого числа из указанного множества. Например, у чисел 12 и 8 общими делителями будут 4 и 1. Чтобы это проверить, напишем верные равенства: 8 = 4 * 2 и 12 = 3 * 4.

Любое число можно разделить на 1 и на само себя. Значит, у любого набора целых чисел будет как минимум два общих делителя.

Наибольшим общим делителем двух чисел a и b называется наибольшее число, на которое a и b делятся без остатка. Для записи может использоваться аббревиатура НОД. Для двух чисел можно записать вот так: НОД (a, b).

Например, для 4 и 16 НОД будет 4. Как мы к этому пришли:

1. Зафиксируем все делители четырех: 4, 2, 1.
2. А теперь все делители шестнадцати: 16, 8, 4 и 1.
3. Выбираем общие: это 4, 2, 1. Самое большое общее число: 4. Вот и ответ.

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Найдем наибольший общий делитель нескольких целых чисел: 10, 6, 44, 18. Он будет равен трем. Ответ можно записать так: НОД (12, 6, 42, 18) = 3. А чтобы проверить правильность ответа, нужно записать все делители и выбрать из них самые большие.

Взаимно простые числа — это натуральные числа, у которых только один общий делитель — единица. Их НОД равен 1.

Еще один пример. Рассчитаем НОД для 28 и 64.

Распишем простые множители для каждого числа и подчеркнем одинаковые

Д (64) = 2 * 2 * 2 * 2 * 2 * 2

Найдем произведение одинаковых простых множителей и запишем ответ

НОД (28; 64) = 2 * 2 = 4

Ответ: НОД (28; 64) = 4

Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.

Способы нахождения наибольшего общего делителя

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

1. Разложение на множители

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

Пример 1. Найти НОД (84, 90).

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

Подчеркнем все общие множители и перемножим их между собой:

Ответ: НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Разложим 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.

Ответ: НОД (15, 28) = 1.

Пример 3. Найти НОД для 24 и 18.

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

Найдем общие множители чисел 24 и 18: 2 и 3. Для удобства общие множители можно подчеркнуть.

Перемножим общие множители:

НОД (24, 18) =2 * 3 = 6

Ответ: НОД (24, 18) = 6

Онлайн-курсы математики для детей помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.

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

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

Алгоритм Евклида заключается в следующем: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем. Использовать метод Евклида можно легко по формуле нахождения наибольшего общего делителя.

Формула НОД: НОД (a, b) = НОД (b, с), где с — остаток от деления a на b.

Пример 1. Найти НОД для 24 и 8.

Так как 24 делится на 8 и 8 тоже делится на 8, значит, 8 — общий делитель этих чисел. Этот делитель является наибольшим, потому что 8 не может делиться ни на какое число, большее его самого. Поэтому: НОД (24, = 8.

В остальных случаях для нахождения наибольшего общего делителя двух чисел нужно соблюдать такой порядок действий:

1. Большее число поделить на меньшее.
2. Меньшее число поделить на остаток, который получается после деления.
3. Первый остаток поделить на второй остаток.
4. Второй остаток поделить на третий и т. д.
5. Деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель и есть наибольший общий делитель.

Пример 2. Найти наибольший общий делитель чисел 140 и 96:

1. 140 : 96 = 1 (остаток 44)
2. 96 : 44 = 2 (остаток
3. 44 : 8 = 5 (остаток 4)
4. 8 : 4 = 2

Последний делитель равен 4 — это значит: НОД (140, 96) = 4.

Ответ: НОД (140, 96) = 4

Пошаговое деление можно записать столбиком:

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

1. Найти наибольший общий делитель любых двух чисел из данных.
2. Найти НОД найденного делителя и третьего числа.
3. Найти НОД последнего найденного делителя и четвёртого числа и т. д.

Свойства наибольшего общего делителя

У наибольшего общего делителя есть ряд определенных свойств. Опишем их в виде теорем и сразу приведем доказательства.

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

Свойство 1. Наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и а, то есть НОД (a, b) = НОД (b, a). Перемена мест чисел не влияет на конечный результат.

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

Свойство 2. Если а делится на b, то множество общих делителей чисел а и b совпадает со множеством делителей числа b, поэтому НОД (a, b) = b.

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

Любой общий делитель чисел а и b является делителем каждого из этих чисел, в том числе и числа b. Так как а кратно b, то любой делитель числа b является делителем и числа а, благодаря свойствам делимости. Из этого следует, что любой делитель числа b является общим делителем чисел а и b.

Значит, если а делится на b, то совокупность делителей чисел а и b совпадает с совокупностью делителей одного числа b. А так как наибольшим делителем числа b является само число b, то наибольший общий делитель чисела и b также равен b, то есть НОД (а, b) = b.

В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.

• Например, НОД (25, 25) = 25.

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

• Например, НОД (4, 40) = 4, так как 40 кратно 4.

Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.

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

Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.

Поэтому должны совпадать и наибольшие из этих общих делителей, и равенство НОД (a, b) = НОД (b, c) можно считать справедливым.

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).

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

Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.

Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.

Знакомство с темой наибольшего общего делителя начинается в 5 классе с теории и закрепляется в 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 ) .

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

Чему равен НОД чисел 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 .

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

Решение

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

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

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

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

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

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

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

Ответ: НОД ( 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 .

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

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

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

Найдите НОД отрицательных целых чисел − 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 .

Определите НОД трех чисел − 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 .

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

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

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

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

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

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

Деление заканчивается, когда r_k+1=0 , при этом r_k=НОД(a, b) .

Рассмотрим примеры нахождения НОД по алгоритму Евклида.

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

Воспользуемся алгоритмом Евклида. В этом примере a=64 , b=48 .

Делим 64 на 48 , получаем 64:48=1 (ост. 16) (при необходимости смотрите правила и примеры деления с остатком), что можно записать в виде равенства 64=48·1+16 , то есть, q₁=1 , r₁=16 .

Теперь делим b на r₁ , то есть, 48 делим на 16 , получаем 48:16=3 , откуда имеем 48=16·3 . Здесь q₂=3 , а r₂=0 , так как 48 делится на 16 без остатка. Мы получили r₂=0 , поэтому это был последний шаг алгоритма Евклида, и r₁=16 является искомым наибольшим общим делителем чисел 64 и 48 .

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

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

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

Разделив 432 на 111 , получаем равенство 432=111·3+99 .

На следующем шаге делим 111 на 99 , имеем 111=99·1+12 .

Деление 99 на 12 дает равенство 99=12·8+3 .

А 12 на 3 делится без остатка и 12=3·4 . Поэтому это последний шаг алгоритма Евклида, и НОД(432, 111)=3 , следовательно, и искомый наибольший общий делитель чисел 111 и 432 равен 3 .

Для закрепления материала найдем с помощью алгоритма Евклида наибольший общий делитель чисел 661 и 113 .

Найдите НОД(661, 113) по алгоритму Евклида.

Выполняем деление: 661=113·5+96 ; 113=96·1+17 ; 96=17·5+11 ; 17=11·1+6 ; 11=6·1+5 ; 6=5·1+1 , наконец, 5=1·5 . Таким образом, НОД(661, 113)=1 , то есть, 661 и 113 – взаимно простые числа.

Заметим, что если бы мы с самого начала обратились к таблице простых чисел, то выяснили бы, что числа 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 .

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

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

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

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

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

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

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

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

Таким образом, наибольший общий делитель четырех данных чисел равен d₄=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 .

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

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

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

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

Модуль числа −231 равен 231 , а модуль числа −140 равен 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 равен 7 .

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

При нахождении наибольшего общего делителя отрицательные числа можно заменить их абсолютными величинами, то есть, НОД(−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)=3·3=9 , следовательно, НОД(−585, 81, −189)=9 .

Любое натуральное число всегда делится на 1 и на само себя.

Число 2 — наименьшее простое число. Это единственное чётное простое число, остальные простые числа — нечётные.

Простых чисел много, и первое среди них — число 2. Однако нет последнего простого числа. В
разделе «Для учёбы»
вы можете скачать таблицу простых чисел до 997.

Но многие натуральные числа делятся нацело ещё и на другие натуральные числа.

Например:

• число 12
  делится на 1,
  на 2, на 3, на 4,
  на 6, на 12;
• число 36
  делится на 1,
  на 2,
  на 3,
  на 4,
  на 6,
  на 12,
  на 18,
  на 36.

Числа, на которые число делится нацело
(для 12 это
1, 2, 3, 4, 6 и 12) называются
делителями числа.

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

Обратите внимание, что числа 12 и
36 имеют общие делители.
Это числа: 1, 2, 3, 4, 6, 12.
Наибольший из делителей этих чисел — 12.

Общий делитель двух данных чисел «a» и «b» — это число, на которое делятся без остатка
оба данных числа «a» и «b».

Пример: НОД (12; 36) = 12.

Делители чисел в записи решения обозначают большой буквой «Д».

Пример.

Д (7) = {1, 7}

Д (9) = {1, 9}

НОД (7; 9) = 1

Числа
7 и 9 имеют
только один общий делитель — число 1.
Такие числа называют взаимно простыми числами.

Как найти наибольший общий делитель

Чтобы найти НОД двух или более натуральных чисел нужно:

1. разложить делители чисел на простые множители;

Вычисления удобно записывать с помощью вертикальной черты. Слева от черты сначала записываем делимое,
справа — делитель. Далее в левом столбце записываем значения частных.

Поясним сразу на примере. Разложим на простые множители числа 28 и 64.

1. Подчёркиваем одинаковые простые множители в обоих числах.
   
   28 = 2 · 2 · 7

   64 = 2 · 2 · 2 · 2 · 2 · 2

2. Находим произведение одинаковых простых множителей и записать ответ;
   
   НОД (28; 64) = 2 · 2 = 4

   Ответ: НОД (28; 64) = 4

Оформить нахождение НОД можно двумя способами:
в столбик (как делали выше) или «в строчку».

Первый способ записи НОД

Найти НОД 48 и 36.

НОД (48; 36) = 2 · 2 · 3 = 12

Второй способ записи НОД

Теперь запишем решение поиска НОД в строчку. Найти НОД 10 и 15.

Д (10) = {1, 2, 5, 10}

Д (15) = {1, 3, 5, 15}

Д (10, 15) = {1, 5}

НОД (10; 15) = 5

---

Ваши комментарии

Оставить комментарий:

---

О1)Общим делителем многочленов f(x)
и g(x)
называется такой d(x)
что, выполняются f(x)⋮d(x)
и g(x)⋮d(x).

О2)Наибольшим будет тот из общих
делителей степень которого больше.

Будем считать что, общий делитель d(x)
который делится на любой другой делитель
этих многочленов будет наибольшим
d(x)=(f(x),g(x))
очевидно что, общим делителем многочленов
будет и делитель вида:
с*d(x)=(с*f(x),с*g(x)),c=const
0.

НОД отыскивается с точностью до
постоянного множителя. Многочлены
отличающееся друг от друга постоянным
множителем называются ассоциированными.
НОД отыскивают с помощью алгоритма
Евклида который состоит в следующем: с
начал делят с остатком многочлен f(x)
на g(x) затем
g(x) на остаток


от первого деления затем

от первого деления на остаток

от второго деления и так далее до тех
пока не получится нулевой остаток при
этом получается цепочка равенств.

Последний не нулевой остаток и есть НОД
двух многочленов.

Пример 1:

В кольце R[x]
найти НОД двух многочленов:

.

На практике может возникнуть задача
отыскания нескольких многочленов:

НОД(f,g…q)=НОД(f,НОД(g,…НОД(t,q)…)).

Т1:НОД двух многочленов может быт
представлен в виде:

Где

из тогоже кольца что, и данные многочлены.

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

Для нахождения НОД(f,g)
воспользуемся равенствами 1 алгоритма
Евклида:

подставляя это равенство во второе
равенство совокупности 1 можем выразить
остаток
.

действуя так и далее можно выразить
остаток

через f(x) и
g(x) а, также
последний остаток
.

Пример 2:

Из примера 1 запишем представление
остатков:

§ 8 Наименьшее общее кратное двух многочленов.

О1) Многочлен

называется общим кратным для

и

если
.

О2)Общее кратное f(x)
и g(x)
на которое делится любое общее кратное
этих многочленов называется наименьшим
общим кратным многочленов

и

и обозначается:
.

Т1:Для любых многочленов

существует наименьшее общее кратное
которое можно найти по формуле

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

Пусть многочлен

некоторое произвольное общее кратное
многочленов f(x)
и g(x). Так
как М общее кратное то M(x)=f(x)p(x),
M(x)=g(x)q(x)

(f(x),g(x))=d(x),
тогда

g(x)⋮d(x)

Из этого равенства видно, что



Получено выражение для произвольного
общего кратного многочленов f(x)
g(x) положив
в этом выражении 𝜑(x)=1
получим формулу для нахождения наименьшего
общего кратного.

Замечание:

[f,g]⋮f

[f,g]⋮g

M⋮[f,g]

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.

Как найти НОД?

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

1. разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
2. выбрать одинаковые множители, входящие в оба разложения;
3. найти их произведение.

Примеры нахождения наибольшего общего делителя

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОД 12 и 8

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2

3. Перемножаем эти множители и получаем: 2 · 2 = 4

Ответ: НОД (8; 12) = 2 · 2 = 4.

Пример 2: найти НОД 75 и 150

Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5

3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75

Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.

Частный случай или взаимно простые числа

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

Пример 3: найти НОД 9 и 5

Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.

Была ли эта статья полезной?