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

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

Чтобы найти НОД нескольких чисел, нужно:
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. Найти наибольший общий делитель чисел 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.

Пример 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.

Пример 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.

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

Кроме указанного способа нахождения НОД нескольких чисел, существует алгоритм Евклида нахождения наибольшего общего делителя двух чисел 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.

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

Примеры.

Пример 1. С помощью алгорима Евклида найти наибольший общий делитель чисел 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.

Пример 2. С помощью алгорима Евклида найти наибольший общий делитель чисел 126 и 900.

900 = 126*7 + 18; (900 делим на 126, в остатке 18)

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

Cледовательно, НОД(126, 900) = 18.

Пример 3. С помощью алгорима Евклида найти наибольший общий делитель чисел 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.

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