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

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

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


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

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

Business Contact Book - Premium Contact Manager
Copyright © 2022 Intemodino Group s.r.o.
Все права защищены