Нахождение наибольшего общего делителя и наименьшего общего кратного способом разложения на простые множители

Если натуральные числа а и в представлены в каноническом виде, то над ними легко выполнять умножение, деление, возведение в степень.

Пусть ,

.

.

, для a_к ≥ b _к,при к = 1, 2, …, n.

Из последнего равенства следует, что число d может быть общим делителем чисел а и в лишь в том случае, когда показатель степени каждого простого числа в разложении d не превосходит соответствующих показателей в числах а и в.

Иными словами при условии, что для любого к
(1 ≤ к ≤ n) будут выполняться неравенства g_к ≤ a_к и g_к ≤ b _к. НОД (а, в) – это наибольшее из чисел на которое делятся числа а и в. Значит, для каждого из простых чисел показатель степени в разложении НОД (а, в) должен быть наибольшим из возможных (т.е. удовлетворяющих неравенствам g_к ≤ a_к и g_к ≤ b _к). Этим показателем является меньшее из чисел a_к и b _к. Таким образом, чтобы найти НОД чисел, представленных в каноническом виде, достаточно образовать произведение общих всем данным числам простых множителей, каждый с наименьшим показателем, с каким он входит во все разложения данных чисел, и найти его значение.

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

П р и м е р. Найти НОК и НОД чисел 504 и 132

504 = 2³ ·3² · 7; 132 = 2² · 3 ·11.

НОД (504, 132) = 2² · 3 · 7⁰ · 11⁰ =12,

НОК (504, 132) = 2³ · 3² · 7 · 11 = 5544.

Дата добавления: 2015-07-18