【１】位数の法則

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

このとき、a^n=1(modp)ならば、ｎは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を割り切るというわけです。

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

[定理]a^2+1の約数となる奇素数は、4で割ると1余る。

[証明]a^2+1=0 (modq)

a^2=-1 (modq)

a^4=1 (modq)

modqにおけるaの位数をeとすると、eは4の約数であるから、e=1,2,4

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

e=2ならば、a^2=1(modq)となって矛盾。

e=4ならば、a^4=1(modq)となって、e＝4はｑ-1の倍数。→q=4k+1

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