41-я Международная Математическая OлимпиадаРеспублика Корея, Тайджон, 2000 год

Существует ли такое натуральное число $n$, что $n$ имеет ровно 2000 различных простых делителей и ${{2}^{n}}+1$ делится на $n$?

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

Отметим $n=p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000} \Rightarrow$

$2^{p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}}\equiv 0 \pmod {p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}} \Rightarrow$

Заметим все $p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}$ нечетные иначе нечетное делится на четное что невозможно $\Rightarrow$

по МТФ $2^{p^{k_1}_1} \equiv 2^{k_1}\pmod {p^{k_1}_1}$$\Rightarrow$

$2^{p^{k_1}_1}2^{p^{k_2}_2}.....2^{p^{k_{2000}}_{2000}} \equiv 2^{k_1}2^{k_2}.....2^{k_{2000}} \pmod{p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}}$

Докажем что $2^{k_1}2^{k_2}.....2^{k_{2000}} \equiv\ne -1 \pmod {p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}}$

$1$case $n=x^l$,$l\equiv 0 \pmod{2}$$\Rightarrow$

$k_1,k_1,...,k_{2000} \equiv 0 \pmod {2}$$\Rightarrow$

$2^{k_1}2^{k_2}.....2^{k_{2000}} \equiv\ne -1 \pmod {p^{k_1}_1p^{k_2}_2.....p^{k_{2000}}_{2000}}$

$2$case $n=x^l$,$l\equiv 1 \pmod {2}$ по теореме Эйлера у нас будет как раз таки находиться