初等整数論の章ボス的な存在として、
原始根定理というものが君臨しています。
この原始根定理、のちに登場する数多の超すごい定理たちを証明する際に大活躍しますが、
原始根定理自体の証明は、なんかサクッと終わらせられがちです。
そのため今回の記事では、原始根の存在定理を真正面から丁寧に証明することを心掛けました。
地道に丁寧に進めた結果、超長くなったので、
多少長くても式変形の意味や発想の根幹部分を理解したい！という方以外はブラウザバックしてください。
等比数列を合同式の世界で観察
フェルマーの小定理、オイラーの定理をゲットする際、
$a, a^2, a^3, \cdots$
という等比数列を、$\mod n$
の世界で観察するということをやっていました。
今回は、これをもう少し深めていきたいと思います。
$a=2$で固定し、$n$の値を色々変えたものを考えます。
$2 \equiv 0 (\mod 2)$
$2\equiv 2,$ $2^2 \equiv 1 (\mod 3)$
$2 \equiv 0,$ $2^2 \equiv 0, $ $2^3 \equiv 0(\mod 4)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 2,$ $2^4 \equiv 4,$ $2^5 \equiv 2(\mod 6)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 1,$ $2^4 \equiv 2,$ $2^5 \equiv 4,$ $2^6 \equiv 1(\mod 7)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 0,$ $2^4 \equiv 0,$ $2^5 \equiv 0, $ $2^6 \equiv 0 ,$ $2^7 \equiv 0 (\mod 8)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 7,$ $2^5 \equiv 5,$ $2^6 \equiv 1,$ $2^7 \equiv 2,$ $2^8 \equiv 4 (\mod 9)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 6 ,$ $2^5 \equiv 2,$ $2^6 \equiv 4,$ $2^7 \equiv 8,$ $2^8 \equiv 6,$ $2^9 \equiv 2 (\mod 10)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 5,$ $2^5 \equiv 10,$ $2^6 \equiv 9,$ $2^7 \equiv 7 ,$ $2^8 \equiv 3,$ $2^9 \equiv 6$ $2^{10} \equiv 1 (\mod 11)$
青いマーカーがついているものだけ、
だいぶファンタスティックで特別な現象が観測されているのですが、お気づきでしょうか？
例えば$\mod 5$だけ取り出してみましょう。
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
$\mod 5$の世界に存在する数は、
０，１，２，３，４のみですが、
このうち１，２，３，４
つまり０以外のすべてが登場しています。
ヤバくないですか？
$\mod 11$でも、
１，２，３，４，５，６，７，８，９，１０のすべてが登場しています。
圧巻です。
青色マーカーの共通点を見てみると、
$\mod 3$ $\mod 5$ $\mod 11$
全て素数です。
なんだかウキウキしませんか？
素数が特別な性質を持もっていそう、という気配を感じるだけでちょっと嬉しいものです。
しかし。
黄色マーカーを見てください。
同じ素数でも、$n=7$の場合は
１，２，３，４，５，６のうち、
１，２，４しか登場しません。
あれ！？
じゃぁ、$n=7$の場合はもう駄目なのかというと、そんなことはないので、ご安心を。
$n=7$のときは、$a=2$ではなく$a=3$を考えるとよいです。
$3 \equiv 3,$ $3^2 \equiv 2,$ $3^3 \equiv 6,$ $3^4 \equiv 4,$ $3^5 \equiv 5,$ $3^6 \equiv 1(\mod 7)$
$\mod 7$に対しては、$3$がファンタスティックな動きをします
このような数のことを原始根といいます。
原始根の定義を与えるにあたっては、位数という概念を知っておくと便利です。
（位数の定義）
$p$を素数とし、$a$は$p$と互いに素である整数とする。
このとき、
$a^m \equiv 1(\mod p)$
なる整数$m$のうち、最小となるものを
法$p$における$a$の位数という。
例えば、先ほどの観察結果の黄色マーカーに注目してください。
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 1,$ $2^4 \equiv 2,$ $2^5 \equiv 4,$ $2^6 \equiv 1(\mod 7)$
フェルマーの小定理により、
$a^{p-1} \equiv 1(\mod p)$
が必ず成立します。
黄色マーカーの例でいくと、
$2^6 \equiv 1(\mod 7)$
です。
しかし、６は最小の数ではありません
$2^3 \equiv 1(\mod 7)$
があるからです。
よって、$\mod 7$における２の位数は６ではなく３です。
さて、これを踏まえたうえで原始根の話に戻りましょう。
青色マーカーに着目してください。
$2\equiv 2,$ $2^2 \equiv 1 (\mod 3)$
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
$2\equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 8,$ $2^4 \equiv 5,$ $2^5 \equiv 10,$ $2^6 \equiv 9,$ $2^7 \equiv 7 ,$ $2^8 \equiv 3,$ $2^9 \equiv 6$ $2^{10} \equiv 1 (\mod 11)$
黄色マーカーと青色マーカーを分かつ最も大切なポイントは、１が出てくるタイミング。
すなわち、位数です。
青色マーカーは、
全て位数が$p-1$なのです！
ここまでのところを箇条書きで整理しておきます。
・フェルマーの小定理から、$a^{p-1} \equiv 1(\mod p)$は必ず成立。
・位数が$p-1$に等しい→青色マーカー（つまり原始根）
・位数が$p-1$より小さい→黄色マーカー（原始根にならない）
といった具合です。
では、原始根の定義を確認しましょう。
（原始根の定義）
$p$を素数とし、$a$は$p$と互いに素である整数とする。
法$p$における$a$の位数が$p-1$に等しいとき、
$a$を法$p$における原始根という
$p$が素数のときは必ず原始根が存在するぜ！
という驚きの定理が今回の記事の主役となります。
そして、原始根は
「$a, a^2, a^3 \cdots$を素数$p$を法として計算した際に
$1, 2, 3, \cdots, p-1$が網羅される」
というファンタスティックな性質をもちます！
原始根の存在証明をするための準備
原始根の存在を証明するには、
かなーり長い準備が必要になります。
ここから先はぶっちゃけおまけみたいなものなので、
読み飛ばしてまとめにいってもOKです。
証明はいろいろな方法があり、群論的な発想を用いた証明が最も簡素なのですが、
ちょっと高度な数学の道具が必要となるので、今回はオイラー関数を用いた証明を採用します。
核心となるアイデアは、
原始根を$x^m \equiv 1(\mod p)$の解として捉えるという天才的な発想です。
例えば、$\mod 5$の例を見てみましょう。
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
です。
この結果と、$x^4 \equiv 1(\mod 5)$という方程式を見比べてみましょう。
まず$2 \equiv 2 (\mod 5)$を考えましょう。
$2^4 \equiv 1(\mod 5)$から、
$x=2$が$x^4 \equiv 1(\mod 5)$の解となることは明らかです。
次に$2^2 \equiv 4(\mod 5)$を考えます。
$(2^2)^4=(2^4)^2\equiv 1^2 \equiv 1(\mod 5)$
なので、$x=2^2$も$x^4 \equiv 1(\mod 5)$の解となります。
同様に、$2^3$と$2^4$も考えてきます
$(2^3)^4 =(2^4)^3\equiv 1(\mod 5)$
$(2^4)^4=\equiv 1(\mod 5)$
です。
つまり、$x=2, 2^2, 2^3, 2^4$は全て$x^4\equiv 1(\mod 5)$の解になるのです。
このように、原始根の存在証明を進めるにあたっては
$x^m \equiv 1(\mod p)$
という方程式がカギを握ることになります。
それにあたって、合同式の世界における高次方程式と、その解の個数についての
法則が必要になり、以下の定理に至ります。
（定理A）
次数が$d$の整数係数多項式
$f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots +a_1x+a_0$
と素数$p$があり、
$f(x)$の係数のうち少なくとも１つは$p$の倍数でないとする。
このとき、
$f(x)\equiv 0(\mod p)$
の解となる整数は$d$個以下である。
この定理は方程式の次数$d$についての定理です。
したがって、$d$についての数学的帰納法で示すことになります。
なお、定理Aの証明では合同式の世界でも因数定理が成り立つことを用いるので留意してください
（因数定理）
$f(x)$が$x-a$で割り切れる$⇔f(a)=0⇔x=a$が$f(x)=0$の解となる。
では定理Aの証明へ進んでいきましょう。
（定理Aの証明）
$d$についての数学的帰納法によって示す。
$i)$ $d=1$のとき
$f(x)=a_1x+a_0$である。
$a_1x+a_0\equiv 0(\mod p)$
の解について考える。
いま、$f(x)$は$\mod p$において１次式でなければならないので、
１次の係数$a_1$は$p$の倍数ではない。
ゆえに、$a_1$と$p$は互いに素である。
したがって、$\mod p$において$a_1$には逆元が存在し、←※１
$a_1x +a_0 \equiv 1(\mod p)$
は必ず解を１つもつことになる。
よって、$d=1$のとき定理Aは成立する$\cdots ①$
$ii)$ $d=k$で定理Aが成り立つと仮定する。このとき、$d=k+1$でも定理Aが成り立つことを示す。
仮定より、$\mod p$における$k$次の方程式の解の個数は$k$個以下である。
いま、$k+1$次方程式$f(x)$について、$f(x)\equiv 0(\mod p)$を考える。
$f(x)\equiv 0(\mod p)$に解が存在しない場合は、
解の個数は０となり、$k+1$個以下であるので定理Aは成立。
$f(x)\equiv 0(\mod p)$に解が存在する場合は、それを$x=a$とおく。
すると、因数定理より$f(x)$は$x-a$で割り切れるので、
$f(x)=(x-a)g(x)$と表すことができる。
ここで、$g(x)$は$k$次の整数係数多項式である。
仮定より、$g(x)\equiv 0 (\mod p)$の解は$k$個以下である。
よって、$f(x)\equiv 0 (\mod p)$の解は$k+1$個以下となり、
$d=k+1$でも定理Aは成立する。$\cdots ②$
①と②より、数学的帰納法から、全ての自然数$d$について定理Aは成立
（証明終了）
段々準備が整ってきました。
次は、$a, a^2, a^3 \cdots$について深めていきます。
（定理B）
$p$を素数とし、$a$は$p$と互いに素である整数とする。
$m$を法$p$における$a$の位数とする。
このとき、
$a^n \equiv 1(\mod p)$
を満たす$n$は、必ず$m$の倍数となる
（定理Bの証明）
背理法で示す。
$a^n \equiv 1(\mod 1)$
を満たす$n$が$m$の倍数ではないと仮定する。
すると、割り算で余りが発生するとこになる。
$n$を$m$で割った商を$q$とし、余りを$r$とすると、
$n=mq+r$ $1≦r≦m-1$
となる。
これを$a^n \equiv 1(\mod p)$に代入する。
$a^{mq+r} \equiv 1(\mod p)$
指数法則より、
$a^{mq+r}=a^{mq}×a^r=(a^m)^q×a^r$
である。
条件より、$m$は法$p$における$a$の位数であるので、
$a^m \equiv 1(\mod p)$
が成立。
したがって、
$a^n=a^{mq+r}=(a^m)^q×a^r \equiv a^r (\mod p)$
となり、$a^n \equiv 1(\mod p)$であることから
$a^r \equiv 1(\mod p)$
でなければならない。
しかし、余りの定義より$1≦r≦m-1$であり、
これは$m$が法$p$における$a$の位数であること、
すなわち$a^x \equiv 1(\mod p)$
を満たす$x$のうち最小のものが$m$であるという点に矛盾する。
ゆえに背理法から、$n$は$m$の倍数でなければならない。
（証明終了）
ここからは、$a, a^2, a^3, \cdots$
が$\mod p$で見たときに互いに異なる、という部分を示していきます。
（余りが全て網羅されるかどうかはこの時点ではわかりません
例えば$p=7$のとき、
$2^1\equiv 2, $ $2^2 \equiv 4,$ $ 2^3 \equiv 1(\mod 7)$
なので、$2^1, 2^2, 2^3$は互いに異なりますが、
１，２，３，４，５，６を網羅しません）
（定理C）
$p$を素数とし、$a$は$p$と互いに素である整数とする。
$m$を法$p$における$a$の位数とする。
このとき、
$a, a^2, a^3, \cdots, a^m$
はどの２つをとっても$p$を法として合同でない。
否定形の証明なので、背理法を用います
（定理Cの証明）
$a^j \equiv a^i (\mod p)$ $(0≦i<j<m)$と仮定する。
$a$は$p$と互いに素であるので、$a^i$も$p$と互いに素である。
よって、$a^j \equiv a^i (\mod p)$
の両辺を$a^i$で割ることができる。
$a^{j-i} \equiv 1(\mod p)$
である。
ここで、$(0≦i<j<m)$であったので、
$j-i<m$である。
しかし、これは$m$が法$p$における$a$の位数であることに矛盾する。
ゆえに背理法から、
$a, a^2, a^3, \cdots, a^m$
はどの２つをとっても$p$を法として合同でない
（証明終了）
あとちょっとです。
最後に、オイラー関数$\phi(n)$について、
驚嘆すべき事実が成り立つことを確認したら準備完了！
６の約数は１，２，３，６です。
実は、
$\phi(1)+\phi(2)+\phi(3)+\phi(6)=6$
が成り立ちます。
ヤバいですよね。
これを文字で表すと、次のようになります。
（定理D）
$n$を自然数とし、$n$の約数を$d_1(=1), d_2, d_3, \cdots, d_k(=n)$とする。
このとき、
$\phi(d_1)+\phi(d_2)+\cdots + \phi(n)=n$
が成り立つ
証明はこちらの記事をご覧ください
さぁ！
ようやく準備完了です！！
※１について
一次合同式$ax \equiv b(\mod k)$は$a$と$k$が互いに素という条件があるとき、
必ず解くことができます。そのことを詳しく説明した記事があるので、
よければご覧ください。
原始根の存在証明
証明に当たっては、定義が何より大切です。
まずは原始根の定義をおさらいしましょう。
（原始根の定義）
$p$を素数とし、$a$を$p$と互いに素な自然数とする。
法$p$における$a$の位数が$p-1$であるとき、
$a$を法$p$における原始根という
簡単にいうと、$a$を$p-1$乗して初めて$1$と合同になるときに原始根と呼ぶよ、というイメージです。
フェルマーの小定理より、
$a^{p-1}\equiv 1(\mod p)$
は成立します。
しかし、これは$a$を$p-1$乗すると$1$と合同になるということを主張しているだけで、
$a$を$p-1$乗して初めて$1$と合同になる
ということを主張しているわけではない点がポイント。
要するに、フェルマーの小定理では$p-1$より小さい数$n$が$a$の位数になる可能性を排除できないのです。
とはいえ、$n$について何もてがかりがないわけではありません。
定理Bより$p-1$は$n$の倍数です。
見方を変えると、$n$は$p-1$の約数です。
つまり、$p-1$の約数についてだけ考えればよいことになります。
また、例えば$\mod 5$の場合を考えると、
$2 \equiv 2,$ $2^2 \equiv 4,$ $2^3 \equiv 3,$ $2^4 \equiv 1(\mod 5)$
でした。
一方、
$3\equiv 3,$ $3^2 \equiv 4,$ $3^3 \equiv 2,$ $3^4 \equiv 1(\mod 5)$
も成り立ちます。
つまり、$\mod 5$においては、２も３も両方とも原始根になります。
（４は原始根にはなりません。）
要するに、原始根は一つとは限らず、複数あるのが普通です。
となると、原始根はどのくらいあるの？という疑問が浮かびます。
そこで原始根の存在証明では、まず$p-1$の約数$n$について、
$x^n \equiv 1(\mod p)$
の解がちょうど$n$個であることを示します。
ひとまずは、$n$乗して$1$と合同になるやつらを押さえておくわけです。
そして、最後に$n$乗して初めて$1$と合同になるやつらを数え上げて、
存在証明を終えるという流れになります
ではまず、最初のステップである$x^n \equiv 1(\mod p)$の解の個数を数えていきましょう。
途中で$X^s-1=(X-1)(X^{s-1}+X^{s-2}+ \cdots +X+1)$
という因数分解を使うので、留意してください。
（定理E）
$p$を素数とし、$n$を$p-1$の約数とする。
このとき、$x^n \equiv 1(\mod p)$
の解$x$ $(1≦x≦p-1)$はちょうど$n$個である。
（定理Eの証明）
$n$は$p-1$の約数であるので、ある数$s$を用いて
$p-1=ns$と表すことができる。
$1, 2, 3, \cdots, p-1$は$p$と互いに素であるので、
フェルマーの小定理より、
$1≦x≦p-1$となるすべての$x$に対して
$x^{p-1}\equiv 1(\mod p)$
が成立する。
ここで、$x^{p-1}-1$について考える。
$p-1=ns$であったので、
$x^{p-1}-1=x^{ns}-1=(x^n)^s-1$
である。
いま、
$X^s-1=(X-1)(X^{s-1}+X^{s-2}+ \cdots +X+1)$
という因数分解が成立するので、この式に$X=x^n$を代入すると、
$(x^n)^s-1=\lbrace (x^n)-1 \rbrace \lbrace (x^n)^{s-1}+(x^n)^{s-2}+\cdots +(x^n)+1 \rbrace$
となる。
したがって、
$x^{p-1}-1=\lbrace (x^n)-1 \rbrace \lbrace (x^n)^{s-1}+(x^n)^{s-2}+\cdots +(x^n)+1 \rbrace \cdots ①$
が成り立つ。
①の左辺について、
$x^{p-1}-1\equiv 0 (\mod p)$の解の個数はフェルマーの小定理より$p-1$個であった。
ここで、右辺について考える。
$f(x)=x^n-1, g(x)=(x^n)^{s-1}+(x^n)^{s-2}+\cdots +(x^n)+1$とする。
$f(x)$は$n$次式なので、定理Aより
$f(x) \equiv 0(\mod p)$の解は$n$個以下である。
同様に、$g(x)$は$n(s-1)$次式なので、
$g(x)\equiv 1(\mod p)$の解は$n(s-1)$個以下である。
よって、①式の右辺について、
$f(x)g(x)\equiv 0(\mod p)$
の解の個数は$n+n(s-1)=ns=p-1$個以下と分かる。
（左辺）$\equiv 0(\mod p)$の解の個数と
(右辺)$\equiv 0 (\mod p)$の解の個数
は一致していなければならないので、
$f(x)g(x)\equiv 0(\mod p)$
の解の個数はちょうど$p-1$個となり、
必然的に$x^n-1 \equiv (\mod p)$の解の個数はちょうど$n$個となる。
（証明終了）
さぁ、満を持して原始根の存在証明を行いましょう。
定理Eで$p-1$の約数$n$について、$n$乗して$1$と合同になるやつは$n$個あると分かりました。
次は、$n$乗して初めて$1$と合同になるやつの個数を数え上げます。
そして、その個数は$\phi(n)$個となります。
（定理F）
$p$素数、$n$を$p-1$の約数とする。
このとき、$n$乗して初めて$1$と合同になる数$x$ $1≦x≦p-1$
はちょうど$\phi(n)$個存在する。
（定理Fの証明）
$p-1$の約数についての数学的帰納法によって証明を行う（累積帰納法）。
$i)$ $p-1$の最小の約数$1$について
$x^1 \equiv 1(\mod p)$
の解は$x=1$のみである。
すなわち、１乗して初めて１と合同になる数は１個のみ。
ここで、$\phi(1)=1$であり、$p-1$の最小の約数$1$について定理Fは成り立つ。
$ii)$ $n$より小さい$p-1$の約数については定理Fが成り立っていると仮定する。
すなわち、$n$より小さい$p-1$の約数$d$について、
$d$乗して初めて$1$と合同になる数$x$ $(1≦x≦p-1)$
の個数は$\phi(d)$個であると仮定する。
このとき、$n$乗して初めて$1$と合同になる数$x$ $(1≦x≦p-1)$
がちょうど$\phi(n)$個であることを示す。
$n$乗して初めて$1$と合同になる数$x$ $1≦x≦p-1$の個数を
$\psi(n)$とおく。
$\psi (n)=\phi(n)$を示すことができればよい。
ここで、$n$の約数を小さい順に
$d_1(=1), d_2, \cdots, d_k(=n)$とする。
帰納法の仮定より、
$d_i$乗して初めて$1$と合同になる数は$\phi(d_i)$個である （$i=1, 2, \cdots, k-1$）。
（$d_k=n$なので、仮定で使えるのは$d_{k-1}$までです。）
ここで、自然数$a$ $(1≦a≦p-1)$に対して
$a^n \equiv 1(\mod p)$が成り立っているとする。
このとき$n$より小さい数$m$に対して、
$a$を$m$乗して初めて$1$と合同になるとすると、
定理Bより$m$は$n$の約数でなければならない。
逆に、$n$の約数$m$について、$a$を$m$乗して初めて$1$と合同になるとすると、
$a^n =(a^m)^{\dfrac{n}{m}}\equiv 1(\mod p)$
が成り立つ。
これらを踏まえると、$n$の約数$d_i$と$a$ $(1≦a≦p-1)$について
$a$を$d_i$乗して初めて$1$と合同となるならば$a^n \equiv 1(\mod p)$
が成立する。$\cdots ①$
$n$乗して$1$になる数全体の集合を$A_n$とし、
$d_i$乗して初めて$1$と合同になる数全体の集合を$B_{d_i}$
とすると、①より
$A_n =B_{d_1} \cup B_{d_2} \cup \cdots \cup B_{d_k}\cdots ②$
が成立しなければならない。
②式の両辺の集合の要素の数を数え上げる。
右辺については定理Eより、
$x^n \equiv 1(\mod p)$を満たす解の個数は$n$個であった$\cdots ③$
左辺については、帰納法の仮定より、
$d_i$乗して初めて$1$と合同になる数は$\phi(d_i)$個（$l=1, 2, \cdots, k-1$）であったので、
$B_{d_i}$の要素の個数は$\phi(d_i)$個である$\cdots ④$
（$d_k=n$なので、仮定で使えるのは$d_{k-1}$までです。$n$乗して初めて$1$と合同になるものの個数は$\psi(n)$と置いているのでした）
③と④より、
$n=\phi(d_1)+\phi(d_2)+ \cdots +\phi(d_{k-1})+\psi(n)$である$\cdots ⑤$
ここで、定理Dより、
$n=\phi(d_1)+\phi(d_2)+\cdots +\phi(d_{k-1})+\phi(n)$であった$\cdots ⑥$
⑤と⑥より、$\psi(n)=\phi(n)$
が成立し、数学的帰納法より、定理Gが示される。
（証明終了）
定理Fにおいて、$n=p-1$とすると、
$p-1$乗して初めて$1$と合同になる数が$\phi(p-1)$個存在することが示されます。
こうして、原始根の存在が証明されました！！
まとめ
いかがだったでしょうか？
今回のポイントをまとめておこうと思います
・原始根の存在証明マジ長い
以上！
また次回の記事でお会いしましょう！
コメント