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

Общим делителем нескольких чисел называется число, которое является делите-лем каждого из них. Например, числа  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² · 5¹,

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

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

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

 

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

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

                          180 = 2 · 2 · 3 · 3 · 5 = 2²  · 3²  · 5¹ ,

                          3024 = 2 · 2 · 2 · 2 · 3 · 3 · 3 · 7 = 2⁴  · 3³  · 7¹ .

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

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

НОД = 2²  · 3¹  = 12 .