【１】位数の法則

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)→63＝1→ｑ＝３または７

ｑ＝７とすると８^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)→262143=0→3＾3・7・19・73→ｒ＝3または7・・・

r＝3とすると512^l=-1 (mod3)

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

ｑ＝3→n=3m=9l＝27ｋ・・・と続く

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