§A4.12位数と原始根

証明.$d=\operatorname{ord}_m(a)$とおく。$d\mid n$ならば、正整数$q$を用いて$n=dq$と書くことができるので、$a^n=(a^d)^q\equiv1\pmod m$である。

$a^n\equiv1\pmod m$とする。$n=qd+r$、$0\le r<d$と書くと、

より$a^r\equiv1\pmod m$である。$r>0$ならば、$d$より小さい正整数$r$が$a^r\equiv1\pmod m$を満たし、$d$の最小性に反する。したがって$r=0$であり、$d\mid n$である。▨

証明.$m\ge2$ならば§A4.7 定理 2.2により、$m=1$ならば§A4.7 注意 2.3により、$a^{\varphi(m)}\equiv1\pmod m$である。命題 1.2を$n=\varphi(m)$に適用すると、$\operatorname{ord}_m(a)\mid\varphi(m)$を得る。▨

証明.$h=\gcd(d,k)$とし、$d=hd'$、$k=hk'$と書くと、$\gcd(d',k')=1$である。$kd'=k'd$なので、$(a^k)^{d'}=(a^d)^{k'}\equiv1\pmod m$である。

正整数$r$が$(a^k)^r\equiv1\pmod m$を満たすとする。命題 1.2により$d\mid kr$なので、$d'\mid k'r$である。§A4.3 補題 1.1により$ud'+vk'=1$を満たす整数$u,v$を取ると、

の右辺の両項は$d'$で割り切れる。したがって$d'\mid r$であり、$r\ge d'$である。よって、$(a^k)^r\equiv1\pmod m$を満たす最小の正整数$r$は$d'=d/h$である。▨

証明.$1\le i<j\le\varphi(m)$とし、$g^i\equiv g^j\pmod m$と仮定する。$g^i$は$m$と互いに素なので、§A4.5 命題 3.2により$g^{j-i}\equiv1\pmod m$である。$0<j-i<\varphi(m)=\operatorname{ord}_m(g)$なので、位数の最小性に反する。よって$g,g^2,\ldots,g^{\varphi(m)}$は法$m$で互いに異なる。各べきは$m$と互いに素であり、そのような剰余類は$\varphi(m)$個なので、この列がすべてを尽くす。

命題 1.4により、任意の正整数$k$について

である。したがって、$g^k$が原始根であることと$\gcd(k,\varphi(m))=1$は同値である。$1\le k\le\varphi(m)$の範囲にそのような$k$は$\varphi(\varphi(m))$個あり、対応するべきは法$m$で互いに異なるので、原始根の個数も$\varphi(\varphi(m))$である。▨

証明.$d=0$のとき、$f$は$p$で割り切れない定数なので、解はない。$d\ge1$とし、次数$d-1$の場合には主張が成り立つと仮定する。$f(x)\equiv0\pmod p$に解がなければ主張は成り立つので、解の一つを$a$とする。各正整数$j$について

であるから、整数係数多項式$g(X)$を用いて

と書くことができる。$g$の次数は$d-1$であり、最高次係数は$f$と等しい。$a$と合同でない解$b$について

である。$p\nmid b-a$なので、§A4.2 補題 2.1により$p\mid g(b)$である。帰納法の仮定により、そのような$b$の剰余類は高々$d-1$個である。$a$の剰余類を加えても、$f$の解は高々$d$個である。▨

証明.$p-1$の各正の約数$d$について、$1,2,\ldots,p-1$のうち法$p$に関する位数が$d$である整数の個数を$e_d$とする。合同式$x^d\equiv1\pmod p$の解の剰余類の集合を$R_d$とする。多項式$X^d-1$の次数は$d$であり、最高次係数は$1$なので、補題 3.1により$R_d$の元は高々$d$個である。

$e_d>0$と仮定し、法$p$に関する位数が$d$である整数$a$を$1\le a\le p-1$の範囲に取る。$1\le i<j\le d$について$a^i\equiv a^j\pmod p$ならば、§A4.5 命題 3.2により$a^{j-i}\equiv1\pmod p$となり、$0<j-i<d$は位数の最小性に反する。したがって、$a,a^2,\ldots,a^d$は法$p$で互いに異なる。また、$(a^i)^d=(a^d)^i\equiv1\pmod p$なので、その$d$個の剰余類はすべて$R_d$に属する。$R_d$の元は高々$d$個なので、$a,a^2,\ldots,a^d$が$R_d$を尽くす。

位数が$d$である整数は$x^d\equiv1\pmod p$を満たすので、その剰余類は$R_d$に属する。命題 1.4により、$1\le i\le d$の範囲で$a^i$の位数が$d$であることと、$\gcd(i,d)=1$は同値である。そのような$i$は$\varphi(d)$個なので、$e_d=\varphi(d)$である。$e_d=0$の場合と合わせると、各正の約数$d$について$e_d$は$0$または$\varphi(d)$に等しく、特に$e_d\le\varphi(d)$である。

§A4.8 命題 2.1より$\varphi(p)=p-1$であり、系 1.3より$1,2,\ldots,p-1$の各整数の位数は$p-1$の正の約数である。これらの整数を位数によって分けて数えると

である。一方、§A4.8 命題 5.1を正整数$p-1$に適用すると

である。いずれの和も$p-1$の正の約数にわたる和である。各項で$e_d\le\varphi(d)$であり、両方の総和が等しいので、すべての$d$について$e_d=\varphi(d)$である。実際、一つでも$e_d<\varphi(d)$となる約数があれば、$\sum e_d<\sum\varphi(d)$となり、二つの総和が等しいことに反する。特に$e_{p-1}=\varphi(p-1)\ge1$なので、位数が$p-1=\varphi(p)$である整数が存在する。この整数は法$p$の原始根である。▨