Как найти НОД

В этой теме разберём нахождение НОД методом разложения на множители, а также с помощью алгоритма Евклида.

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

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

Возьмём для примера пару чисел.

1.                Найдём наибольший общий делитель для чисел 24 и 18. Для начала разложим их на простые множители:

24 = 2 ∙ 2 ∙ 2 ∙ 3; 18 = 2 ∙ 3 ∙ 3.

Выделенные числа, которые встречаются среди множителей у двух чисел, перемножим для нахождения НОД: НОД = 2 ∙ 3 = 6.

То есть НОД (24; 18) = 6.

2.                Найдём НОД также и для пары чисел 54 и 56. Разложим на множители:

Таким образом: 54 = 2 ∙ 3 ∙ 3 ∙ 3 и 56 = 2 ∙ 2 ∙ 2 ∙ 7.

Так как только одна цифра встречается среди множителей двух чисел, то она и будет ответом.

НОД (54; 56) = 2.

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

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

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

То есть мы сразу нашли ответ делением большего числа на меньшее:

НОД (81; 9) = 9.

Для двух чисел есть следующий алгоритм нахождения наибольшего общего делителя:

1.                Всегда из двух чисел выбирают большее и затем делят на меньшее из двух.

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

3.                Далее число, на которое мы делили до этого, становится делимым, а найденный остаток — делителем.

4.                Так продолжается до тех пор, пока не получим нуль в остатке. А последний делитель (предпоследний получившийся остаток) записывается в ответ как искомый НОД.

Для нахождения общего делителя для трёх чисел нужно придерживаться следующего порядка действий:

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

2)                Далее найдём НОД для общего делителя и третьего числа.

3)                После, если чисел больше трёх, нужно продолжить второе действие для четвёртого числа. И так продолжать для всех оставшихся чисел, сколько бы их ни было.