素数のべきの時
法が素数の時には原始根が存在することを前節で見た。
法が素数のべきである場合にも原始根が存在することをこの節で見る。
・d.1 スクリプトでxkを49で割った余りの表を見てみると、次の特徴に気がつく。
(1) k=42で1になる (φ(49)=42だから。pが素数の時φ(p^q)＝(p-1)pq-1となる。)
(2) xkが初めて1になるkについて、kは6以下、または(6以下)*7である。
(3) xk≡1(mod 7) ⇔ x7k≡1 (mod 49) である。
☆主張☆：pを奇素数としq≧1とする。次が成り立つ。
x≡1 (mod pq) ⇔ xp≡1 (mod pq+1)
＃例えばxが25N+1型ならばx^5は125N+1型になり、xが25N+1型でなければx^5は125N+1型にならない。
＃p=2のときについてはこれと振る舞いが異なることを注意する。
x≡±1 (mod pq) ⇔ x^2≡1 (mod 2q+1) となる。(証明略)
系：q≧2とする。xがNp+1型でNp2+1型でないならばxはpq-1乗して初めてNpq+1型となる。
（25N+1型でない5N+1型の数は、(mod 125)において25乗して初めて1と合同になる。ということ。）
系：従ってx=p+1のべき乗は(mod pq)においてpq-1個あるNp+1型の剰余類をすべて巡回網羅する。
（x=6とするとxのべき乗は(mod 125)において 6, 36, 91, 46, 26, 31, 61, 116, 71, 51,
56, 86, 16, 96, 76, 81, 111, 41, 121, 101, 106, 11, 66, 21, 1 と5N+1型を巡回網羅する。）
系：ということはNp+1型の剰余類は(p+1)y [1≦y≦pq-1]で一意に書ける。
系：(mod p^q)の剰余類xで、(p-1)pq-1乗して初めて1になるxがある。
すなわちxのべき乗が(p-1)pq-1個の既約剰余類を巡回網羅するx(原始根)がある。
[構成の仕方]
(mod p)における原始根bをとってくる。x＝b*(p+1)yとおく。
フェルマーの小定理よりbp-1はNp+1型である。bp-1≡(p+1)Yとおく。
xp-1≡(p+1)Y+(p-1)y だからY+(p-1)y がpと素になるようなyをとればよい。
(mod 125)の原始根xを構成してみる。(mod 5)の原始根2を使い、x＝2*6y とおく。
2^4＝16は先の巡回網羅列の13番目にある。16≡6^13、よってx^4≡6^(13+4y) (mod 125)
よって13+4yが5と素ならば、x^4はNp2+1型でないので25乗で初めて1になる。
ということは、そのときxは100乗で初めて1になる。(例えばy=1,x≡12)
逆に13+4y≡0(mod 25)ならばx^4はすでに1と合同である。(y=3,x≡57)
[主張の証明] (pを奇素数とする)
・q=1の時
(左から右) q≧2の時に使っている下の補題でq=2とすれば得る。
(右から左) x^p≡1(mod p^2), x≠1(mod p)とする。フェルマーの小定理よりxp-1≡1(mod p)
ということはx^p≡x≠1(mod p)であるからx^p≡1 (mod p^2) であるはずがなく矛盾。
・q≧2の時
[補題] x＝apq-1+1 ⇒ xp≡apq+1 (mod pq+1) を使う。証明は後に回した。
(左から右)
x≡1 (mod pq) ⇒ x＝apq-1+1 かつ aがpの倍数
⇒ 上記補題を使うことにより xp≡apq+1 (mod pq+1)
aがpの倍数であることより xp≡1 (mod pq+1) が言えた。
(右から左)
数学的帰納法を使う。すなわちxp≡1 (mod pq) ⇒ x≡1 (mod pq-1)を仮定する。
xp≡1 (mod pq+1) なので xp≡1 (mod pq)が必要である。
帰納法の仮定により x≡1 (mod pq-1) が言えるので x＝apq-1+1 とおける。
補題を使うと xp≡apq+1 (mod pq+1) なので
xp≡1 (mod pq+1) ⇒ aがpの倍数 ⇒ x≡1 (mod pq) が言えた。
[以下さっきの補題の証明]
xp＝(apq-1+1)p＝
1+pC1*apq-1
+pC2*(apq-1)2
+...+pCj*(apq-1)j
+...+pCp*(apq-1)p となる。
＃第二項pC1*apq-1＝apq である。
＃途中項pCj*(apq-1)j [2≦j≦p-1]は pで1+j(q-1)回割り切れる。
q≧2,j≧2のとき 1+j(q-1)≧q+1 なので、途中項はpq+1の倍数であると言える。
＃最終項pCp*(apq-1)p は pでp(q-1)回割り切れる。
p≧3,q≧2なので p(q-1)≧q+1 であり、最終項はpq+1の倍数となる。
従って xp＝1+apq+(pq+1の倍数) となることが言えた。
＃上記の下線を引いた所は、p=2,q=2では成り立たない。
これがp=2について主張を成り立たせなくしている所である。
（数学的帰納法を使っているのでq=2がだめならq≧2でもだめ）
＃補題自体はp=2に対してもq≧3ならば成り立つ。
目次
