Республиканская олимпиада по математике, 2015 год, 10 класс
Комментарий/решение:
Число $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$, а потому одно из них подходит по условию.
Решение: Сперва упомянем лемму.
Лемма (Бразилия 2005): Для любых натуральных $a,c$ и целого $b$ найдется натуральное $x,$ что
$$a^x+x\equiv b \pmod c$$
Доказательство. Зафиксируем $a$ и $b,$ и докажем индукцией по $c,$ что существует даже бесконеное кол-во таких $x.$
База $c=1$ очевидна. Допустим утверждение верно для всех чисел меньших $c\ge 2.$ Теперь докажем для $c.$
Рассмотрим $\varphi(c)<c,$ из предположение $\exists$ строго возрастающая последовательность $\{x_i\}_{i\ge 1}>0,$ что
$$\varphi(c)\mid a^{x_i}+x_i-b\implies a^{x_i}+x_i-b=y_i\varphi(c)\implies b=a^{x_i}+x_i-y_i\varphi(c).$$
Теперь рассмотрим $x=x_i-y_i\varphi(c)+cK_i\varphi(c),$ где $x_i$ и $K_i$ достаточно большие натуральные числа. Отсюда получаем
$$a^x+x-b=a^x+\big(x_i-y_i\varphi(c)+cK_i\varphi(c)\big)-(a^{x_i}+x_i-y_i\varphi(c))=$$
$$a^x-a^{x_i}+cK_i\varphi(c)\equiv a^x-a^{x_i}\pmod c,$$
осталось показать, что если $x-x_i=\varphi(c)\cdot (cK_i-y_i),$ то $c\mid a^x-a^{x_i}.$
Для этого заметим, что для всех простых $p\mid c,$ но $p\nmid a:$
$$v_p(a^x-a^{x_i})=v_p(a^{x-x_i}-1)=v_p(a^{\varphi(c)\cdot (cK_i-y_i)}-1)\ge v_p(c),$$
а для $p\mid a,c:$
$$v_p(a^x-a^{x_i})=v_p(a^{x_i})=x_i\cdot v_p(a)\ge v_p(c).$$
Доказано. Ясно, что таких $x$ бесконечно много, переход доказан. $\blacksquare$
Вернемся к задаче. Будем считать, что $a,m>1,$ ведь иначе задача очевидна.
Рассмотрим простое $2<p\mid a^2+1,$ пусть $d=v_p(a^2+1)$ и $N=d*(m-1).$
Существует бесконечно много $x,$ что $a^x+x\equiv 2p^{N-1}\pmod {4p^N}.$ Подставим $n=a^x:$
$$v_p(na^n+1)=v_p(a^{a^x+x}+1)=v_p(a^{2p^{N-1}}+1)=v_p(a^2+1)+N-1=dm-1,$$
тогда $m\mid dm\mid \tau (na^n+1).$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.