Олимпиадная задача: Число простых делителей суммы и слагаемых (Жуков Г.)
Задача
Пусть C(n) – количество различных простых делителей числа n.
а) Конечно или бесконечно число таких пар натуральных чисел (a, b), что a ≠ b и C(a + b) = C(a) + C(b)?
б) А если при этом дополнительно требуется, чтобы C(a + b) > 1000?
Решение
а) См. задачу 216818. б) Рассмотрим число P, равное произведению p1p2...pn первых n простых чисел (n > 1000). P – наименьшее число, у которого n простых делителей. Пусть C(P – 1) = n – k. Рассмотрим число Q, равное произведению k различных простых чисел, каждое из которых больше pn и всех простых делителей числа P – 1. Возьмём a = Q, b = (P – 1)Q. Имеем C(a) = k, C(b) = n, C(a + b) = C(PQ) = n + k.
Ответ
Бесконечно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет