合同式

$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$ $\newcommand{\nequiv}{\not\equiv}$ $\newcommand{\ord}{\mathrm{ord}}$ $\newcommand{\ind}{\mathrm{ind}}$

合同式の導入

$kn+a$ $(k\in\ZZ)$ の形の数全体の集合を $$n\ZZ +a=\{a, a\pm n, a\pm 2n, \ldots\}=\{kn+a, k\in\ZZ\}$$ とおくと、除法の原理より整数全体は $$n\ZZ, n\ZZ +1, n\ZZ +2, \ldots, n\ZZ +n-1$$ に分けられる。 $n\ZZ+a (0\leq a\leq n-1)$ は $n$ で割った余りが $a$ に一致する整数全体の集合となる。

これは整数全体を、与えられた整数 $n$ で割った余りにより類別しているとみることができる。 より具体的に、次の定理が成り立つ。

定理1.1

次の各条件は互いに同値である。

1. $n\mid (a-b)$,
2. $n\ZZ+a=n\ZZ+b$,
3. $a\in n\ZZ+b$,
4. $b\in n\ZZ+a$,
5. $a$ を $n$ で割った余りと $b$ を $n$ で割った余りが等しい。

上記の条件が成り立つことを $a$ は $n$ を法として $b$ に合同であるといい $$a\equiv b\mathmod{n}$$ であらわす。

Proof.

1.$\Longrightarrow$2. $a-b=kn$ とおくと $$a+sn=b+kn+tn=b+(k+s)n, b+tn=a-kn+tn=a+(t-k)n$$ より $n\ZZ+a=n\ZZ+b$.

2.$\Longrightarrow$3. $n\ZZ+a=n\ZZ+b$ ならば $a\in n\ZZ+a=n\ZZ+b$.

3.$\Longrightarrow$4. $a=kn+b\in n\ZZ+b$ ならば $b=a-kn\in n\ZZ+a$.

4.$\Longrightarrow$5. $a=qn+r$, $0\leq r\leq n-1$ とおく。 $$b=kn+a\in n\ZZ+a$$ ならば $$b=kn+a=kn+qn+r=(k+q)n+r, 0\leq r\leq n-1$$ より $b$ を $n$ で割った余りも $r$ となる。

5.$\Longrightarrow$1. $a=kn+r$, $b=\ell n+r$ ならば $a-b=(k-\ell)n$ は $n$ で割り切れる。

□

$n\ZZ+a$ を $a$ の属する剰余類といい、$a\mathmod{n}$ であらわす。$a\equiv b\mathmod{n}$ は $a$ と $b$ の属する剰余類が一致することと定義できる。

定理1.2

$n$ を $0$ でない整数とする。

1. $a\equiv a\mathmod{n}$.
2. $a\equiv b\mathmod{n}$ ならば $b\equiv a\mathmod{n}$.
3. $a\equiv b\mathmod{n}, b\equiv c\mathmod{n}$ ならば $a\equiv c\mathmod{n}$.
4. $a\equiv c\mathmod{n}, b\equiv d\mathmod{n}$ で $k, \ell$ が整数ならば $ka+\ell b \equiv kc+\ell d\mathmod{n}$.
5. $a\equiv c\mathmod{n}, b\equiv d\mathmod{n}$ ならば $ab\equiv cd\mathmod{n}$.
6. $a\equiv b\mathmod{n}$ で、$c_0, c_1, \ldots, c_n$ が整数で $P(x)=c_n x^n+c_{n-1} x^{n-1}+\cdots +c_0$ を整数係数の多項式とすると $P(a)\equiv P(b)\mathmod{n}$.
7. 任意の整数 $k$ に対して $a\equiv b\mathmod{n} \Longleftrightarrow ka\equiv kb\mathmod{kn}$.
8. $a^g\equiv 1\mathmod{n}, s\equiv t\mathmod{g}$ のとき $a^s\equiv a^t\mathmod{n}$.
9. $a^s\equiv a^t\equiv 1\mathmod{n}$ のとき任意の整数 $k, \ell$ に対して $a^{ks+\ell t}\equiv 1\mathmod{n}$.

Proof.

1. $n\mid 0=(a-a)$.
2. $n\mid (b-a)$ より $n\mid -(b-a)=a-b$.
3. $n\mid (b-a), n\mid (c-b)$ より $n\mid (c-a)$.
4. $a-c=sn, b-d=tn$ となる整数 $s, t$ をとると \[ka+\ell b=k(c+sn)+\ell(d+tn)=kc+\ell d+n(ks+\ell t)\equiv kc+\ell d \mathmod{n}.\]
5. $a-c=sn, b-d=tn$ となる整数 $s, t$ をとると \[ab=(c+sn)(d+tn)=cd+ctn+sdn+stn^2=cd+n(ct+ds+stn)\equiv cd\mathmod{n}\]
6. $a\equiv b\mathmod{n}$ なので 5. より $a^k\equiv b^k\mathmod{n}$ ならば $a^{k+1}\equiv b^{k+1}\mathmod{n}$ も成り立つ。よって数学的帰納法より $a^k\equiv b^k\mathmod{n}$ はすべての $k=0, 1, \ldots$ に対して成り立つ。4. より $$c_k a^k+c_{k-1} a^{k-1}+\cdots +c_0 \equiv c_k b^k+c_{k-1} b^{k-1}+\cdots +c_0\mathmod{n}$$ ならば $$c_k a^{k+1}+c_k a^k+c_{k-1} a^{k-1}+\cdots +c_0 \equiv c_{k+1} b^{k+1}+c_k b^k+c_{k-1} b^{k-1}+\cdots +c_0\mathmod{n}$$ も成り立つから数学的帰納法より任意の整数係数の多項式 $P(x)$ に対して $P(a)\equiv P(b)\mathmod{n}$ が成り立つ。
7. 倍数と約数:定理2.2(3)より $n\mid (b-a) \Longleftrightarrow kn\mid k(b-a)$.
8. $a^g\equiv 1\mathmod{n}$ のとき $s=kg+t$ とおくと $a^s=a^{kg+t}=a^t (a^g)^k\equiv a^t\mathmod{n}$
9. $a^s\equiv a^t\equiv 1\mathmod{n}$ のとき任意の整数 $k, \ell$ に対して $a^{ks+\ell t}\equiv (a^s)^k (a^t)^\ell\equiv 1\mathmod{n}$.

