合同式の導入

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\Z+a=n\Z+b$.

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

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

4.$\Longrightarrow$5.
$a=qn+r$, $0\leq r\leq n-1$ とおく。
$$b=kn+a\in n\Z+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$ で割り切れる。

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 \Mod{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\Mod{n}$$
6. $a\equiv b\Mod{n}$ なので 5. より $a^k\equiv b^k\Mod{n}$ ならば $a^{k+1}\equiv b^{k+1}\Mod{n}$ も成り立つ。よって数学的帰納法より $a^k\equiv b^k\Mod{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\Mod{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\Mod{n}$$ も成り立つから数学的帰納法より任意の整数係数の多項式 $P(x)$ に対して $P(a)\equiv P(b)\Mod{n}$ が成り立つ。
7. 倍数と約数:定理2 (3) より $n\mid (b-a) \Longleftrightarrow kn\mid k(b-a)$.
8. $a^g\equiv 1\Mod{n}$ のとき $s=kg+t$ とおくと $a^s=a^{kg+t}=a^t (a^g)^k\equiv a^t\Mod{n}$
9. $a^s\equiv a^t\equiv 1\Mod{n}$ のとき任意の整数 $k, \ell$ に対して $a^{ks+\ell t}\equiv (a^s)^k (a^t)^\ell\equiv 1\Mod{n}$.

実数 $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\Mod{4}$ とすると 定理2 より$4P-1\equiv 1\Mod{4}$ となる。しかし、$4P-1$ を $4$ で割った余りは $3$ だから、これは矛盾。

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

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

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

まず $\gcd(a, n)=1$ の場合について示す。
$m=0, 1, \ldots, n-1$ に対して $am$ を $n$ で割った余りを $s_m$ とおくと
定理4 より、$s_i=s_j, 0\leq i< j\leq n-1$ ならば $i\equiv j\Mod{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\Mod{n}$ となる $b$ が存在する。
よって 任意の整数 $k$ に対して、$k$ を $n$ で割った余りを $r$ とすると、$ab\equiv r\equiv k\Mod{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\Mod{n_1}$$
となる $b$ が存在する。 倍数と約数: 定理2 (9) より
$$ab\equiv k\Mod{n}$$
が成り立つ。

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

$a_0, a_1, \ldots, a_{n-1}$ が $n$ を法とする完全剰余系であるとする。
定義より $a_i$ についても $a_i\equiv a_j\Mod{n}$ となる $a_j$ が一意に定まるが、$a_i\equiv a_i\Mod{n}$ だから $i=j$ でなければならない。
よって $i\neq j$ のとき必ず $a_i\nequiv a_j\Mod{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\Mod{n}$ となる $a_i$ は、あるとしても$1$つしかないことを示す。
実際、$i\neq j$ にもかかわらず $m\equiv a_i\Mod{n}$, $m\equiv a_j\Mod{n}$ がともに成り立つとき $a_i\equiv a_j\Mod{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\Mod{n}$ となる $i$ が存在する。
任意の整数 $m$ に対して、$m$ を $n$ で割った余りを $r$ とすると、$a_i\equiv r\Mod{n}$ となる $i$ が存在する。このとき
$m\equiv a_i\equiv s\Mod{n}$ が成り立つ。

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