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

Наибольшим общим делителем (НОД) нескольких чисел называется наибольшее натуральное число, на которое без остатка делятся эти числа. Например, для чисел 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. Найти наибольший общий делитель чисел 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 > r1 > r2 > r3 > ... > rn в соответствии с формулами

a = b*q0 + r1, где r1 – остаток от деления a на b;

b = r1*q1 + r2, где r2 – остаток от деления b на r1;

r1 = r2*q2 + r3, где r3 - остаток от деления r1 на r2;

...

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

rn-1 = rn*qn;

НОД(a,b) = rn.

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

Примеры.

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

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

Copyright © 2018 Intemodino Group s.r.o.
Все права защищены