□

このことは整数の演算 $+, -, \times$ が $\ZZ/n\ZZ$ においてwell-definedであり、かつそれらの演算により $\ZZ/n\ZZ$ が環となっていることを意味する。

定理1.3

$4n+3$ の形の素数は無限に多く存在する。

Proof.

実数 $X>0$ を任意にとり、$P$ を $X$ より小さいすべての素数の積とする。$4P-1$ は必ず $4n+3$ の形の素因数 $q$ をもつ。実際、 $$4P-1=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ と分解すると、$4P-1$ は奇数だから各 $p_i$ も奇数でなければならないがすべての $p_i$ が $p_i\equiv 1\mathmod{4}$ とすると定理1.2より$4P-1\equiv 1\mathmod{4}$ となる。しかし、$4P-1$ を $4$ で割った余りは $3$ だから、これは矛盾。

$q$ は $P$ を割り切らない。実際 $q\mid P$ ならば $q\mid 1=4P-(4P-1)$ となり、矛盾する。よって $q$ は $X$ より大きい $4n+3$ の形の素数である。$X$ は任意にとれるから $4n+3$ の形の素数は無限に多く存在する。

□

整数の演算 $+, -, \times$ が合同式の世界でもそのまま定義されるのに対して、合同式の世界における除法は整数の除法とは大きく様相が異なる。

定理1.4

$n$ を $0$ でない整数とする。 $\gcd(a, n)=1$ で $ab\equiv ac\mathmod{n}$ のとき $b\equiv c\mathmod{n}$. とくに $p$ が素数で $a$ が $p$ で割り切れないとき $ab\equiv ac\mathmod{n}$ ならば $b\equiv c\mathmod{n}$.

Proof.

$\gcd(a, n)=1$ かつ $n\mid (ab-ac)=a(b-c)$ ならば倍数と約数: 定理2.6より、$n\mid (b-c)$ つまり $b\equiv c\mathmod{n}$.

□

定理1.5

$k, n$ が整数で $n\neq 0, \gcd(a, n)\mid k$ のとき $ab\equiv k\mathmod{n}$ となる $b$ が存在する。

Proof 1.

$\gcd(a, n)\mid k$ よりBezoutの補題から、$ab-nt=k$ となる整数 $b, t$ がとれる。

□

Proof 2.

まず $\gcd(a, n)=1$ の場合について示す。 $m=0, 1, \ldots, n-1$ に対して $am$ を $n$ で割った余りを $s_m$ とおくと 定理1.4より、$s_i=s_j, 0\leq i<j\leq n-1$ ならば $i\equiv j\mathmod{n}$ であるが、$0\leq i<j\leq n-1$ より、これは不可能である。 よって $s_0, s_1, \ldots, s_{n-1}$ は $n$ 個の値 $0, 1, \ldots, n-1$ をすべてとらなければならない。 つまり各 $s=0, 1, \ldots, n-1$ に対して $ab\equiv s\mathmod{n}$ となる $b$ が存在する。 よって 任意の整数 $k$ に対して、$k$ を $n$ で割った余りを $r$ とすると、$ab\equiv r\equiv k\mathmod{n}$ となる $b$ が存在する。

一般の場合、 $\gcd(a, n)\mid k$ ならば $a_1=a/\gcd(a, n), n_1=n/\gcd(a, n), k_1=k/\gcd(a, n)$ とおくと $\gcd(a_1, n_1)=1$ なので $$a_1 b\equiv k_1\mathmod{n_1}$$ となる $b$ が存在する。倍数と約数: 定理2.2(9)より $$ab\equiv k\mathmod{n}$$ が成り立つ。

□

このことから、とくに次のことがわかる。

定義1.6（逆元）

$\gcd(a, n)=1$ のとき $ab\equiv 1\mathmod{n}$ となる $b$ が存在する。この $b$ を $n$ を法とする $a$ の逆元といい、$\bar a$ あるいは $a^{-1}$ であらわす（$\bar a$ は $a$ の属する剰余類を意味する場合もあるので注意）。

定理1.7

$\gcd(a, n)=1$ ならば $ab\equiv c\mathmod{n}\Longleftrightarrow b\equiv ca^{-1}\mathmod{n}$.

Proof.

$b\equiv ca^{-1}\mathmod{n}$ のとき $ab\equiv (ac)a^{-1}\equiv caa^{-1}\equiv c\mathmod{n}$. 逆に $ab\equiv c\mathmod{n}$ ならば $ab\equiv aca^{-1}\mathmod{n}$ なので定理1.4より $b\equiv ca^{-1}\mathmod{n}$.

□

$\gcd(a, n)=1$ が $n$ を法として逆元をもつとき、$\ZZ/n\ZZ$ における除法が $(b\mathmod{n})/(a\mathmod{n})=ba^{-1}\mathmod{n}$ により定義できる。とくに $p$ が素数のとき $\ZZ/p\ZZ$ が体となる。一方 $n$ が素数でなければ、$1$ と $n$ 自身を除く $n$ の約数 $d$ は $n$ を法として逆元をもたず、$0$ と合同でもないので、$\ZZ/n\ZZ$ は体ではない。

よって $\ZZ/n\ZZ$ が体となることの必要十分条件は $n$ が素数であることがわかる。より一般に、$(n)$ が可換環 $R$ の素イデアルであることの必要十分条件は、 $R/(n)$ が体となることである。素イデアルと極大イデアルの項目を参照。

剰余系

$0$ ではない整数 $n$ をとる。 整数の組 $a_1, a_2, \ldots, a_r$ が $n$ を法とする完全剰余系 であるとは、任意の整数 $m$ について $m\equiv a_i\mathmod{n}$ となる $a_i$ が一意に定まることをいう。 冒頭に書いたことから、 $0, 1, \ldots, n-1$ は $n$ を法とする完全剰余系となる。

