Наибольший Общий Делитель в деталях

Умение определять самый общий делитель — одно из основных для работы с дробями. НДС может пригодиться и для решения линейных уравнений.

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

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

Для записи этой конструкции используется обозначение НОД(а;b). Например: наибольшим общим делителем для чисел 18 и 24 будет число 6. В рабочую тетрадь это записывается следующим образом: НОД (18; 24) = 6.

Определение самого крупного общего делителя (НОД). Методы нахождения

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

количество чисел;
размер этих чисел;
собственные предпочтения.

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

Метод множителей

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

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

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

Метод последовательных чисел. Таблица простых чисел

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

Использование алгоритма Евклида

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

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

Приложили применение алгоритмов поиска НСД

Попробуем найти самый общий делитель для чисел 24 и 36 методом множителей. Разлагаем 24 на простые множители: 2 х 3 х 4. Раскладываем 32 на обычные множители: 3 х 3 х 4. Совместные множители для двух чисел - 3 и 4. 3 х 4 = 12. НСД (24; 36) = 12.

Найдем НДС для 11 и 38. Используем для этого второй способ – таблицу простых чисел. Как видим, число 11 находится в этой таблице. То есть НДД (11; 38) = 1.

Используем алгоритм Евклида для чисел 36 и 56.

Берем число 36.

Делим: 56/36 = 1 (остаток 20).

Далее делим: 36/20 = 1 (остаток 16).

Делим еще: 20/16 = 1 (остаток 4).

16/4 = 4.

После ряда действий деления, мы получили число без остатка. Следовательно, НДД (36; 56) = 4.

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