Задача 116825

Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4- Классы: 10,11

Условие

Автор: Жуков Г.

Пусть C(n) – количество различных простых делителей числа n.
  а) Конечно или бесконечно число таких пар натуральных чисел  (a, b),  что  a ≠ b  и  C(a + b) = C(a) + C(b)?
  б) А если при этом дополнительно требуется, чтобы  C(a + b) > 1000?

Решение

   а) См. задачу 116818.

   б) Рассмотрим число P, равное произведению p₁p₂...p_n первых n простых чисел  (n > 1000).  P – наименьшее число, у которого n простых делителей. Пусть  C(P – 1) = n – k.  Рассмотрим число Q, равное произведению k различных простых чисел, каждое из которых больше p_n и всех простых делителей числа  P – 1.  Возьмём  a = Q,  b = (P – 1)Q.  Имеем  C(a) = k,  C(b) = n,  C(a + b) = C(PQ) = n + k.

Ответ

Бесконечно.

Замечания

баллы: 2 + 3

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	2012/13
Номер	34
вариант
Вариант	осенний тур, базовый вариант, 10-11 класс
Задача
Номер	4