Сколько существует упорядоченных пар натуральных чисел a и b, для которых известны их наибольший общий делитель d=6 и их наименьшее общее кратное m=6930. Сформулируйте ответ и в общем случае, используя канонические разложения d и m на простые множители.
- Решение
Решение
Разложим числа m и d на простые множители: d=6=2·3; m=6930=2·3·3·5·7·11. Обозначим буквой t число m/d, равное произведению 3·5·7·11 . Найдем все его делители q вида: q=3x5y7z11u, где числа x, y, z и u принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа q и t/q окажутся взаимно простыми. Полагая а=dq и b=dt/q, получим все искомые пары (a,b). В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен d, а ее наименьшее общее кратное равно dqt/q=dt=dm/d=m. Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей q вида: 3x5y7z11u, которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно 24=16, так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число m/d представляется в виде m/d=pirj... sh, где p, r, ..., s - различные простые числа, а i, j, ..., h - натуральные числа. Число всех делителей вида: q=pxry... sz, где числа x, y, ..., z принимают только по два значения (0 и соответствующий натуральный показатель степени в представлении числа m/d), равно 2k, где k - число всех простых делителей числа m/d. Если число различных простых множителей в каноническом разложении числа m/d равно k, то число различных упорядоченных пар (a,b) равно 2k.
- Ответ
Ответ
16 пар (пары (a,b) и (b,a) разные). В общем случае число упорядоченных пар равно 2k, где k - число всех простых делителей m/d.