Processing math: 28%

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


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

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

  0
7 года назад #

Число nan+1 представимо в виде nan+1=pa11pa22...pakk тогда кол-во делителей будет (a1+1)(a2+1)...(ak+1) поэтому нам достаточно доказать, что при pi простом((a;pi)=1,(pi>m+2)), существует бесконечно много таких n, что nan делится на pm1i, но не делится на pmi. Заметим, что по теореме Эйлера pm1im - делится на показатель числа a по модулю pm1i,(заменим pm1im=d) поэтому если заменить n на (pm1im)(mpm1im1)r (где r число вида kpm1i+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, а потому одно из них подходит по условию.

  9
3 года назад #

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

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

  0
3 года назад #

Я не понял почему v_{p}(a^{a^x+x}+1)=v_{p}(a^{2p^{N-1}}+1), можете подробней объяснить?

  7
3 года назад #

a^x+x=2p^{N-1}*z, где z не делится на 2 и p. Тогда из LTE число \left(a^{2p^{N-1}}\right)^z+1 имеет ту же степень вхождения, что и a^{2p^{N-1}}+1

  1
3 года назад #

Ну ты гений!