定理2.1

$n$ 個の整数 $a_1, a_2, \ldots, a_n$ が $n$ を法とする完全剰余系であるための必要十分条件は $i\neq j$ のとき必ず $a_i\nequiv a_j\mathmod{n}$ となることである。

Proof.

$a_0, a_1, \ldots, a_{n-1}$ が $n$ を法とする完全剰余系であるとする。 定義より $a_i$ についても $a_i\equiv a_j\mathmod{n}$ となる $a_j$ が一意に定まるが、$a_i\equiv a_i\mathmod{n}$ だから $i=j$ でなければならない。 よって $i\neq j$ のとき必ず $a_i\nequiv a_j\mathmod{n}$ となる。

$n$ 個の整数 $a_0, a_1, \ldots, a_{n-1}$ が $n$ を法として互いに不合同とする。 $n$ 個の整数 $a_0, a_1, \ldots, a_{n-1}$ が $n$ を法とする完全剰余系であることを示すため、まず 任意の整数 $m$ について $m\equiv a_i\mathmod{n}$ となる $a_i$ は、あるとしても$1$つしかないことを示す。 実際、$i\neq j$ にもかかわらず $m\equiv a_i\mathmod{n}$, $m\equiv a_j\mathmod{n}$ がともに成り立つとき $a_i\equiv a_j\mathmod{n}$ となって、先の仮定に反する。

各 $a_i$ を $n$ で割った余りを $s_i$ とする。$s_i$ は $n$個の数 $0, 1, \ldots, n-1$ のいずれかである。 また $a_0, a_1, \ldots, a_{n-1}$ は $n$ を法として互いに不合同だから、各 $s_i$ は相異なる値をとる。よって $s_0, s_1, \ldots, s_{n-1}$ は $n$ 個の値 $0, 1, \ldots, n-1$ をすべてとらなければならない。 つまり各 $s=0, 1, \ldots, n-1$ に対して $a_i\equiv s\mathmod{n}$ となる $i$ が存在する。 任意の整数 $m$ に対して、$m$ を $n$ で割った余りを $r$ とすると、$a_i\equiv r\mathmod{n}$ となる $i$ が存在する。このとき $m\equiv a_i\equiv s\mathmod{n}$ が成り立つ。

□

定理2.2

$3n+2$ の形の平方数は存在しない。

Proof.

$-1, 0, 1$ は $3$ を法とする完全剰余系である。 $k\equiv 0\mathmod{3}$ のとき $k^2\equiv 0\mathmod{3}$, $k\equiv \pm 1\mathmod{3}$ のとき $k^2\equiv 1\mathmod{3}$ であるから 任意の整数 $k$ について $k^2\equiv 0\mathmod{3}$ または $k^2\equiv 1\mathmod{3}$ が成り立つ。よって $k^2\equiv 2\mathmod{3}$ となる整数 $k$ は存在しない。

□

Fermatの小定理とEulerの定理

Fermatの小定理は、合同式と素数との関係において、とくに重要な定理であり、さまざまな素数判定法の基礎になっている。 Fermatの小定理の一般化であるEulerの定理とあわせて解説する。

Fermatの小定理

$p$ が素数で $a$ が $p$ で割り切れない整数のとき $$a^{p-1}\equiv 1\mathmod{p}$$ が成り立つ。

Proof.

