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

Понятие

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

Самый простой способ нахождения НОД

Существует несколько способов нахождения НОД.

Самым распространенным в математике является способ при помощи разложения чисел на простые множители.

Алгоритм

— разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);

— выбрать одинаковые множители, входящие в оба разложения;

— найти их произведение.

Как разложить числа на простые множители, Вы можете ознакомиться здесь

Примеры решения

Найти НОД 18 и 9. Раскладываем 18 и 9 на простые множители:

18 = 2 · 3 · 3

9 = 3 · 3

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

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

Ответ: НОД (9; 18) = 3 · 3 = 9

2. Найти НОД 225 и 255

Раскладываем 225 и 255 на простые множители:

225 = 3 · 3 · 5 · 5

255 = 3 · 5 · 17

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

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

Ответ: НОД (225; 255) = 3 · 5 = 15

Способ Евклида

Есть два варианта. Первый — это нахождение НОД при помощи деления, а второй – при помощи вычитания.

Нахождение НОД при помощи деления

Рассмотрим первый вариант.

Данный способ позволяет найти НОД через последовательное деление.

Пример: Найти НОД для чисел 18 и 48

48 : 18 = 2 (остаток 12)

18 : 12 = 1 (остаток 6)

12 : 6 = 2 (остаток 0)

Последний делитель или последний, отличный от 0 остаток будет являться искомым НОД. В данном случае это 6.

НОД (18; 48) = 6

Алгоритм:

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

Нахождение НОД при помощи вычитания

Пример: Найти НОД для чисел 14 и 21

21 — 14 = 7

14 – 7 = 7

7 – 7 = 0

НОД (14; 21) = 7

Алгоритм:

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

Взаимно простые числа

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

Например, нам необходимо найти НОД для чисел 3 и 5.

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

3 = 3

3 это простое число, так как оно делится на сумо себя и на 1. О простых и составных числах, Вы можете ознакомиться тут

5 = 5

Тоже самое можно сказать о 5, это простое число.

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

НОД трех чисел

Рассмотрим на примере.

НОД (325; 75; 50) — ?

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

325 = 5 ∙ 5 ∙ 13

75 = 5 ∙ 5 ∙ 3

50 = 2 ∙ 5 ∙ 5

Затем выберем какое-либо разложение их этих трех. Например, разложение числа 75. Будем вычеркивать те множители, которых нет в других двух разложениях.

Рассмотрим множитель 5. Он есть в первом разложении и в третьем. Оставляем его ∨

Рассмотрим второй множитель 5, он также есть в первом и в третьем разложении. Тоже его оставляем ∨

Следующий множитель 3. Его мы вычеркиваем, так как его нет ни в первом, ни в третьем разложении ×

Далее, НОД чисел 325, 75 и 50 мы получим, перемножив оставшиеся множители у выбранного числа 75.

НОД (325; 75; 50) = 5 ∙ 5 = 25

Нахождение НОД трех чисел, Вы можете посмотреть на видео