2.4.5 mod pの性質

この講では、$p$を素数とするとき$\pmod{p}$の性質をみていきます。定理2.4.18のとおり、$\pmod{p}$では、四則演算が定義できます。（素数以外を法とする場合は、2.4.3のとおり除算は定義できません。)

次の定理は、様々なところで応用される重要な定理です。

定理 2.4.22
$p$を素数とすると、任意の整数$x,y$に対し

$$(x+y)^p\equiv x^p+y^p \pmod p$$

証明
2項定理より、

$$(x+y)^p = \sum_{n=0}^p {}_p\mathrm{C}_n x^{n}y^{p-n}$$

$$= x^p+\sum_{n=1}^{p-1} {}_p\mathrm{C}_n x^{n}y + y^p$$

$$p$$

$$\equiv x^p+y^p \pmod p$$

よって証明できた。

補題 2.4.23
$p$を素数とすると2項係数 ${}_p\mathrm{C}_n$は、 $1\leqq n\leqq p-1$のとき$p$で割り切れる。

証明
${}_p\mathrm{C}_n=\frac{p!}{n!(p-n)!}$であるが、 $1\leqq n\leqq p-1$であるから$n!$には$p$は含まれず$p$では割り切れない。また、同様に $1\leqq p-n \leqq p-1$となるため$(p-n)!$にも$p$は含まれず$p$は割り切れない。 ${}_p\mathrm{C}_n=\frac{p!}{n!(p-n)!}$は整数となるが、分子は$p$で割り切れ分母は$p$で割り切れないため、$p$は素数であることを考えると ${}_p\mathrm{C}_n$は$p$で割り切れる。

この定理を使いフェルマーの小定理を証明してみましょう。

定理 2.4.24 (フェルマーの小定理)
$p$を素数、$n$を$p$と互いに素な整数とするとき、

$$n^{p-1}\equiv1 \pmod{p}$$

Remark 2.4.25
$(\mathbb{Z}/p\mathbb{Z})^{\times}$は位数$p-1$の群となります。群の元は、群の位数乗すると1になりますので（系3.1.31)、フェルマーの小定理はこの群の一般的な性質の特別な場合となります。フェルマーの小定理はこのように群の一般論の中で理解することができます。下記に整数の性質を用いた2つの証明を載せますが、系3.1.31のように群論の一般論からも証明できることが分かります。

証明
定理2.4.18より $\mathbb{Z}/p\mathbb{Z}$の $overline{0}$でない元は逆元がありますので、$p$と素な$n$の逆元が存在する。すると、 $S=(\mathbb{Z}/p\mathbb{Z})^{\times}$とすると$nS=S$である。
よって、

$$n1\cdot n2\cdot n3\cdots n(p-1) \equiv 1\cdot 2\cdot 3\cdots (p-1) \pmod p$$

$$n^{p-1}(p-1)! \equiv (p-1)! \pmod p$$

$$(p-1)!\not\equiv 0\pmod p (p-1)!$$

$$n^{p-1} \equiv　1　\pmod p$$

証明 (定理2.4.22を使った別証明)
正の整数$n$に対し $n=1+1+\cdots+1$と分解したうえで定理2.4.22を繰返し適用することにより $n^p\equiv n \pmod p$であることが分かる。 同様に負の整数$n$に対しては $n=(-1)+(-1)+\cdots+(-1)$と分解したうえで定理2.4.22を繰返し適用し $(-1)^p\equiv -1\pmod p$であることを考えると $n^p\equiv n \pmod p$であると分かる。つまり、すべての整数$n$に対し $n^p\equiv n \pmod p$である。
$n$が$p$と互いに素のとき定理2.4.18より$n$の逆元$m$が存在し、 $nm\equiv 1\pmod p$となる。 $n^p\equiv n \pmod p$に$m$を掛けることにより、 $n^{p-1}\equiv 1 \pmod p$となる。

この定理から、$\mod{p}$の零でない合同類は、$p-1$乗すると必ず $\overline{1}$（1を含む合同類を意味しています。)に等しいことがわかります。更にこれから示すように、$p-1$乗して初めて $\overline{1}$になる合同類が存在することが分かります。そのような合同類を、pを法とする原始根（primitive root）又は原始元といいます。合同類 $\overline{n}$が原始根のとき、整数$n$も原始根といいます。$\mod{p}$を固定している限り、この場合、合同類を考えても整数を考えても意味は一緒だからです。

定理 2.4.26 (原始根の存在定理)
$p$を素数とする。このとき、 $p$を法とする原始根は存在し、その個数は（合同類として)$\phi(p)$個存在する。ここで、$\phi$はオイラー関数を意味します。

Remark 2.4.27
この定理は、 $(\mathbb{Z}/p\mathbb{Z})^{\times}$が巡回群であることを意味しています。
$(\mathbb{Z}/p\mathbb{Z})$はですが、この定理は有限体の乗法群は巡回群であるとの一般的な定理の特別な場合であると考えることができます。

証明は決して難しくありませが、いくつかのステップをたどる必要がありますので、ここでは省略します。

例 2.4.28
$\mod{17}$の原始根を求めてみましょう。 $\phi(16)=\phi(2^4)=2^4-2^3=8$ですので8個の原始根があるはずです。また、$\mod{17}$の元の位数は、16の約数ですので、1,2,4,8,16になります。 まず、2から試してみます。
2の場合、 $2^2=4,2^4=16=-1,2^8=1$　したがって、2の位数は8です。
3の場合、$3^2=9=1$　したがって、3の位数は2です。
4の場合、 $4^2=-1,4^4=1$　したがって、4の位数は4です。 5の場合、 $5^2=25=8,5^4=16=-1,5^8=1$　したがって、5の位数は8です。 6の場合、 $6^2=36=2,6^4=4,6^8=-1,6^16=1$　したがって、6の位数は16で、6が原始根の1つであると分かりました。 実際、6のべき乗（1から16まで)を計算すると

表: $6のべき乗\mod{17}$

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$
$6^n$	$6$	$2$	$12$	$4$	$7$	$8$	$14$	$16$	$11$	$15$	$5$	$13$	$10$	$9$	$3$	$1$

原始根が1つ分かれば命題3.1.14より他の原始根を求めることができます。
この例では6が原始根だと分かりましたので、$16$と互いに素な$n$に対し$6^n$が原始根となります。$16$と互いな素な数として1,3,5,7,9,11,13,15（つまり、奇数）がとれます。上の表より原始根は、6,12,7,14,11,5,10,3であることが分かります。