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

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

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

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

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

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).

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

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

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

Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД(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.

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

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

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

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

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

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

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

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

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

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

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

Как находим:

 

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

   Д (28) = 2 * 2 * 7

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

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

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

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

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

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

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

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

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

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

Как решаем:

 

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

   

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

   2 * 3 = 6.

 

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

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

Как решаем:

 

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

   

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

 

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

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

Как решаем:

 

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

   

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

   

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) = 8.

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

 

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.

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

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

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

 

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

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

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

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

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

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

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

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

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

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

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, 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 классе на практике. В этой статье мы узнали все основные определения, свойства и их доказательства, а также как найти НОД.

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 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

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

Как найти НОД

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

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

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

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

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

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

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

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

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

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

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

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

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

Онлайн калькулятор НОД и НОК двух чисел

Наибольший общий делитель (НОД)

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

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

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

• Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» – это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

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

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

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

Наименьшее общее кратное (НОК)

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

НОК двух или более целых чисел — это наименьшее число, которое делится на каждое из этих чисел без остатка.

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

Как найти наименьшее общее кратное (НОК)

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

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

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

• Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
• Выпишем все простые множители: 23⋅32^3 cdot 3.
• Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
• Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

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

• Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
• Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
• Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
• Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} – общее кратное чисел aa и bb;
• Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
• Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).