定理1.5の証明2のように $am$ を $p$ で割った余りを $s_m (i=0, 1, \ldots, p-1)$ とすると $s_0, s_1, \ldots, s_{p-1}$ は $0, 1, \ldots, p-1$ をすべてとらなければならず、かつ $i\neq j$ のとき $s_i\neq s_j$ である。 $s_0=0$ であるから、$s_1, s_2, \ldots, s_{p-1}$ は $1, \ldots, p-1$ のそれぞれの値を$1$回ずつとる。 よって $$a^{p-1} (p-1)!\equiv \prod_{m=1}^{p-1} (am)\equiv \prod_{m=1}^{p-1} s_m\equiv (p-1)!\mathmod{p}$$ が成り立つ。 $1, 2, \ldots, p-1$ は $p$ で割り切れないから $(p-1)!$ も $p$ で割り切れない。よって[#定理1.4|定理1.4]より $$a^{p-1}\equiv 1\mathmod{p}$$ が成り立つ。

□

とくに、$p$ が奇素数ならば、つねに $$2^{p-1}\equiv 1\mathmod{p}$$ が成り立つ。

しかし、 $$2^{340}\equiv (2^{10})^{34}\equiv 1\mathmod{341}$$ のように、$2^{N-1}\equiv 1\mathmod{N}$ となるからといって、$N$ が素数であるとは限らない。 したがって、Fermatの小定理はそのままでは、与えられた整数が素数かどうかを確かめることには使用できない。

Eulerの定理

$\varphi(N)$ を $N$ より小さい正の整数 $1, 2, \ldots N-1$ のうち、$N$ と互に素であるものの個数とする。 このとき、次の事実が成り立つ。

$a$ が $N$ と互に素な整数ならば $a^{\varphi(N)}\equiv 1\mathmod{p}$.

Proof.

$1, 2, \ldots , N-1$ のなかで $N$ と互に素な整数全体を $s_1, s_2, \ldots, s_{\varphi(N)}$ とし、$as_i$ を $N$ で割った余りを $t_i$ とおく。

倍数と約数: 命題3.4より各 $t_i$ も $N$ と互に素である。また、定理1.4より各 $t_i$ は相異なる値をとらなければならない。 よって $t_1, t_2, \ldots, t_{\varphi(N)}$ は $1, 2, \ldots , N-1$ のなかで $N$ と互に素な整数を$1$回ずつとるから $$\prod_i t_i=\prod_i s_i$$ となるので \[a^{\varphi(N)}\prod_i s_i=\prod_i (as_i)\equiv \prod_i t_i=\prod_i s_i\mathmod{N}\] が成り立つ。

$s_i$ はいずれも $N$ と互に素だから再び倍数と約数: 命題3.4より $\prod_i s_i$ も $N$ と互に素なので \[a^{\varphi(N)}\equiv 1\mathmod{N}\] が成り立つことがわかる。

□

$p$ が素数のとき $\varphi(p)=p-1$ だから、この定理はFermatの小定理の拡張となっている。

$\varphi(N)$ を Euler関数、Eulerの$\varphi$関数、Eulerのtotientなどと呼ぶ。一般の整数に対するEuler関数の値は後に中国式剰余定理を用いて求める。一方で $\varphi(N)=N-1 \Longleftrightarrow$ $N$ が素数であることはすぐにわかる。実際 $N$ が素数でなければ $2, \ldots, N-1$ のなかに $N$ の約数 $d$ が存在し、$\gcd(d, N)=d>1$ となるから $\varphi(N)<N-1$ となる。

乗法的位数

定理1.2(9)から、$a^e\equiv 1\mathmod{n}$ となる整数 $e$ 全体は倍数と約数: 定理2.3の条件を満足するので、 次のことがわかる。

$$a^g\equiv 1\mathmod{n}$$ となる最小の正の整数 $g$ をとると、 $$a^e\equiv 1\mathmod{n}\Longleftrightarrow g\mid e$$ が成り立つ。この整数 $g$ を $n$ を法とする $a$ の乗法的位数あるいは単に位数という。$\ord_n(a)$ とかく場合もあるが、この記号は付値をあらわす場合もあるので注意が必要である。

Fermatの小定理およびEulerの定理より、次のことがすぐにわかる。

定理4.1

$n$ を法とする $a$ の位数は $\varphi(n)$ を割り切る。

このことから、次のような定理を示すことができる。

定理4.2

$n$ が整数で $p$ が $n^2+1$ の素因数ならば、$p=2$ または $p\equiv 1\mathmod{4}$.

Proof.

$n^2+1\equiv 0\mathmod{p}$ ならば $$n^4-1\equiv (n^2+1)(n^2-1)\equiv 0\mathmod{p}$$ となる。よって $p$ を法とする $n$ の位数は $4$ の約数である。$n^2-1\equiv 0\mathmod{p}$ ならば $p\mid (n^2+1)-(n^2-1)=2$ より、$p=2$ である。よって $p$ が奇数ならば $p$ を法とする $n$ の位数は $4$ に一致するので 定理4.1より $4$ は $p-1$ を割り切る。

□

系4.3

$4n+1$ の形の素数は無数に存在する。

Proof.

実数 $X>0$ を任意にとり、$P$ を $X$ より小さいすべての素数の積とする。$P^2+1$ の素因数 $q$ をひとつとる。

$q$ は $P$ を割り切らない。実際 $q\mid P$ ならば $q\mid 1=(P^2+1)-P^2$ となり、矛盾する。 一方 $P$ は $2$ で割り切れるから、$q$ は奇数なので、定理4.2より $q\equiv 1\mathmod{4}$ となる。 よって $q$ は $X$ より大きい $4n+1$ の形の素数である。$X$ は任意にとれるから $4n+1$ の形の素数は無限に多く存在する。

□

定理4.4

$x^n\equiv 1\mathmod{p}\Longleftrightarrow$ $x\mathmod{p}$ の位数が $\gcd(n, p-1)$ を割り切る $\Longleftrightarrow x^{\gcd(n, p-1)}\equiv 1\mathmod{p}$.

Proof.

$x^n\equiv 1\mathmod{p}$ ならば $x$ の位数は $n$ の約数、かつ位数が $p-1$ の約数でもあるので倍数と約数:命題3.3より位数は $\gcd(n, p-1)$ の約数となるので $$x^{\gcd(n, p-1)}\equiv 1\mathmod{p}$$ となる。 このことは $x^n\equiv 1\mathmod{p}$ ならば、Bezoutの補題より $an+b(p-1)=\gcd(n, p-1)$ となる $a, b$ がとれるので $$x^{\gcd(n, p-1)}\equiv x^{an}x^{b(p-1)}\equiv 1\mathmod{p}$$ となることからもわかる。

逆に $x^{\gcd(n, p-1)}\equiv 1\mathmod{p}$ ならば明らかに $x^n\equiv 1\mathmod{p}$ となる。

□

多項式の合同の基礎

まず、整数係数多項式の合同について定義する。$2$つの整数係数多項式 $P(X), Q(X)$ が $n$ を法として合同であるとは、各 $X^k (k=0, 1, \ldots)$ の係数がすべて整数 $n$ を法として合同であることをいい、$P(X)\equiv Q(X)\mathmod{n}$ であらわす。$P(X)\equiv Q(X)\mathmod{n}$ は $P(X)-Q(X)$ の係数がすべて $n$ で割り切れることと言い換えられる。

定理1.2より $x, y$ が整数で $P(X)\equiv Q(X)\mathmod{n}$ かつ $x\equiv y\mathmod{n}$ ならば $P(x)\equiv Q(y)\mathmod{n}$ となる。 とくに $x\equiv y\mathmod{n}$ のとき $P(x)\equiv 0\mathmod{n}\Longleftrightarrow P(y)\equiv 0\mathmod{n}$ となる。

$\ZZ$ における剰余類の定義と同様に、$\ZZ[X]$ における剰余類を $$R(X)\mathmod{Q(X)}=Q(X)\ZZ[X] +R(X)=\{Q(X)P(X)+R(X), P(X)\in\ZZ[X]\}$$ と定義すると $$P(X)\equiv Q(X)\mathmod{n}\Longleftrightarrow n\ZZ[X]+P(X)=n\ZZ[X]+Q(X)$$ が成り立つ。

多項式の剰余類 $P(X)\mathmod{n}$ の次数は、$P(X)$ の係数が $n$ で割り切れない最も高い $X$ の次数と一致する。これを $n$ を法とする多項式 $P(X)$ の次数といい、$\deg P(X)\mathmod{p}$ であらわすことにする。

それで、$P(X)\mathmod{n}$ の次数が $d$ のとき $P(X)\equiv P_1(x)\mathmod{n}$ となる、$d$ 次の、最高次の係数が $n$ で割り切れない整数係数多項式 $P_1(X)$ がとれる。

定理5.1

$p$ が素数のとき、$p$ を法とする $P(X), Q(X)$ の次数をそれぞれ $e, f$ とおくと $p$ を法とする $P(X)Q(X)$ の次数は $e+f$ に一致する。

Proof.

実際 $$P(X)\equiv a_e x^e+\cdots +a_0, Q(X)\equiv b_f x^f+\cdots +b_0 \mathmod{p}, \gcd(p, a_e)=\gcd(p, b_f)=1$$ となるように係数をとると $$P(X) Q(X)\equiv a_e b_f x^{e+f}+\cdots +a_0 b_0\mathmod{p}$$ となるが、$\gcd(p, a_e)=\gcd(p, b_f)=1$ より $\gcd(p, a_e b_f)=1$ なので、$p$ を法とする $P(X)Q(X)$ の次数は $e+f$ に一致する。

□

この定理は、$p$ が素数でないときには一般には成り立たない。たとえば $$(2X+1)(3X+1)\equiv 6X^2+5X+1\equiv 5X+1\mathmod{6}$$ となり、$6$ を法とする $(2X+1)(3X+1)$ の次数は $1$ となる。

定理5.2

$p$ が素数のとき、$p$ を法とする $f(X), g(X)$ の次数をそれぞれ $e, f$ とおくと $e\geq f$ のとき $$f(X)\equiv Q(X)g(X)+R(X)\mathmod{p}$$ となる多項式 $Q(X), R(X)$ で $p$ を法とする $\deg Q(X) \mathmod{p}=e-f, \deg R(X)\mathmod{p}\leq f-1$ となるものが $p$ を法として一意的に定まる。

すなわち、$p$ を法とする多項式の計算においても除法の原理が成立する。

Proof.

$$f(X)\equiv a_e X^e+\cdots +a_0, g(X)\equiv b_f X^f+\cdots +b_0 \mathmod{p}, \gcd(p, a_e)=\gcd(p, b_f)=1$$ となる係数がとれる。

$e=f$ のとき、 $$f(X)-sg(X)=(a_e-b_e s) X^e+(a_{e-1}-b_{e-1} s) X^{e-1}+\cdots +(a_0-b_0 s)\mathmod{p}$$ より $$\deg (f(X)-sg(X))\mathmod {p} \leq f-1\Longleftrightarrow a_e\equiv b_e s\mathmod{p}$$ となる。よって、定理の条件を満足するものは $Q(X)\equiv a_e b_e^{-1}\mathmod{p}, R(X)\equiv (a_{e-1}-b_{e-1} s) X^{e-1}+\cdots +(a_0-b_0 s)\mathmod{p}$ により $p$ を法として一意的に定まる。

$e\leq f+k-1$ のとき定理が正しいと仮定し、$e=f+k$ の場合を考える。 $$f(X)-sX^k g(X)=(a_e-b_f s) X^e+(a_{e-1}-b_{f-1} s) X^{e-1}+\cdots +(a_k-b_0 s)X^k+a_{k-1} X^{k-1}+\cdots +a_0\mathmod{p}$$ より、 $$\deg (f(X)-sg(X))\leq f+k-1\Longleftrightarrow a_e\equiv b_f s\mathmod{p}$$ となる。そして $\deg (f(X)-sg(X))\mathmod{p} \leq f+k-1$ のとき、仮定より $$(f(X)-sX^k g(X))-Q_1(X)g(X)=R_1(X)\mathmod{p}$$ かつ $\deg Q_1(X) \mathmod{p}=\deg (f(X)-sg(X))\mathmod{p}-f, \deg R_1(X)\mathmod{p}\leq f-1$ となる $Q_1(X), R(X)$ が $p$ を法として一意的に定まる。 よって、定理の条件を満足するものは $Q(X)\equiv (a_e b_f^{-1})X^k+Q_1(X)\mathmod{p}, R(X)\equiv R_1(X)\mathmod{p}$ により $p$ を法として一意的に定まる。

これらのことから、数学的帰納法より、$e\geq f$ のとき定理は成り立つことが証明された。

□

上記のことから、与えられた整数係数多項式 $P$ の、与えられた整数 $x$ における値 $P(x)$ の属する剰余類は、$P$ の属する剰余類 $P\mathmod{n}$ と $x$ の属する剰余類 $x\mathmod{n}$ のみによって定まる。それで、この剰余類を $$P\mathmod{n}(x\mathmod{n})$$ と定める。とくに、 $$P(x)\equiv 0\mathmod{n}\Longleftrightarrow P\mathmod{n}(x\mathmod{n}) \equiv 0\mathmod{n}$$ となって、$P(x)\equiv 0\mathmod{n}$ の解は $P$ の属する剰余類と $x$ の属する剰余類のみで定まるといえるので、$P(x)\equiv 0\mathmod{n}$ となるような剰余類 $x\mathmod{n}$ そのものを $P(x)\equiv 0\mathmod{n}$ の解とみることができる。法が素数の場合、解を与える剰余類について次のことがわかる。

定理5.3

$p$ が素数で、整数 $a$ について $$P(a)\equiv 0\mathmod{p}$$ となるとき $$P(X)\equiv (X-a)Q(X)\mathmod{p}$$ となる多項式 $Q(X)$ がとれる。さらに、$a\mathmod{p}$ と合同でない整数 $b$ について $$P(b)\equiv 0\mathmod{p}$$ となるとき $$Q(b)\equiv 0\mathmod{p}$$ も成り立つ。すなわち $a\mathmod{p}$ 以外の剰余類で $$P(x)\equiv 0\mathmod{p}$$ の解となるものは $$Q(x)\equiv 0\mathmod{p}$$ の解でもある。 また、 $$P(x)\equiv 0\mathmod{p}$$ の解となる剰余類の個数は、$\deg P(x)\mathmod{p}$ 以下である。

Proof.

定理5.2より $$P(X)\equiv (X-a)Q(X)+c\mathmod{p}$$ となる $c$ がとれる。$X=a$ を代入すると $$c\equiv P(a)\equiv 0\mathmod{p}$$ より、 $$P(X)\equiv (X-a)Q(X)\mathmod{p}$$ が成り立つ。このとき、$b\not\equiv a\mathmod{p}$ で $$P(b)\equiv 0\mathmod{p}$$ ならば $$(b-a)Q(b)\equiv P(b)\equiv 0\mathmod{p}$$ となるが、$p$ は $b-a$ を割り切らないから倍数と約数: 定理2.6より $p$ は $Q(b)$ を割り切る。つまり $$Q(b)\equiv 0\mathmod{p}$$ も成り立つ。

最後に、$d=\deg P(x)\mathmod{p}$ とし、 $$P(x)\equiv 0\mathmod{p}$$ が $d+1$ 個の解 $a_1, a_2, \ldots, a_{d+1}\mathmod{p}$ をもつとすると、先に証明したことから $$P(X)\equiv (X-a_1)P_1(X)\mathmod{p}$$ となる多項式 $P_1(X)$ が存在し、$a_2, \ldots, a_{d+1}\mathmod{p}$ は $$P_1(x)\equiv 0\mathmod{p}$$ の解である。これを繰り返し $$P(X)\equiv (X-a_1)(X-a_2)\cdots (X-a_{d+1})Q(X)\mathmod{p}$$ となる多項式 $Q(X)$ がとれるので、 $$\deg P(x)\mathmod{p}\geq d+1+\deg Q(x)\mathmod{p}>d=\deg P(x)\mathmod{p}$$ となり、矛盾する。よって $$P(x)\equiv 0\mathmod{p}$$ の解となる剰余類の個数は、$d=\deg P(x)\mathmod{p}$ 以下である。

□

原始根と指数

$p$ を法とする $a$ の位数が与えられた整数 $d$ に一致するとき、定理4.1より、$d$ は $p-1$ の約数である。さらに、次のことがいえる。

命題6.1

$d$ を $p-1$ の約数とする。$p$ を法とする剰余系のうち、$p$ を法とする位数が $d$ に一致するものが存在するならば、それらの個数は $\varphi(d)$ に一致する。

Proof.

$p$ を法とする剰余系のうち、$p$ を法とする位数が $d$ のものが存在するとして、そのひとつを $a$ とすると $x=a^k (k=0, 1, \ldots, d-1)$ は互いに不合同でかつ $$x^d-1\equiv 0\mathmod{p}\quad\quad(1)$$ の解である。

定理5.3より $(1)$ の互いに不合同な解の個数は $d$ 個以下だから、 $$x^d-1\equiv 0\mathmod{p}\Longleftrightarrow x\equiv a^k\mathmod{p}$$ となることがわかる。

また $\gcd(k, d)=k_1>1$ のとき $$(a^k)^{d/\gcd(k, d)}\equiv (a^d)^{k/\gcd(k, d)}\equiv 1\mathmod{p}$$ より、$p$ を法とする $a^k$ の位数は $d/\gcd(k, d)$ の約数なので $d$ より小さい。

このことから、$p$ を法とする $b$ の位数が $d$ ならば $b\equiv a^k\mathmod{p}, \gcd(k, d)=1$ とならなければならない。逆に $b$ がこのような形のとき、 $$b^g\equiv 1\mathmod{p}\Longleftrightarrow d\mid kg\Longleftrightarrow d\mid g$$ より、$p$ を法とする $b$ の位数は $d$ に一致する。 よって $p$ を法とする剰余系のうち、$p$ を法とする位数が $d$ に一致するものが存在すれば、それらの個数は $\varphi(d)$ に一致する。

□

$\varphi(d)$ を与える公式は存在するので、後に証明するが、この公式を用いずに次のことが成り立つことが示せる。

定理6.2

$\sum_{d\mid n}\varphi(d)=n$.

Proof.

$d$ の約数に対して $$S_d=\{k(n/d): 0\leq k\leq d-1, \gcd(k, d)=1\}$$ と定義すると $\# S_d=\varphi(d)$ となる。

また、$0\leq m\leq n-1$ となる整数 $m$ に対して $d=n/\gcd(m, n), k=m/\gcd{m, n}$ とおくと $$m=k\gcd{m, n}=kn/d\in S_d$$ となるから、$0\leq m\leq n-1$ となる整数 $m$ は $S_{n/\gcd(m, n)}$ に属する。

一方、$m\in S_d$ ならば $m=kn/d$ とおくと $n/d$ は $m, n$ の公約数なので、 $m, n$ の最大公約数は $n/d$ の倍数でなければならない。しかし、 $\gcd(m, n)=fn/d$ とおくと $f$ は $m/(n/d)=k$ と $n/(n/d)=d$ の公約数なので $f=1$ つまり $\gcd(m, n)=n/d$ あるいは $d=n/\gcd(m, n)$ となる。 よって $0\leq m\leq n-1$ となる整数 $m$ は $S_{n/\gcd(m, n)}$ にのみ属するので、 $$n=\sum_{d\mid n} \# S_d=\sum_{d\mid n}\varphi(d)$$ が成り立つ。

□

定理6.2とあわせると、命題6.1より強く、$d$ が $p-1$ の約数ならば、実際に $p$ を法とする位数が $d$ のものが存在することがわかる。

定理6.3

$d$ を $p-1$ の約数とする。$1, 2, \ldots, p-1$ のうち、$p$ を法とする位数が $d$ のものの個数は $\varphi(d)$ に一致する。

Proof.

$1, 2, \ldots, p-1$ のうち、$p$ を法とする位数が $d$ のものの個数を $a_d$ とおくと命題6.1より $a_d\leq \varphi(d)$ となる。 一方、$p$ を法とする位数は $p-1$ の約数だから $$p-1\leq \sum_{d\mid p-1} a_d$$ となる。$a_d<\varphi(d)$ となる $d$ があるとすれば、定理6.2より $$p-1<\sum_{d\mid p-1} \varphi(d)=p-1$$ となって矛盾する。よって、$p-1$ のどの約数 $d$ に対しても $a_d=\varphi(d)$ が成り立つ。

□

とくに $p$ が素数のとき $p$ を法とする位数が $p-1$ となる整数 $a$ が存在する。そのような整数 $a$ あるいは剰余類 $a\mathmod{p}$ を $p$ を法とする原始根という。

実際に原始根を得るには、次のような方法がある。

Proof.

整数 $1, \ldots, p-1$ からひとつ整数 $a$ をとり、その $p$ を法とする位数を $s$ とおく。$s=p-1$ のとき $a$ は $p$ を法とする原始根。 $s<p-1$ のとき $$x^s-1\equiv 0\mathmod{p}, 1\leq x\leq p-1$$ となる整数 $x$ の個数は $s$ 以下なので、$p-1$ より少ない。よって $$b^s\not\equiv 1\mathmod{p}, 1\leq b\leq p-1$$ となる整数 $b$ がとれる。$b$ の $p$ を法とする位数を $t$ とおくと、$t$ は $s$ を割り切らない。

$$s=p_1^{e_1} p_2^{e_2} \cdots, p_k^{e_k}, t=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}$$ と素因数分解し、$u=\prod_{e_i\geq f_i}p_i^{e_i}, v=\prod_{e_i<f_i} p_i^{f_i}$ とおくと $u\mid s, v\mid t, \gcd(u, v)=1$ かつ $$uv=\prod_{i=1}^k p_i^{\max\{e_i, f_i\}}=\LCM[s, t]$$ が成り立つ。 $a_1=a^{s/u}, b_1=b^{t/v}$ とおくと $a_1, b_1$ の $p$ を法とする位数はそれぞれ $u, v$ である。

