Математикадан республикалық олимпиада, 1999-2000 оқу жылы, 10 сынып

$p$ саны ${{2}^{{{2}^{k}}}}+1$ санының жай бөлгіші болсын. $p-1$ саны ${{2}^{k+1}}$ санына бөлінетінін дәлелдеңіздер.

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

Докажем индукцией по $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)-$ противоречие.

Пусть $l$ - показатель 2 по модулю $p$. $2^{2^{k+1}}\equiv 1\pmod p$, поэтому $l|2^{k+1}$, т.е. $l$ - степень двойки. Если $l\le2^k$, то $2^{2^{k}}\equiv1\pmod p$ - противоречие. Поэтому $l=2^{k+1}$, значит $l=2^{k+1}|p-1$ из малой теоремы Ферма