【１】位数の法則

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 P />

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

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ｋ

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

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

2＾81＝？　　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)

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

2＾6561＝？　　mod6561

2^10=1024 (mod6561)

2~20=1048576=1184 (mod6561)

2~40=1401856=4363 (mod6561)

2~80=19035769=2308 (mod6561)

これでは時間がかかりすぎる。

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