$p$ を法とする $a_1 b_1$ の位数を $k$ とすると、 $$b_1^{ku}\equiv (a_1 b_1)^{ku}\equiv 1\mathmod{p}$$ より $v\mid ku$ だが $\gcd(u, v)=1$ より $v\mid k$ となる。 同様に $$a_1^{kv}\equiv (a_1 b_1)^{kv}\equiv 1\mathmod{p}$$ より $u\mid kv$ だが $\gcd(u, v)=1$ より $u\mid k$ となる。 よって $k$ は $u, v$ 両方で割り切れるから $\LCM[u, v]=uv=\LCM[s, t]$ で割り切れる。 $t$ は $s$ を割り切らないので $$k\geq \LCM[s, t]>s$$ となり、$a_1 b_1$ の位数は $s$ より大きい。 $a$ のかわりに $a_1 b_1$ をとり、同様の議論を繰り返すと、位数は次第に増加していくから、最終的に原始根を得る。

□

与えられた素数 $p$ について、$p$ を法とする原始根が存在することはこのようにして示せるが、逆に与えられた整数 $a$ を原始根とする法 $p$ が存在するかは自明ではない。与えられた整数 $a$、たとえば $2$ を原始根とする素数 $p$ が存在するかどうかは未だに解決されていない。

$p$ を法とする原始根 $a$ をひとつとると、$a^k\mathmod{p} (k=0, 1, \ldots, p-2)$ は $p$ を法とするすべての剰余類をとり、かつ $$a^k\equiv a^\ell\mathmod{p}\Longleftrightarrow k\equiv \ell\mathmod{p-1}$$ となる。よって、$0$ 以外の剰余類 $b\mathmod{p}$ に対して $$b\equiv a^k\mathmod{p}$$ となる $k\mathmod{p-1}$ が一意的に定まる。そのような最小の正の整数 $k$ を $p$ を法とする $b$ の、底 $a$ に対する指数といい、 $$\ind_a b\mathmod{p}\equiv k\mathmod{p-1}$$ であらわす。

