Наибольший общий делитель

Общий делитель. Наибольший общий делитель .

Общим делителем нескольких чисел называется число, которое является делите-лем каждого из них. Например, числа 36, 60, 42 имеют общие делители 2, 3 и 6. Среди всех общих делителей всегда есть наибольший, в данном случае это 6. Это и есть наибольший общий делитель (НОД).

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

1)  представить каждое число как произведение его простых множителей , например:

360 = 2 · 2 · 2 · 3 · 3 · 5 ,

2)  записать степени всех простых множителей :

360 = 2 · 2 · 2 · 3 · 3 · 5 = 2

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

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

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

П р и м е р .  Найти НОД чисел: 168, 180 и 3024.

Р е ш е н и е .   168 = 2 · 2 · 2 · 3 · 7 = 2

180 = 2 · 2 · 3 · 3 · 5 = 2

3024 = 2 · 2 · 2 · 2 · 3 · 3 · 3 · 7 = 2

Выпишем наименьшие степени общих делителей 2 и 3

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

НОД = 2