Простые делители (задача Г. Жукова в моей переработке)

[Ktina]

Пусть $C(n)$ – количество различных простых делителей числа $n$.
Например, $C(10)=2,\quad C(11)=1,\quad C(12)=2$
а) Конечно или бесконечно число таких пар натуральных чисел $(a, b)$, что $a\ne b$ и $C(a+b)=(C(a)+C(b))^2$?
б) А если при этом дополнительно требуется, чтобы $C(a+b)>1000$?

[Red_Herring]

Чем-то это мне напоминает индо-пакистанский инцидент….


$\rotatebox{180}{Турнир Городов осень 2012, базовый вариант: а) младшие и старшие б) только старшие}}$

[Ktina]

Red_Herring
Только зря он шутит с нашим братом,
У меня есть мера, даже две.
В той задаче не было квадрата,
В этой - ход конем по голове!

[Руст]

Бесконечно много.
Берем вначале два произвольных взаимно простых числа $a_0, b_0$.
Возьмем некоторую степень n b и новое взаимно простое с $a_0,b_0$ число с
и рассмотрим числа $a=(a_0c)^n,b=(a_0c)^n$.
Пусть $m=C(a_0^n+b_0^n)$ При выборе c можем взять k простых делителей $a_0^n+b_0^n$ и взаимно простым с $a_0*b_0$
и произвольные l других простых делителей.
Тогда уравнение получается $m+l=(C(a_0)+C(b_0)+2k+2l))^2.$
За счет выбора нечетного n с большим количеством делителей число m можно сделать как угодно большой, хоть миллион.
Далее за счет выбора k и l можно удовлетворить уравнению.

[Ktina]

Руст
Спасибо!

У меня к пункту а) имеется довольно простое решение, доступное пятиклассникам. Немного позже опубликую его.

[Red_Herring]

Ну, по (а) решение совсем простое: $a=41^m, b=41^{m+1}, C(a)=C(b)=1, C(a+b)=4.$

Цитата:

За счет выбора нечетного n с большим количеством делителей число m можно сделать как угодно большой, хоть миллион.

А можно ли ссылку на теорему? Заметим что $a_0, b_0$ фиксированы до выбора $n$

[Руст]

Red_Herring в сообщении #827696 писал(а):

А можно ли ссылку на теорему? Заметим что $a_0, b_0$ фиксированы до выбора $n$

Некоторые ссылаются на Зигмундов теорему. Но это почти очевидно.
Для взаимно простых x,y (xy>1) обозначим через $\Phi_m(x,y)=\prod_{d|n}(x^d+y^d)^{\mu(\frac{m}{d})}$ (круговой многочлен).
Все такие числа за исключением одного случая, когда $xy=2,m=1,3$ не имеют общих простых делителей.
Соответственно $x^n+y^n=\prod_{m|n}\Phi_m(x,y)$ имеет как минимум $\tau(n)$ (количество делителей числа n, который можно сделать сколько угодно) различных простых делителей. В исключительном случае гарантируем только на одно меньше.

Да здесь $n$ нечетно, иначе надо брать разницы степеней.

[Red_Herring]

А что такое функция $\mu$?

[Руст]

$\mu(n)=0$, если n делится на некоторый квадрат простого числа, иначе
$\mu(p_1*...p_k)=(-1)^k$. Это называется функцией Мёбиуса и используется в комбинаторике для подсчета через исключения.

[Ktina]

Red_Herring в сообщении #827696 писал(а):

Ну, по (а) решение совсем простое: $a=41^m, b=41^{m+1}, C(a)=C(b)=1, C(a+b)=4.$

Или 29 вместо 41

[Red_Herring]

Руст в сообщении #827720 писал(а):

$\mu(n)=0$, если n делится на некоторый квадрат простого числа, иначе
$\mu(p_1*...p_k)=(-1)^k$. Это называется функцией Мёбиуса и используется в комбинаторике для подсчета через исключения.

Спасибо...Забыл… что-то с памятью моей стало

http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D1%83%D0%B3%D0%BE%D0%B2%D0%BE%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D0%BD

[Руст]

Часто удобнее работать круговым многочленом от двух переменных. Связь между ними простая:
$\Phi_m(x,y)=y^{\phi(m)}\Phi(-\frac{x}{y})$. Опять таки я определял специально для нечетных степеней.