Как найти нод произведения чисел

Как найти НОД

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

НОК и НОД

Рассмотрим выражение:

(45:9)

Можем сказать, что 45 – делимое, а 9 – делитель данного выражения.

Мы знаем, что 45 делится нацело на число 9. В таком случае, если мы захотим описать, чем эти числа являются друг другу, то мы скажем, что

9 – делитель числа 45

45 – кратно числу 9

Иногда при решении задач нужно находить общие кратные или общие делители двух чисел.

Наименьший делитель двух чисел – всегда единица. Такой делитель нет смысла искать, поэтому ищут наибольший общий делитель.

А кратных наоборот – бесконечно много, невозможно искать наибольшее из них, поэтому ищут, наименьшее общее кратное.

НОД:

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

Пример №1:

Рассмотрим числа 30 и 45.

1. Найдем все их существующие делители, т.е. числа, на которые каждое из них поделится нацело:

1. Мы видим, что у этих двух чисел есть несколько общих делителей. Наибольший из них – 15 – является самым большим. Это и есть НОД.

Значит и число 45 и число 30 можно нацело поделить на 15. Записывают это так:

(НОД (30;45) = 15)

Ответ: 15.

Пример №2:

Найдем (НОД (20;36):)

1. Выпишем все делители этих чисел.

Так же делители можно сразу записывать парой. Если 20 нацело делится на 2, то

(20 : 2 = 10)

Значит 10 – тоже делитель числа 20. Запишем делители 2 и 10 парой:

1. Выделим все общие делители и найдем наибольший из них. В данном случае

(НОД(20;35) = 4.)

Ответ: 4.

НОК:

Наименьшее общее кратное (НОК) двух чисел – это наименьшее число, которое можно поделить на каждое из этих чисел без остатка.

Пример №3:

Найдем (НОК (10;12).)

1. Возьмем наименьшее число. В данном случае – 10.

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

(10 bullet 1 = 10; 10 НЕ кратно 12)

(10 bullet 2 = 20; 20 НЕ кратно 12)

(10 bullet 3 = 30; 30 НЕ кратно 12)

(10 bullet 4 = 40; 40 НЕ кратно 12)

(10 bullet 5 = 50; 50 НЕ кратно 12)

(10 bullet 6 = 60; 60 кратно 12)

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

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

Ответ: 60.

Также можно находить НОК через разложение на множители:

Пример №4:

Найдём (НОК (6;8):)

1. Разложим числа 6 и 8 на простейшие множители, т.е. представим каждое число как произведения простых чисел. Множители большего числа запишем сверху:

8: (1 bullet 2 bullet 2 bullet 2)

6: (1 bullet 2 bullet 3)

1. Видим, что множители 1 и 2 повторяются у обоих чисел, поэтому для меньшего числа их уберем. Останется:

1. Перемножим все оставшиеся числа. Их произведение и будет НОК:

(НОК (6; = 1 bullet 2 bullet 2 bullet 2 bullet 3 = 24)

Ответ: 24.

Пример №5:

Найдем (НОК (10;12)) разложением на множители:

1. Разложим оба числа на простые множители. Сверху запишем большее число:

12: 1, 2, 2, 3

10: 1, 2, 5

1. Для меньшего числа зачеркнем те множители, которые уже есть у большего числа:

1. Перемножим все оставшиеся числа:

(НОК (10; 12) = 1 bullet 2 bullet 2 bullet 3 bullet 5 = 60)

Наш ответ совпал с ответом, где мы использовали метод подбора.

Ответ: 60.

ВЗАИМОСВЯЗЬ НОК И НОД:

Произведение НОК и НОД некоторых чисел равно произведению самих этих чисел:

(НОК(a; b) bullet НОД(a; b) = a bullet b)

Докажем эту формулу на примере.

Пример №6:

Рассмотрим пару чисел 24 и 60.

1. Найдем их НОД:

(НОД (24;60) = 12)

1. Найдем их НОК:

(НОК (24; 60) = 1 bullet 2 bullet 2 bullet 2 bullet 3 bullet 5 = 120)

1. Рассмотрим поближе НОК. Чтобы его получить, мы переменожили все простые множители чисел 60 и 24 за исключением множителей 1, 2, 2, 3. Найдем отдельно их произведение:

(1 bullet 2 bullet 2 bullet 3 = 12)

Если перемножить все простые множители числе 60 и 24 мы получим просто их произведение, при этом оно будет состоять из НОК и числа 12, которое в свою очередь равно НОД:

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

Определение наибольшего общего делителя

Делитель натурального числа a – это такое натуральное число b, которое делит a нацело (без остатка). Обозначается буквой Д. Например Д(6) означает “делитель числа 6”.

Если у числа больше двух делителей, его называют составным.

Примеры делителей:

• Число 12 имеет следующие делители: 1, 2, 3, 4, 6.
• Число 15 имеет следующие делители: 1, 3, 5.

В отличие от кратных, количество делителей числа ограничено.

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

Наибольший общий делитель двух натуральных чисел – наибольшее число из общих делителей данных чисел. Обозначается как НОД.

Например, НОД (12, 24) – это наибольший общий делитель чисел 12 и 24.

Нахождение НОД

Чтобы найти наибольший общий делитель, можно применить один из способов ниже.

Для двух (или небольших) чисел

1. Записываем в ряд все делители для каждого числа (по возрастанию).
2. Находим наибольшее значение, встречающееся в обоих рядах. Это и есть НОД.

Пример
Найдем наибольший делитель чисел 18 и 30.

Решение
Д(18): 1, 2, 3, 6, 9.
Д(30): 1, 2, 3, 5, 6, 10, 15.

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

Для нескольких (или больших) чисел

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

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

Пример
Найдем НОД (16, 24, 40).

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

Для всех трех чисел одинаковыми являются три множителя – это три двойки.

Следовательно, НОД (16, 24, 40) = 2 ⋅ 2 ⋅ 2 = 8.