合同式の証明

質問

5^2^x≡1{mod2^(x+2)},≡/［合同でない］1{mod2^(x+3)}
であることをxに関する数学的帰納法で示しなさい。なおxは自然数とする。

x=1のとき　略　成り立つ
x=kのとき与式が成り立つと仮定すると、
5^2^k≡1{mod 2^(k+2)},≡/［合同でない］1{mod2^(k+3)}
これを等式で書くと最初の式から5^2^k=2^(k+2)・t+1 (tは奇数)

tは奇数ということからこの後どのように証明していけばいいのでしょうか？
行き詰っています、どなたかアドバイスください。お願いします。

回答No.3

age_momo · ベストアンサー

>混乱しています。

そうだと思います。本当は質問者さんも必要な情報は
すでに得ていると思いますよ。

5^2^k≡1{mod 2^(k+2)}
から
5^2^k=t*2^(k+2)+1
ただし、t=2nならば
5^2^k=2n*2^(k+2)+1=n*2^(k+3)+1≡1 (mod2^(k+3))
5^2^k≡/1{mod2^(k+3)}に矛盾。よって
t≠2n。t=2n+1とおくと
5^2^(k+1)={(2n+1)*2^(k+2)+1}^2=2^(k+3)・(2n+1){(2n+1)2^(k+1)+1}+1
≡1 (mod2^(k+3))
一方、
5^2^(k+1)=2^(k+4){(2n+1)^2+n｝+2^(k+3)+1≡2^(k+3)+1 (mod2^(k+4))
2^(k+3)+1<2^(k+4)より
2^(k+3)+1≡/1{mod2^(k+4)}

>{2^(k+2)・t+1}^2=2^(k+3)・t{2^(k+1)・t+1}+1
>とはならないのですか？

なる、ならないより証明したいことを明確に示すために都合のよい
変形をすれば良いと思います。

お礼

詳しく書いていただいたおかげでやっと理解できました。スッキリです。
本当にありがとうございました！

回答No.2

age_momo

tが奇数ならt=2n+1として再度、変形するのが基本だと思います。

{2^(k+2)・t+1}^2=2^(k+4)+t・2^(k+3)+1≡t・2^(k+3)+1 (mod 2^(k+4))

tが偶数なら一目で1余ることが分かるでしょう？
奇数なら2^(k+3)+1余りますよね。

補足

すみません、正直どのように示していいのかわからず混乱しています。
方式としては、
5^2^k=2^(k+2)・t+1 (tは奇数)
↓
tが偶数ならば1余ることを示す
↓
tが奇数ならば1余らないことを示す
ということでいいのでしょうか？あと、
>{2^(k+2)・t+1}^2=2^(k+4)+t・2^(k+3)+1≡t・2^(k+3)+1 (mod 2^(k+4))
この式変形についてですが、
{2^(k+2)・t+1}^2=2^(k+3)・t{2^(k+1)・t+1}+1
とはならないのですか？
何度も質問させていただき申し訳ありませんが、どうかよろしくお願いします。

回答No.1

age_momo

後は

5^2^(k+1)={2^(k+2)・t+1}^2

が2^(k+3)で割ると1余り、2^(k+4)で割ったときの余りが1で
ないことを示すだけですが。。。
(tが偶数なら2^(k+4)で割っても1余ってしまいますが)

補足

m=k+1のとき　
5^2^(k+1)={2^(k+2)・t+1}^2=2^(k+3)・t{2^(k+1)・t+1}+1
これで最初の式は証明できると思うんですが、
後の式2^(k+4)で割ったときの余りが1でないことはどうやって示せばいいのでしょうか？
>(tが偶数なら2^(k+4)で割っても1余ってしまいますが)
このあたりもう少しアドバイスいただけないでしょうか？
申し訳ありませんが、よろしくお願いします。