Вычисление НОК и НОД
Для отыскания наибольшего общего делителя двух натуральных чисел следует выполнить следующие операции:
1) разложить каждое из данных чисел на простые множители;
2) найти произведение простых множителей, входящих в каждое из данных чисел.
Если какой-то простой множитель входит в эти разложения в разных степенях, то в наибольший общий делитель он входит в наименьшей из этих степеней. Если нет ни одного простого множителя, входящего в оба рассматриваемых числа, то наибольший общий делитель равен единице.
Для разложения числа на простые множители применяем следующий прием:
а) подбираем наименьшее простое число, на которое делится данное число;
б) представляем данное число как произведение найденного простого множителя и некоторого натурального числа;
в) повторяем пункты а) и б) для нового натурального числа до тех пор, пока оно не станет равным единице.
Для нахождения наименьшего общего кратного двух натуральных чисел следует выполнить следующие операции:
1) разложить каждое из данных чисел на простые множители;
2) найти произведение простых множителей, входящих в разложение хотя бы одного из чисел.
Если какой-то простой множитель входит в эти разложения в разных степенях, то в наименьшее общее кратное он входит в наибольшей из этих степеней.
СВОЙСТВО: НОК(А, В)*НОД(А, В)=А*В
