【１】位数の法則

modpでのaの位数をeとする。

このとき、a^n=1(modp)ならば、ｎはeの倍数。とくにp-1はeの倍数

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］(２^n+１)／ｎが整数となるｎをすべて決定せよ

ｎの素因数で最小のものをｐとする。

分子は奇数であるから、ｎも奇数。ｐ≧３

２^n＝-１　　(modｐ）

４^n＝１　　(modｐ）

ここで、ｐを法とする４の位数をeとする。

４^e＝１　　(modｐ）

eはｎの約数かつｐ-１の約数。しかし、eはｎの最小の素因数であるから、e=1

p=3と決定される。

n=3ｍ

ｍ＝1のとき(２^3+１)／3＝３

ｍ≧２の奇数

２^3m+１＝８^m+１は３ｍで割り切れる。

ｍの最小の素因数をｑとすると

８^m=-1 (modq)

64^m=1 (modq)

modqにおける６４の位数をｆとすると

６４^f=1 (modq)

位数の法則よりｆはｍの約数かつｑ−1の約数→ｆ＝１

64=1　　(modq)→ｑ＝３または７

ｑ＝７とすると８^m=-1 (mod7)

しかし８＝１　　(mod7)より矛盾→ｑ＝3→n=3m=9l

2^3=-1 (mod3)

2^(3^2)=512=-1 (mod3)

2^10=1024=1 (mod3)

2^80=1 (mod3)

2^(3^4)=2=-1 (mod3)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

l＝1のとき(２^9+１)／9＝57

l≧２の奇数

２^9l+１＝512^l+１は9lで割り切れる。

lの最小の素因数をrとすると

512^l=-1 (modr)

262144^l=1 (modr)

modrにおける262144の位数をgとすると

262144^g=1 (modr)

位数の法則よりgはlの約数かつr−1の約数→g＝１

262144=1　　(modr)→r＝7または9

r＝9とすると512^l=-1 (mod9)

r＝7とすると512^l=1 (mod7)

ｑ＝3→n=3m=9l＝81ｋ

2^3=-1 (mod9)

2^(3^2)=-1 (mod9)

2^10=1024=7 (mod9)

2^20=49=4 (mod9)

2^40=16=7 (mod9)

2^80=49=4 (mod9)

2^81=-1 (mod9)

2^(3^4)=-1 (mod9)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

→ｎ＝3→3＾2→3＾4→3＾8→・・・と思われる。

2＾81＝？　　mod81

2^3=8 (mod81)

2^(3^2)=512=26 (mod81)

2^10=1024=52 (mod81)

2~20=2704=31 (mod81)

2~40=961=70 (mod81)

2~80=4900=40 (mod81)

2~81=80=-1 (mod81)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3＾3の場合を確かめておきたい

2^27=？ (mod27)

2^7=20 (mod27)

2^(3^2)=26＝-1 (mod27)

2^10=-2 (mod27)

2~20=4 (mod27)

2~27=80=-1 (mod27)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3＾5の場合を確かめておきたい

2^243=？ (mod243)

2^10=52 (mod243)

2^20=2704=31 (mod243)

2^40=961=-11 (mod243)

2^80=121 (mod243)

2^160=14641=61 (mod243)

2^240=7381=91 (mod243)

2^243=728=-1 (mod243)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