【1】原始根
nを奇素数とする,nで割り切れない任意の数aに対し,
a,a^2,a^3,・・・,a^n-1 (modn)
を作る.このとき,常に
a^n-1=1 (modn)
が成立するが,aのベキの次数がn-1に到達する以前に,小さな次数kに対して
a^k=1 (modn)
が成立することがある.
逆に,n-1で初めて
a^n-1=1 (modn)
が起こることもあり,そのような数aを法nに関する原始根とよぶ.すなわち,原始根の周期はn-1といえるのである.どのような奇素数nに対しても法nに関する原始根は存在する(ガウス).
n=5,a=2の場合を調べてみると
2^1=2,2^2=4,2^3=3,2^4=1
→2は法5に関する原始根である.ord5(2)=4
===================================
z^5-1=(z-1)(z^4+z^3+z^2+z+1)
z^4+z^3+z^2+z+1=0
となる4つのzの値を求めたい。
5の原始根は2である。2,4,3,1の項の順番にしたがって、
z+z^2+z^3+z^4=r1+r2=-1
r1=z^2+z^3, r2=z^4+z^1
とベキ指数を結合する。このとき、
r1・r2=z^6+z^3+z^7+z^4=z^1+z^3+z^2+z^4=-1
r1+r2=-1より、
r1=-g,r2=1/g
z+z^2+z^3+z^4=r1+r2=1/g-g=-1
===================================
n=17の場合は、ガウスが17の原始根をつかって、そして17-1=16が2のベキであることを使って初めて解いた。
z^17-1=(z-1)(z^16+z^15+・・・+z+1)
コラム「指数合同式(その2)」
3^0=1、3^1=3,3^2=9,3^3=10,3^4=13,
3^5=5,3^6=15,3^7=11,3^8=16,
3^9=14,3^10=8,3^11=7,3^12=4,
3^13=12,3^14=2,3^15=6,3^16=1
→3は法17に関する原始根である.
項の順番にしたがって、2群に分けると
z^3+z^10+z^5+z^11+z^14+z^7+z^12+z^6=z^3+z^-7+z^5+z^-6+z^-3+z^7+z^-5+z^6
z^9+z^13+z^15+z^16+z^8+z^4+z^2+z^1=z^-8+z^-4+z^-2+z^-1+z^8+z^4+z^2+z^1
===================================
a=z^3+z^10+z^5+z^11+z^14+z^7+z^12+z^6=z^3+z^-7+z^5+z^-6+z^-3+z^7+z^-5+z^6
b=z^9+z^13+z^15+z^16+z^8+z^4+z^2+z^1=z^-8+z^-4+z^-2+z^-1+z^8+z^4+z^2+z^1
a+b=-1はよいとして、ab=-4となることを確認してみたい。
b=z^1+z^2+z^4+z^8+z^9+z^13+z^15+z^16
a=z^3+z^5+z^6+z^7+z^10+z^11+z^12+z^14
ab=z^4+z^5+z^7+z^11+z^12+z^16+z^1+z^2
z^6+z^7+z^9+z^13+z^14+z^1+z^3+z^4
z^7+z^8+z^10+z^14+z^15+z^2+z^4+z^5
z^8+z^9+z^11+z^15+z^16+z^3+z^5+z^6
z^11+z^12+z^14+z^1+z^2+z^6+z^8+z^9
z^12+z^13+z^15+z^2+z^3+z^7+z^9+z^10
z^13+z^14+z^16+z^3+z^4+z^8+z^10+z^11
z^15+z^16+z^1+z^5+z^6+z^10+z^12+z^13=-4
===================================
一つおきに項をとったが、三つおきに取ると
c=z^3+z^5+z^14+z^12=z^3+z^5+z^12+z^14 → (その26)と一致
c=z^9+z^15+z^8+z^2=z^2+z^8+z^9+z^15 → (その26)と一致
c=z^10+z^11+z^7+z^6=z^6+z^7+z^10+z^11 → (その26)と一致
c=z^13+z^16+z^4+z^1=z^1+z^4+z^13+z^16 → (その26)と一致
===================================
七つおきに取ると
c=z^3+z^14
c=z^8+z^9
c=z^7+z^10
c=z^4+z^13 → (その18)と一致
c=z^5+z^12
c=z^2+z^15
c=z^6+z^11
c=z^1+z^16 → (その18)と一致
===================================