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

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

Для этого термина существует аббревиатура «НОД», которая имеет и другие значения, см. Нод.

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей[1]. Пример: для чисел 54 и 24 наибольший общий делитель равен 6.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не равно нулю.

Возможные обозначения наибольшего общего делителя чисел m и n:

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

Связанные определения[править | править код]

Наименьшее общее кратное[править | править код]

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n (без остатка). Обозначается НОК(m,n) или [m,n], а в английской литературе {mathrm {lcm}}(m,n).

НОК для ненулевых чисел m и n всегда существует и связан с НОД следующим соотношением:

(m,n)cdot [m,n]=mcdot n

Это частный случай более общей теоремы: если a_{1},a_{2},dots ,a_{n} — ненулевые числа, D — какое-либо их общее кратное, то имеет место формула:

D=[a_{1},a_{2},dots ,a_{n}]cdot left({frac {D}{a_{1}}},{frac {D}{a_{2}}},dots ,{frac {D}{a_{n}}}right)

Взаимно простые числа[править | править код]

Числа m и n называются взаимно простыми, если у них нет общих делителей, кроме pm 1. Для таких чисел НОД{displaystyle (m,n)=1}. Обратно, если НОД{displaystyle (m,n)=1,} то числа взаимно просты.

Аналогично, целые числа a_{1},a_{2},dots a_{k}, где kgeq 2, называются взаимно простыми, если их наибольший общий делитель равен единице.

Следует различать понятия взаимной простоты, когда НОД набора чисел равен 1, и попарной взаимной простоты, когда НОД равен 1 для каждой пары чисел из набора. Из попарной простоты вытекает взаимная простота, но не наоборот. Например, НОД(6,10,15) = 1, но любые пары из этого набора не взаимно просты.

Способы вычисления[править | править код]

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m,n) можно легко вычислить, если известно каноническое разложение чисел m и n на простые множители:

n=p_{1}^{{d_{1}}}cdot dots cdot p_{k}^{{d_{k}}},
m=p_{1}^{{e_{1}}}cdot dots cdot p_{k}^{{e_{k}}},

где p_{1},dots ,p_{k} — различные простые числа, а d_{1},dots ,d_{k} и e_{1},dots ,e_{k} — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(n,m) и НОК[n,m] выражаются формулами:

(n,m)=p_{1}^{{min(d_{1},e_{1})}}cdot dots cdot p_{k}^{{min(d_{k},e_{k})}},
[n,m]=p_{1}^{{max(d_{1},e_{1})}}cdot dots cdot p_{k}^{{max(d_{k},e_{k})}}.

Если чисел более двух: a_{1},a_{2},dots a_{n}, их НОД находится по следующему алгоритму:

d_{2}=(a_{1},a_{2})
d_{3}=(d_{2},a_{3})

………
d_{n}=(d_{{n-1}},a_{n}) — это и есть искомый НОД.

Свойства[править | править код]

  • Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
  • Если m делится на n, то НОД(m, n) = n. В частности, НОД(n, n) = n.
  • {displaystyle (a,b)=(a-b,b)}. В общем случае, если {displaystyle a=b*q+c}, где {displaystyle a,b,c,q} – целые числа, то {displaystyle (a,b)=(b,c)}.
  • (acdot m,acdot n)=|a|cdot (m,n) — общий множитель можно выносить за знак НОД.
  • Если D=(m,n), то после деления на D числа становятся взаимно простыми, то есть, left({{frac {m}{D}},{frac {n}{D}}}right)=1. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.
  • Мультипликативность: если a_{1},a_{2} взаимно просты, то:
(a_{1}cdot a_{2},b)=(a_{1},b)cdot (a_{2},b)
left{acdot m+bcdot nmid a,bin mathbb{Z } right}
и поэтому (m,n) представим в виде линейной комбинации чисел m и n:

(m,n)=ucdot m+vcdot n.
Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы mathbb {Z} , порождённая набором {a_{1},a_{2},dots ,a_{n}}, — циклическая и порождается одним элементом: НОД(a1, a2, … , an).

Вариации и обобщения[править | править код]

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

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

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

НОД двух элементов коммутативного кольца, вообще говоря, не обязан существовать. Например, для нижеследующих элементов a и b кольца {mathbb {Z}}left[{sqrt {-3}}right] не существует наибольшего общего делителя:

a=4=2cdot 2=left(1+{sqrt {-3}}right)left(1-{sqrt {-3}}right),qquad b=left(1+{sqrt {-3}}right)cdot 2.

В евклидовых кольцах наибольший общий делитель всегда существует и определён с точностью до делителей единицы, то есть количество НОД равно числу делителей единицы в кольце.

См. также[править | править код]

  • Бинарный алгоритм вычисления НОД
  • Делимость
  • Алгоритм Евклида
  • Наименьшее общее кратное

Литература[править | править код]

  • Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Примечания[править | править код]

  1. ↑ Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. страница 857
Источник

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

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

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

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

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

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

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

1. Раскладываем 12 и 8 на простые множители:

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

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

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

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

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