定理6.4

$p$ を法とする、底 $a$ に対する指数について、次の事実が成り立つ。

• $(1)$ $\ind_a (mn)\equiv \ind_a m+\ind_a n\mathmod{p-1}$.
• $(2)$ $b\mathmod{p}$ が原始根であるとき $(\ind_a b)(\ind_b c)\equiv \ind_a c\mathmod{p-1}$.

Proof.

• $(1)$ $\ind_a m\equiv g\mathmod{p-1}, \ind_a n\equiv h\mathmod{p-1}$ ならば

$m\equiv a^g\mathmod{p}, n\equiv a^h\mathmod{p}$ なので $mn\equiv a^{g+h}\mathmod{p}$ つまり $\ind_a (mn)\equiv g+h\mathmod{p-1}$.

• $(2)$ $\ind_a b\equiv g\mathmod{p-1}, \ind_b c\equiv h\mathmod{p-1}$ ならば

$b\equiv a^g\mathmod{p}, c\equiv b^h\mathmod{p}$ なので $c\equiv (a^g)^h\equiv a^{gh} \mathmod{p}$ つまり $\ind_a c\equiv gh\mathmod{p-1}$.

□

このように、指数は対数関数と類似した性質をもっていることから、離散対数とも呼ばれる。

$p$ を法とする原始根が存在することは、$\ZZ/p\ZZ$ の乗法群 $(\ZZ/p\ZZ)^*$ が位数 $p-1$ の巡回群であることを意味しており、原始根は $(\ZZ/p\ZZ)^*$ の生成元である。

