■正多角形の作図問題(その7)

【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)

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

n=2^n+1,m=2^32ではn=4294967297は合成数である。

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