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

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

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

Решение: Сперва упомянем лемму.

Лемма (Бразилия 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).$

Берём фиксируем $m$

и в отношении него берём $n=\varphi(m)l$ берём такой $l$ что $\varphi(m)l \equiv -1 \pmod m$ и дальше по теореме Эйлера выйдет все в лоб

Замечаем таких $l$ бесконечно много так как мы знаем что для любых данных $a,b$ есть бесконечно много $c$ такик что $ac \equiv 1\pmod {b}$ откуда легко вывезти что для $-1$ тоже будет бесконечно много так как у нас число делится на бесконечно много $m$ и можно считать $n$ как последовательность то есть с каждым таким $n$ у нас число делителей меняется в меньшую либо большую сторону тогда легко заметить что при каком то $n$ в прогрессии у нас будет что кол-во делителей делится на $m$ и заметим что когда у каких то двух $n$ одинаковое кол-во остатков по мод $m$ то между ними должен быть ещё один $m$ что кол-во делителей делится на $m$

Если где то неправильно скажите

А что если $\varphi({m})$ и $m$ не взаимно простые?

Там ещё и про количество делителей числа