法が大きいとき、与えられた原始根を底とする指数を計算する高速なアルゴリズムは現在知られていない（量子コンピューターにおいては、理論的には多項式時間で計算可能なアルゴリズムが存在するが、実用化はされていない）。指数／離散対数の概念は他の巡回群、たとえば、$p$ を法とする楕円曲線の点のなす加法群の部分群にも拡張されるが、やはり法 $p$ が大きい場合、指数を計算することは難しい。離散対数暗号はこの原理を応用したものである。

中国式剰余定理

合成数を法とする合同式は、素数冪を法とする合同式に還元される。すなわち、次の定理が成り立つ。

定理7.1

$a_1, a_2, \ldots, a_r, N_1, N_2, \ldots, N_r$ が整数で、$N_i$ のどの2つも互に素であるならば $$x\equiv a_i\mathmod{N_i} (1\leq i\leq r)\Longleftrightarrow x\equiv t \mathmod{N_1 N_2 \cdots N_r} \quad\quad (2)$$ となる $t\mathmod{N_1 N_2 \cdots N_r}$ が一意的に定まる。さらに $$\gcd(a_1, N_1)=\gcd(a_2, N_2)=\cdots =\gcd(a_r, N_r)=1\Longleftrightarrow \gcd(t, N_1 N_2 \cdots N_r)=1 \quad\quad (3)$$ が成り立つ。

