x^kの様子、原始根

pは素数とする。
xが代数的剰余類(要するに無理数)の時のx^k(mod p)の様子を調べる。

この場合、xが整数の時と違って x^(p-1)≡1 とは限らない。
＃実際、p=13の時、例えば(√2)^12＝64≡-1 であるし、
　(2+√2)^12≡3+11√2であるので、全然成り立っていない。

視点を変えると、x=1,2,...,11,12の時はx^12≡1(mod 13)となるのであったから、
x^12-1≡(x-1)(x-2)...(x-11)(x-12) (mod 13) が成り立つ。
右辺にx＝a+b√qとか代入しても0にならないことが見て取れる。
（∵前節のab≡0 ⇒ a≡0またはb≡0 が適用される）
しかし、実はx＝a+b√qの場合、x^p≡a-b√qになる。
ということはx^(p^2)≡x,つまりx^(p^2-1)≡1ということになる。

☆主張☆： xをm次の代数的剰余類とする。
・x^(p^m-1)≡1 (mod p)　となる。（フェルマーの小定理の拡張）
・x^k≡1 (mod p) となる最小のkがp^m-1であるようなxが存在する（「原始根」）

＃m次の代数的既約剰余類はp^m-1個あるので、
　そのxのべき乗はそれらを巡回網羅するのである。
＃d.1節のスクリプトで2次の場合をちょっと試せる。
＃p=7についてちょっと試すと、例えば1+√3は原始根の1つである。

[証明]
有理数の時と同じ議論である。やはりラグランジュの定理による。
前節の通り、乗法に関して群をなす、という前提が成り立つから。

＃例えばxを2次の代数的剰余類としてx^kを7で割ったあまりは48種類の既約剰余類のどれかとなる。
仮にxを5回掛けたら元に戻る、すなわちx≠1,x^2≠1,x^3≠1,x^4≠1,x^5≡1 (mod 7)と仮定する。
x,x^2,x^3,x^4,x^5≡1 は異なる5つの剰余類である。ここに使われない剰余類がまだある。
それを１つcとする。cx,cx^2,cx^3,cx^4,cx^5≡c も同様に5つの異なる剰余類となる。
これらは先の5つの数と全部ばらばらでなければならない。
操作を繰り返すと48は5で割り切れないから、最後に矛盾になる。

・後半も有理数の時と同様に、円分多項式の積による次の合同方程式
x^{p^2-1}-1≡0を考えれば理解される。Φ[p^2-1]の解が原始根になる。

＃x^48≡1 (mod 7)は2次の無理数範囲では解を48個持つ。(主張の前半による。)
x^48-1＝Φd(x)の積[dは48の約数]　に注意する。
Φk(x)≡0はφ(k)次式で、高々φ(k)個の解しか持たないからフル活用しないといけない。
（∵一般に、Y＝Σφ(d):dはYの約数）
というわけでΦ48(x)≡0が解を持つ。それが原始根となる。
（∵その解はフル活用要請からΦd(x)＝0(d＜48)の解にはならないからである。）