Республиканская олимпиада по математике, 2015 год, 10 класс


Дано натуральное число $a$. Докажите, что для любого натурального $m$ существует бесконечно много натуральных $n$ таких, что количество делителей числа $n{{a}^{n}}+1$ делится на $m$. ( Сатылханов К. )
посмотреть в олимпиаде

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

  -1
2018-03-06 17:54:36.0 #

Число $na^n+1$ представимо в виде $ na^n+1=p_{1}^{a_1}p_{2}^{a_2} ... p_{k}^{a_k} $ тогда кол-во делителей будет $(a_1+1)(a_2+1)...(a_k+1)$ поэтому нам достаточно доказать, что при $p_i$ простом($(a;p_i)=1, (p_i>m+2)$), существует бесконечно много таких $n$, что $na^n$ делится на $p_i^{m-1}$, но не делится на $p_i^{m}$. Заметим, что по теореме Эйлера $p_{i}^{m-1}-m$ - делится на показатель числа $a$ по модулю $p_i^{m-1}$,(заменим $p_{i}^{m-1}-m=d$) поэтому если заменить $n$ на $(p_i^{m-1}-m)(m^{p_i^{m-1}-m-1})r$ (где $r$ число вида $kp_i^{m-1}+1$) , то ${na^n+1}\equiv {-m^{d}+1} \pmod {p^{m-1}}$ , а так как $(m;p_i)=1$, то $-m^{d}+1$ делится на $p_i^{m-1}$. осталось доказать, что существует бесконечно много таких $r$, что $na^n+1$ не делится на $p_i^m$, что очевидно, так как $kp_i^{m-1}+1$ и $(k+1)p_i^{m-1}+1$ дают разные остатки по модулю $p_i^m$, при любом натуральном $k$, а потому одно из них подходит по условию.