1. Раскладываем 75 и 150 на простые множители:

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

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

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

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

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

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

1. Раскладываем 5 и 9 на простые множители:

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

Источник

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

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

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

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

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

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

Пример 1

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

Решение

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

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

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

Вторым шагом разделим 48 на 16, получим 3. То есть q2=3, а r2=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:

72361893122233

96482412631222223

Общими для двух чисел простые множители: 2, 2, 2 и 3. Это значит, что НОД(72, 96)=2·2·2·3=24.

Ответ: НОД(72, 96)=24.

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

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

Независимо  от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.

Пример 6

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

Решение

Введем обозначения: a1=78, a2=294, a3=570, a4=36.

Начнем с того, что найдем НОД чисел 78 и 294: d2=НОД(78, 294)=6.

Теперь приступим к нахождению d3=НОД(d2, a3)=НОД(6, 570). Согласно алгоритму Евклида 570=6·95. Это значит, что d3=НОД(6, 570)=6.

Найдем d4=НОД(d3, a4)=НОД(6, 36). 36 делится на 6 без остатка. Это позволяет нам получить d4=НОД(6, 36)=6.

d4=6, то есть, НОД(78, 294, 570, 36)=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.

Ирина Мальцевская

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

Источник

Как найти НОД

  • Нахождение путём разложения на множители
  • Алгоритм Евклида

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

Нахождение путём разложения на множители

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

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

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

Решение: Раскладываем числа  84  и  90  на простые множители:

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

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

2 · 3 = 6.

Таким образом, НОД (84, 90) = 6.

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

Решение: Раскладываем  15  и  28  на простые множители:

наибольший общий делитель двух чисел

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

НОД (15, 28) = 1.

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

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

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

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

Пример 1. Возьмём два числа  27  и  9.  Так как  27  делится на  9  и  9  делится на  9,  значит,  9  является общим делителем чисел  27  и  9.  Этот делитель является в тоже время и наибольшим, потому что  9  не может делиться ни на какое число, большее  9.  Следовательно:

НОД (27, 9) = 9.

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

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

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

1) 140 : 96 = 1 (остаток 44)

2) 96 : 44 = 2 (остаток 8)

3) 44 : 8 = 5 (остаток 4)

4) 8 : 4 = 2

Последний делитель равен  4  — это значит:

НОД (140, 96) = 4.

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

как найти нод чисел

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

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

Пример 3. Найдём наибольший общий делитель чисел  140,  96  и  48.  НОД чисел  140  и  96  мы уже нашли в предыдущем примере (это число  4).  Осталось найти наибольший общий делитель числа  4  и третьего данного числа —  48:

48 : 4 = 12

48  делится на  4  без остатка. Таким образом:

НОД (140, 96, 48) = 4.

Источник

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


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

4.3

Средняя оценка: 4.3

Всего получено оценок: 222.

4.3

Средняя оценка: 4.3

Всего получено оценок: 222.

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

Что такое НОД?

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

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

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

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

Специальной формулы для этого не придумали, зато есть алгоритм вычисления.

Приведем пример нахождения наибольшего общего делителя двух натуральных чисел: 540 и 252. Разложим 640 на простые множители. Последовательность действий такова:

  • Делим число на наименьший из возможных простых чисел. То есть, если число можно разделить на 2, 3 или 5, то сначала нужно делить на 5. Просто, чтобы не запутаться.
  • Получившийся результат делим на наименьшее из возможных простых чисел.
  • Повторяем деление каждого полученного результата, пока не получим простое число.

Теперь проведем ту же процедуру на практике.

  • 540 : 2=270
  • 270:2=135
  • 135 : 3 =45
  • 45 : 3=15
  • 15 : 5 = 3

Запишем результат в виде равенства 540=2*2*3*3*3*5. Для того, чтобы записать результат, нужно последнее получившееся число умножить на все делители.

Аналогично поступим с числом 252:

  • 252 : 2=126
  • 126: 2=63
  • 63 : 3=21
  • 21 : 3 = 7

Запишем результат: 252=2*2*3*3*7.

В каждом разложении есть одинаковые числа. Найдем их, это два числа 2 и два числа 3. Отличаются только 7 и 3*5.

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

НОД=2*2*3*3=36

Как можно это использовать?

Задача: сократить дробь $$252over540$$.

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

НОД = 36

Сократим числитель и знаменатель дроби на 36 и получим ответ.

$${252over540} ={7over15}$$ – чтобы быстро сократить, достаточно посмотреть на разложение чисел.

Если 540=2*2*3*3*3*5, а НОД=36=2*2*3*3, то 540 = 36*3*5. И если мы поделим 540 на 36, то получим 3*5=15.

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

Заключение

Что мы узнали?

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

Тест по теме

Доска почёта

Доска почёта

Чтобы попасть сюда – пройдите тест.

    Пока никого нет. Будьте первым!

Оценка статьи

4.3

Средняя оценка: 4.3

Всего получено оценок: 222.

А какая ваша оценка?

Источник

Добавить комментарий