Пример как найти нод двух натуральных чисел

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

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

Делитель натурального числа 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.

Как найти НОД

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

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

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

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

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

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

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

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

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

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

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

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