■剰余の計算(その39)

【1】位数の法則

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

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

===================================

[Q](2^n+1)/nが整数となるnをすべて決定せよ

nの素因数で最小のものをpとする。

分子は奇数であるから、nも奇数。p≧3

2^n=-1  (modp)

4^n=1  (modp)

ここで、pを法とする4の位数をeとする。

4^e=1  (modp)

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

p=3と決定される。

n=3m

m=1のとき(2^3+1)/3=3

m≧2の奇数

2^3m+1=8^m+1は3mで割り切れる。

mの最小の素因数をqとすると

8^m=-1 (modq)

64^m=1 (modq)

modqにおける64の位数をfとすると

64^f=1 (modq)

位数の法則よりfはmの約数かつq−1の約数→f=1

64=1  (modq)→q=3または7

q=7とすると8^m=-1 (mod7)

しかし8=1  (mod7)より矛盾→q=3→n=3m=9l P />

===================================

l=1のとき(2^9+1)/9=57

l≧2の奇数

2^9l+1=512^l+1は9lで割り切れる。

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

512^l=-1 (modr)

262144^l=1 (modr)

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

262144^g=1 (modr)

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

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

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

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

q=3→n=3m=9l=81k

===================================

→n=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)

===================================