Gelioxis.ru
Натуральные числа и действия над ними Устная нумерация Натуральные числа Арифметические действия Сложение натуральных чисел Законы сложения Свойства сложения Сложение столбиком Вычитание натуральных чисел Свойства вычитания Умножение Законы умножения Деление Признаки делимости чисел Простые и составные числа Разложение числа на простые множители Проверка арифметических действий Проверка сложения и вычитания Изменение результатов действий Изменение суммы Изменение разности Системы счисления Римская система счисления Общие делители и кратные Наибольший общий делитель Как найти НОД Наименьшее общее кратное

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

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

Метод разложения на простые множители

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

Пример.

Найти НОД (120, 252).

Решение. Раскладываем числа 120 и 252 на простые множители:

Поиск НОД методом разложения на простые множители

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

1 · 22 · 3 = 12.

Ответ: НОД (120, 252) = 12.

Пример.

Найти НОД (8, 9).

Решение. Раскладываем 8 и 9 на простые множители:

Поиск НОД методом разложения на простые множители

Числа 8 и 9 являются взаимно простыми, поэтому их наибольший общий делитель — единица.

Ответ: НОД (8, 9) = 1.

Метод последовательного деления (алгоритм Евклида)

Чтобы найти НОД двух натуральных чисел нужно:

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

Пример.

Найти НОД (12, 24).

Решение. Так как 24 делится на 12, то число 12 является НОД чисел 12 и 24.

Ответ: НОД (12, 24) = 12.

Пример.

Найти НОД (210, 72).

Решение. Делим большее число на меньшее:

1) 210 : 72 = 2 (остаток 66).

Делим меньшее число на остаток:

2) 72 : 66 = 1 (остаток 6).

Делим первый остаток на второй:

3) 66 : 6 = 11 (остаток 0).

Последний делитель равен 6, значит НОД (210, 72) = 6.

Ответ: НОД (210, 72) = 6.

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

Пример.

Найти НОД (120, 252, 42).

Решение. Сначала найдём НОД каких-нибудь двух чисел, например, 120 и 252:

1) 252 : 120 = 2 (остаток 12);

2) 120 : 12 = 10 (остаток 0).

НОД (120, 252) = 12. Теперь найдём НОД найденного наибольшего делителя (12) и оставшегося третьего числа (42):

1) 42 : 12 = 3 (остаток 6);

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

Последний делитель равен 6, значит НОД (120, 252, 42) = 6.

Ответ: НОД (120, 252, 42) = 6.