Определение наибольшего общего делителя (НОД)

 

Наибольшим общим делителем нескольких чисел называется число, которое является делителем каждого из них. То есть это наибольшее число, на которое оба числа a и b делятся без остатка.

Например:

Найдем НОД (21, 14, 42) = 7. Каждое из чисел 21, 14, 42 делится на 7 без остатка и это наибольший общий делитель.

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

 

Рассмотрим, как найти НОД на примере.

Чтобы найти НОД нескольких чисел надо (найти НОД (180, 150)):

 

Шаг 1

Представить каждое число в виде простых множителей:

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

Шаг 2

Записать степени всех простых множителей.

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

Шаг 3

Выписать все общие делители (множители) этих чисел.

Шаг 4

Выбрать наименьшую степень каждого из них, встретившуюся во всех произведениях.

Наименьшая степень общих делителей 2, 3 и 5.

 

Шаг 5

Перемножить эти степени.

Перемножим 2, 3 и 5:

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

Итак,

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

то есть на 30 можно разделить каждое число:

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

Пример 1

 

Найти наибольший общий делитель (НОД) чисел 252, 30, 1512.

 

Шаг 1

Представим каждое число в виде простых множителей:

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

Шаг 2

Где возможно, запишем степени полученных множителей:

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

Шаг 3

Выпишем все общие делители:

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

Шаг 4

Выберем наименьшую степень каждого из них: это 21 и 31.

Шаг 5

Перемножим эти степени:

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

Итак, мы нашли наибольший общий делитель:

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

То есть на 6 можно разделить каждое число без остатка:

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

Пример 2

 

Найдем НОД чисел 1050, 630, 2205.

 

Шаг 1

Разложим каждое число на множители:

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

Шаг 2

Где возможно, запишем степени полученных множителей:

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

Шаг 3

Выпишем все общие делители:

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

Шаг 4

Выберем наименьшую степень каждого из них: это 31, 51 и 71.

Шаг 5

Перемножим их:

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

Итак, мы нашли наибольший общий делитель:

НОД (1050, 630, 2205) = 105, то есть на 105 можно разделить каждое число без остатка.