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

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

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

Существует несколько алгоритмов нахождения НОД. Рассмотрим их.

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

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

• разложить эти числа на простые множители;
• выписать те множители, которые входят в разложение каждого из чисел;
• найти произведение этих множителей.

Пример: найти НОД(100;250)

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

   

   Подробнее о разложении чисел на простые множители, смотрите тут

2. Ищем одинаковые цифры и получаем 2, 5, 5
3. Перемножаем эти цифры и получаем 2 · 5 · 5 = 50

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

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

1. Большее число разделить на меньшее;
2. Если большее число делится на меньшее без остатка — то меньшее будет НОД;
3. Если есть остаток — то то большее число заменяем на остаток от деления;
4. Повторяем пункты 1-3

Пример: реализуем предыдущий пример НОД(100;250), разобранным алгоритмом:

• 250 : 100 = 2 (остаток 50);

  Согласно алгоритму 250 меняем на остаток 50, получаем 100 и 50. Возвращаемся к 1 пункту и продолжаем вычисления, пока остаток не будет равен 0.

• 100 : 50 = 2 (остаток 0);

Ответ: НОД(100;250) = 50

Пример: найти НОД(150;280)

• 280 : 150 = 1 (130)
• 150 : 130 = 1 (20)
• 130 : 20 = 6 (10)
• 20 : 10 = 2 (0)

Ответ: НОД(150;280) = 10