■剰余の計算(その57)

【1】位数の法則

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

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

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

mod7

2=2,2^2=4,2^3=1→2の位数は3

3=3,3^2=2,3^3=6,3^4=4,3^5=5,3^6=1→3の位数は6

mod7での位数は7-1を割り切るというわけです。

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

[定理]Fn=2^(2^n)+1が素数pを約数にもつならばp=1 (mod2^(n+1))である

これが正しいとすれば、F5の約数の素数は

  p=2^6k+1=64K+1

に限定され、p=64・10+1を発見することができる。i

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

[証明]pをFnの約数とすると

2^(2^n)=-1 (modp)

2^(2^(n+1))=1 (modp)

modpにおける2の位数をeとすると、eは2^(n+1)の約数であるから、e=1,2,4,・・・,2^n,2^(n+1)

e=1ならば、2=1,2^2,・・・,2^(2^n)=1 (modp)=1(modq)となって矛盾。

e=2ならば、2^2=1(modp),・・・、2^(2^n)=1 (modp)=1(modq)となって矛盾。

e=4ならば、2^4=1(modq),・・・、2^(2^n)=1 (modp)=1(modq)となって矛盾。

よって、e=2^(n+1)

eはp-1の約数であるから、p=1 (mod2^(n+1))

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