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

Наибольшим общим делителем (НОД) нескольких чисел называется наибольшее натуральное число, на которое без остатка делятся эти числа. Например, для чисел 18 и 30 наибольший общий делитель равен 6; для чисел 10, 15, 45 наибольший общий делитель равен 5.

Нахождение наибольшего общего делителя

Чтобы найти НОД нескольких чисел, нужно:
1) разложить эти числа на простые множители;
2) отметить те множители, которые входят в разложение всех чисел;
3) найти произведение отмеченных множителей в разложении любого из заданных чисел.

Примеры.

Пример 1.
Найти наибольший общий делитель чисел 48, 18, 16.
Решение.
Выпишем разложения на простые множители для заданных чисел и подчеркнем те множители, которые входят в разложения всех чисел:
48 = 2*2*2*2*3,

18 = 2*3*3,

16 = 2*2*2*2.
Cледовательно, НОД(48, 18, 16) = 2.
Ответ: 2.

Пример 2.
Найти наибольший общий делитель чисел 120, 45, 150.
Решение.
Выпишем разложения на простые множители для заданных чисел и подчеркнем те множители, которые входят в разложения всех чисел:
120 = 2*2*2*3*5,

45 = 3*3*5,

150 = 2*3*5*5.
Cледовательно, НОД(120, 45, 150) = 3*5=15.
Ответ: 15.

Пример 3.
Найти наибольший общий делитель чисел 324, 432.
Решение.
Выпишем разложения на простые множители для заданных чисел и подчеркнем те множители, которые входят в разложения всех чисел:
324 = 2*2*3*3*3*3,

432 = 2*2*2*2*3*3*3.
Cледовательно, НОД(324, 432) = 2*2*3*3*3=108.
Ответ:108.

Пример 4.
Найти наибольший общий делитель чисел 48, 60, 80.
Решение.
Выпишем разложения на простые множители для заданных чисел и подчеркнем те множители, которые входят в разложения всех чисел:
48 = 2*2*2*2*3,

60 = 2*2*3*5,

80 = 2*2*2*2*5.
Cледовательно, НОД(48, 60, 80) = 2*2=4.
Ответ: 4.

Алгоритм Евклида нахождения наибольшего общего делителя двух чисел

Кроме указанного способа нахождения НОД нескольких чисел, существует алгоритм Евклида нахождения наибольшего общего делителя двух чисел a и b (a > b). Его можно описать так:
получаем цепочку чисел a > b > r₁ > r₂ > r₃ > ... > r_n в соответствии с формулами

a = b*q₀ + r₁, где r₁ – остаток от деления a на b;

b = r₁*q₁ + r₂, где r₂ – остаток от деления b на r₁;

r₁ = r₂*q₂ + r₃, где r₃ - остаток от деления r₁ на r₂;

...

r_n-2 = r_n-1*q_n-1 + r_n, где r_n – остаток от деления r_n-2 на r_n-1;

r_n-1 = r_n*q_n;

НОД(a,b) = r_n.

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

Примеры.

Пример 5.
С помощью алгорима Евклида найти наибольший общий делитель чисел 48 и 18.
Решение.
48 = 18*2 + 12; (48 делим на 18, в остатке 12)

18 = 12*1 + 6; (18 делим на 12, в остатке 6)

12 = 6*2; (12 делим на 6, в остатке 0, последний делитель и есть НОД).
Cледовательно, НОД(48, 18) = 6.
Ответ: 6.

Пример 6.
С помощью алгорима Евклида найти наибольший общий делитель чисел 126 и 900.
Решение.
900 = 126*7 + 18; (900 делим на 126, в остатке 18)

126 = 18*7; (126 делим на 18, в остатке 0, последний делитель и есть НОД)
Cледовательно, НОД(126, 900) = 18.
Ответ: 18.

Пример 7.
С помощью алгорима Евклида найти наибольший общий делитель чисел 495 и 270.
Решение.
495 = 270*1 + 225; (495 делим на 270, в остатке 225)

270 = 225*1 + 45; (270 делим на 225, в остатке 45)

225 = 45*5; (225 делим на 45, в остатке 0, последний делитель и есть НОД)
Cледовательно, НОД(495, 270) = 45.
Ответ: 45.

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