Proof.

$N_i$ のどの2つも互に素だから倍数と約数: 命題3.4 より $N_s$ と $M_s=(N_1 N_2 \cdots N_r)/N_s=\prod_{1\leq i\leq r, i\neq s} N_i$ も互いに素である。 よって各 $s=1, 2, \ldots, r$ に対して \[b_s M_s\equiv 1\mathmod{N_s}\] となる $b_s$ がとれる。

$$x\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\mathmod{N_1 N_2 \cdots N_r}$$ ならば $s=1, 2, \ldots, r$ に対して $$x\equiv a_s b_s M_s\equiv a_s\mathmod{N_s}$$ が成り立つ。よって $(2)$ が成り立つ $t\mathmod{N_1 N_2 \cdots N_r}$ が存在することが確かめられる。 逆に $$x\equiv a_s\mathmod{N_s} (s=1, 2, \ldots, r)$$ ならば $$x\equiv a_s b_s M_s\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\mathmod{N_s} (s=1, 2, \ldots, r)$$ となるが $N_i$ のどの2つも互に素だから、倍数と約数: 命題3.1より $\LCM[N_i, N_j]=N_i N_j$ が $1\leq i<j\leq r$ について成り立ち、倍数と約数: 命題3.2を繰り返し適用し、 $$x\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\mathmod{N_1 N_2 \cdots N_r}$$ が成り立つ。よって $(2)$ が成り立つ $t\mathmod{N_1 N_2 \cdots N_r}$ は一意的に定まる。

さらに $\gcd(a_1, N_1)=\gcd(a_2, N_2)=\cdots =\gcd(a_r, N_r)=1$ ならば 各 $i$ について $t\equiv a_i\mathmod{N_i}$ かつ $\gcd(a_i, N_i)=1$ なので $\gcd(t, N_i)=1$ であるから 倍数と約数: 命題3.4 より $\gcd(t, N_1 N_2 \cdots N_r)=1$ となる。 一方 $d>1$ が $a_i, N_i$ をともに割り切るとき $t\equiv a_i\mathmod{N_i}$ だから $d$ は $t_i$ も割り切るが、 $d$ は $N_i$ も割り切るので $d$ は $t, N_1 N_2 \cdots N_r$ をともに割り切る。 よって $(3)$ も成り立つ。

□

中国式剰余定理という名称は、古代の中国の算術書「孫子算経」に、複数の合同式を同時に満足する整数を求める問題が 述べられていることに由来するが、実際には古代ギリシアではより古くから知られていたようである （Paulo Ribenboim, \textit{The New Book of Prime Number Records}, Springer, 3rd ed., 1996, p. 33 を参照。なお同書や他の多くの文献では古代の中国で兵士の人数を数えるためにこの定理が用いられたと書かれているが、これは後世の創作のようである。Alexei Volkov, On the origins of the Toan phap dai thanh (Great compendium of mathematical methods), From China to Paris: 2000 years transmission of mathematical ideas, edited by Yvonne Dold-Samplonius, F. Steiner, 2002, p.p. 369--410 など、およびStackExchange, Has Chinese Remainder Theorem ever been used by Chinese military?などを参照）。

定理7.2

中国式剰余定理から、$\varphi(N)$ の値を決定することができる。

$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と素因数分解すると、 $$\varphi(N)=\prod_{i=1}^k p_i^{e_i-1}(p_i-1).$$ ただし $N=1, k=0$ のときは右辺の空積は $1$ をとるとする。

Proof.

$N=p^e$ かつ $p$ が素数のとき $N=p^e$ と互に素な整数全体は $p$ の倍数ではない整数全体と一致する。 よって $1, 2, \ldots, N-1$ のなかで $N$ と互に素なものは、$1, 2, \ldots, N$ のうち $p, 2p, \ldots, (N/p)p=N$ を除いたもの全体と一致するから $$\varphi(p^e)=p^{e-1}(p-1)$$ が成り立つ。

一般の整数 $N>1$ について $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と素因数分解する。 $1\leq t\leq N$ となる整数 $t$ に対して $t$ を $p_i^{e_i}$ で割った余りを $r_i(t)$ とおくと、 各 $i$ に対して $a_i\equiv t\mathmod{p_i^{e_i}}$ が成り立つから、 中国式剰余定理より $$\gcd(t, N)=1\Longleftrightarrow \gcd(r_1(t), p_1^{e_1})=\gcd(r_2(t), p_2^{e_2})=\cdots =\gcd(r_k(t), p_k^{e_k})=1$$ となる。さらに $(a_1, a_2, \ldots, a_k)$ に対して $r_i(t)=a_i (1\leq i\leq k)$ となる $t$ が一意的に定まる。よって $1\leq t\leq N, \gcd(t, N)=1$ となる整数 $t$ と $0\leq a_i\leq p_i^{e_i}-1, \gcd(a_i, p_i^{e_i})=1 (1\leq i\leq k)$ となる整数の組 $(a_1, a_2, ldots, a_k)$ が $1$対$1$に対応する。よって $$\varphi(N)=\prod_{i=1}^k\varphi(p^e)=\prod_{i=1}^k p_i^{e_i-1}(p_i-1).$$ となる。

□

このことから、$\varphi(8)=\varphi(12)=4$, $\varphi(15)=\varphi(20)=\varphi(24)=8$ となることがわかる。

参考文献

定理6.3の第一の証明は Trygve Nagell, Introduction to Number Theory, John Wiler & Sons, Inc. New York, 1951, Theorem 65, p. 107 および G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th Ed. revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008, Theorem 111, p. 109 を、 定理6.3の別証明は Gauss, Disquitiones Arithmeticae, articles 73, 74 によるもので Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, Subection 2.II.A, p.p.23--24 を参考とした。