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

$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)-$ противоречие.

Это работает и для $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$