Республиканская олимпиада по математике, 2000 год, 11 класс
Комментарий/решение:
Докажем индукцией по $k$ что если для произвольного четного числа $a$ число $a^{2^{k-1}}+1$ делится на простое $p$, тогда $p-1$ делится на $2^k$.
База: при $k=1$ выходит что $p|a+1$ и тогда $2|p-1$ где $a-$ любое четное число.
Пусть будет верно, что если для какого то любого произвольного четного числа $a$ число $a^{2^{k-1}}+1$ делится на простое $p$, тогда $p-1$ делится на $2^k$.
Пусть теперь для некоторого четного числа $a$ число $a^{2^{k}}+1$ делится на простое $p$, докажем что $2^{k+1}|p-1$:
Заметим, что число $a^2-$ четное и $(a^2)^{2^{k-1}}+1$ делится на $p$ значит $p-1$ делится $2^k$. Тогда $p-1=2^kt$. Осталось доказать, что $t-$ четное. Допустим , что $t$ нечетно. Тогда по малой теореме Ферма $1\equiv a^{p-1}=a^{2^{k}t}\equiv -1 (mod p) $ т.е $2\equiv 0 (mod p)-$ противоречие.
Это работает и для $a^{2^k}$+1.
Очевидно что $a^{2^{k+1}}-1$ делится на $p$.
Так же по малой теореме ферма: $a^{p-1}-1$ делится на $p$.
Значит $2^{k+1}$ и $p-1$ являются $dm$ и $dl$; где $d$- показатель $a$ по модулю $p$
Так же мы знаем что $2^{2^k}-1$ не делится на $p$.; соответсвенно и $2^k$ не делится на $d$.
значит $2^{k+1} = d$
и $2^{k+1}$ делит $p-1$; ибо как сказано раньше $p-1$ делится на $d$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.