Архив метки: Общий наибольший делитель

§ 13. Общий наибольший делитель

Общим делителем нескольких чисел называется число, служащее делителем для каждого из них.

Например, числа 12, 18, 30 имеют общий делитель 3; число 2 — тоже их общий делитель. Среди всех общих делителей всегда имеется наибольший, в нашем примере — число 6. Это число называется Общим Наибольшим Делителем (О.Н.Д.).

Примеры.
Для чисел 16, 20, 28 О.Н.Д. есть 4;
для чисел 5, 30, 60, 90 О.Н.Д. есть 5.

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

Пример 1.
Найти О.Н.Д. чисел 252, 441, 1080.
Разлагаем на простые множители
252 = 2²*3²*7;
441=3²*7²;
1080=2³*3³*5

Общим для чисел является только простой множитель 3; наименьший из показателей, с которыми он входит в данные числа, есть 2, О.Н.Д. равен 3³=9

Пример 2.
Найти О.Н.Д. чисел 234, 1080, 8100.
234 = 2*3²*13;
1080 = 2³*3³*5;
8100 = 2²*3*3³*5²;
О.Н.Д. = 2*3²= 18.

Может случиться, что простых множителей, общих для всех данных чисел, не будет вовсе. Тогда общий наибольший делитель есть 1. Например, для чисел 15 = 3*5, 10 = 2*5, 6 = 2*3 О.Н.Д. = 1. Два числа, О.Н.Д. которых равен 1, называются взаимно простыми. Например, 15 и 22 — взаимно простые числа.