【１】位数の法則

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

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

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

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

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

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

２^n＝-１　　(modｐ）

４^n＝１　　(modｐ）

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

４^e＝１　　(modｐ）

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

p=3と決定される。

n=3ｍ

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

ｍ≧２の奇数

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

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

８^m=-1 (modq)

64^m=1 (modq)

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

６４^f=1 (modq)

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

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

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

しかし８＝１　　(mod7)より矛盾→ｑ＝3→n=3m=9l→ｎは3＾2で割り切れる。

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

ここでいったん休憩

［Ｑ］奇数ｎが３^aで割り切れるなら、２^n＋１は３^a+1で割り切れる。

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

ここで、a≧２から、2a>a+1

ｎ^2の方が２^n+１より多くの３を含むので、(２^n+１)／ｎ^2は整数にならない。

したがって、ｎ＝３のみとなる。

[参]小島寛之「数学オリンピック問題にみる現代数学」講談社ブルーバックス

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