Математикадан 41-ші халықаралық олимпиада, 2000 жыл, Тайджон

$n$ санының дәл 2000 жай бөлгіші болатындай және ${{2}^{n}}+1$ саны $n$-ге бөлінетіндей $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}$ по теореме Эйлера у нас будет как раз таки находиться