Азиатско-Тихоокеанская математическая олимпиада, 2023 год


Найдите все натуральные числа $n \ge 2$ такие, что $\frac{\sigma(n)}{p(n)-1} = n$. Здесь через $\sigma(n)$ обозначена сумма всех натуральных делителей числа $n$, а через $p(n)$ — наибольший простой делитель числа $n$.
посмотреть в олимпиаде

Комментарий/решение:

  2
2024-06-14 20:25:54.0 #

$n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{k}^{a_{k}}$

Тогда, пусть $p_k>p_{k-1}>...>p_1$

$\frac{\sigma(n)}{p(n)-1}=\frac{(1+p_1+p_1^2+...+p_1^{a_1})(1+p_2+p_2^2+...+p_2^{a_2})...(1+p_k+p_k^2+...+p_k^{a_k})}{p_k-1}=\frac{(p_1^{a_1+1}-1)(p_2^{a_2+1}-1)...(p_k^{a_k+1}-1)}{(p_1-1)(p_2-1)...(p_k-1)(p_k-1)}=n<\frac{p_1^{a_1+1}p_2^{a_2+1}...p_k^{a_k+1}}{(p_1-1)(p_2-1)...(p_k-1)(p_k-1)}$

Значит тк $n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{k}^{a_{k}}$ и $n=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{k}^{a_{k}}<\frac{p_1^{a_1+1}p_2^{a_2+1}...p_k^{a_k+1}}{(p_1-1)(p_2-1)...(p_k-1)(p_k-1)}$

$\frac{p_1p_2...p_k}{(p_1-1)(p_2-1)...(p_k-1)(p_k-1)}>1$

$\frac{p_1}{p_2-1}*\frac{p_2}{p_3-1}*...*\frac{p_{k-1}}{p_k-1}*\frac{p_k}{(p_k-1)(p_1-1)}>1$

Теперь заметим следующее:

$\frac{p_1}{p_2-1}\leq 1$, тк $p_1<p_2 => p_1\leq p_2-1$

$\frac{p_2}{p_3-1}< 1$, тк $p_2<p_3 => p_2\leq p_3-1$, а также $p_2>p_1\geq 2 => p_2\geq 3$ Поэтому между $p_2$ и $p_3$ минимум разница = 2.

и так далее делаем.

Рассмотрим $\frac{p_k}{(p_k-1)(p_1-1)}$. Оно больше 1 иначе вся дробь $\leq 1$, тогда противоречие. Значит $\frac{p_k}{p_k-1}>p_1-1$. При $p_1\geq 3$, $\frac{p_k}{p_k-1}>p_1-1\geq 2$. Но тогда $p_k>2p_k-2$, ну а отсюда, $p_k<2$, противоречие. Значит $p_1=2$

$\frac{2p_2...p_k}{(2-1)(p_2-1)...(p_k-1)(p_k-1)}>1$

Делаем тоже самое - начиная с $p_2$, все дроби вида $\frac{p_i}{p_{i+1}-1}<1$

Точно также, $\frac{2p_k}{(p_2-1)(p_k-1)}>1$

Значит, $2p_k>(p_2-1)(p_k-1)$

Если $p_2\geq 5$, то $p_2-1\geq 4$

$2p_k>(p_2-1)(p_k-1)\geq 4(p_k-1)$

Тогда $2p_k\leq 1$, очевидно противоречие.

Значит $p_2=3$

Если $p_3$ и тд существуют, тогда

$\frac{2*3p_3...p_k}{(2-1)(3-1)(p_3-1)...(p_k-1)(p_k-1)}>1$

$\frac{3p_3...p_k}{((p_3-1)...(p_k-1)(p_k-1)}>1$

Делаем тоже самое - начиная с $p_3$, все дроби вида $\frac{p_i}{p_{i+1}-1}<1$

Смотрим на $\frac{3p_k}{2(p_3-1)(p_k-1)}>1$

Очевидно что $p_3\geq 5$

$3p_k>2(p_3-1)(p_k-1)\geq 8(p_k-1)$

$8>5p_k$

противоречие, тогда чисел $p_3, p_4, ...$ просто не могло быть

Значит $n=2^a3^b$, ведь все утверждения при получении $p_1=2; p_2=3$, работают всегда.

$\frac{(2^{a+1}-1)(3^{b+1}-1)}{(2-1)(2-1)(2-1)}=\frac{(2^{a+1}-1)(3^{b+1}-1)}{4}=\frac{\sigma(n)}{p(n)-1}=n=2^a*3^b$

$2^{a+2}*3^b=2^{a+1}*3^{b+1}-3^{b+1}-2^{a+1}+1$

$1+(3-2)3^b*2^{a+1}=2^{a+1}+3^{b+1}$

$2^{a+1}3^b+1=2^{a+1}+3^{b+1}$

$3^b*2^{a+1}+1-3^b-2^{a+1}=2*3^b$

$(2^{a+1}-1)(3^b-1)=2*3^b$

$(3^b-1, 3^b) = 1$; $(2, 2^{a+1}-1)=1$ Поэтому, $2=3^b-1$, b=1.

$2^{a+1}-1=3$, a = 1

n = 6.