合同式の割り算と逆元

同義語：division and inverses in congruences

概要

前提知識: 合同式の計算規則, 最大公約数, 除法の原理

高校での出発点：合同式で割り算をしたい

合同式の計算規則で見たように、合同式では足し算・引き算・掛け算を余りだけで計算できる。では割り算はどうか。方程式 $3x=5$ なら両辺を $3$ で割ればよいが、合同式 $3x\equiv5\pmod 7$ では「$\frac53$」は整数ではない。この記事では、合同式で割り算ができる条件 を調べる。以下 $n$ は $2$ 以上の整数とし、$a\equiv b\pmod n$ は「$a-b$ が $n$ で割り切れる」ことを表す。

$3x\equiv 5\pmod{7}$ を全部試して解く

$x$ を $0,1,\dots,6$ と変えて、$3x$ を $7$ で割った余りを表にする。

$x$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3x$	$0$	$3$	$6$	$9$	$12$	$15$	$18$
$7$ で割った余り	$0$	$3$	$6$	$2$	$5$	$1$	$4$

余りが $5$ になるのは $x=4$ だけである。どの整数も $0,\dots,6$ のどれかと合同なので、解は $x\equiv4\pmod 7$ である。
表で余りが $1$ になる $x=5$ に注目する。$3\cdot5=15\equiv1\pmod 7$ なので、$3x\equiv5$ の両辺に $5$ を掛けると
$$ 15x\equiv25\pmod 7 $$
となる。$15\equiv1$、$25=7\cdot3+4\equiv4$ なので、左辺は $x$、右辺は $4$ と合同であり、$x\equiv4$ が表を使わずに得られる。「$5$ を掛ける」ことが「$3$ で割る」ことの代わりになっている。

解が 2 つある式と、解がない式

法 $6$ で $2x$ の余りを表にする。

$x$	$0$	$1$	$2$	$3$	$4$	$5$
$2x$ を $6$ で割った余り	$0$	$2$	$4$	$0$	$2$	$4$

$2x\equiv4\pmod 6$ の解は $x\equiv2$ と $x\equiv5$ の $2$ つある。「両辺を $2$ で割って $x\equiv2$」とすると、解 $x\equiv5$ を落とす。
$2x\equiv3\pmod 6$ には解がない。余りの行に $3$ が現れないからである。
余りの行に $1$ も現れないので、$2y\equiv1\pmod 6$ となる $y$ はない。つまり ex-cginv-try7 の「$5$」にあたる数が、法 $6$ の $2$ にはない。

2 つの例から、次の問いが生まれる。

「掛けると $1$ になる数」は、どんなときにあるか。→ thm-cginv-unit
その数を実際に見つけるにはどうするか。→ ex-cginv-euclid-small、ex-cginv-euclid43

1 次の合同式 $ax\equiv b\pmod n$ の解は、いつ、いくつあるか。→ thm-cginv-linear

高校の計算	この記事の言葉	大学の言葉
掛けて $1$ になる数を掛ける	法 $n$ での逆元	剰余環の単元
互除法を逆にたどる	Bézout の等式	イデアル $a\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}$
素数の法なら $0$ 以外で割れる	素数の法では $0$ 以外が逆元をもつ	体 $\mathbb{F}_p$
解が複数・解なし	1 次合同式の解	法 $n/d$ の剰余類

表の $d$ は $a$ と $n$ の最大公約数で、これを $\gcd(a,n)$ と書く。「剰余類」は合同式の計算規則で定義した、法を決めて合同な整数を集めた集合のことである。右の列の「単元」と $\mathbb{F}_p$ は、rem-cginv-field で説明する。

法 $n$ での逆元

整数 $a$ について、
$$ ax\equiv1\pmod n $$
を満たす整数 $x$ を、$a$ の 法 $n$ での逆元 という。このとき $a$ は法 $n$ で 逆元をもつ という。

法 7 での逆元

$1$ から $6$ までの数の、法 $7$ での逆元を表にする。

$a$	$1$	$2$	$3$	$4$	$5$	$6$
逆元 $x$	$1$	$4$	$5$	$2$	$3$	$6$
$ax$	$1$	$8$	$15$	$8$	$15$	$36$
$ax$ を $7$ で割った余り	$1$	$1$	$1$	$1$	$1$	$1$

$0$ でない余りは、すべて法 $7$ で逆元をもつ。

法 8 での逆元

$3\cdot3=9=8\cdot1+1$ なので、$3$ の逆元は $3$ である。同じく $5\cdot5=25=8\cdot3+1$、$7\cdot7=49=8\cdot6+1$ なので、$5$ と $7$ の逆元はそれぞれ $5$ と $7$ である。
$2$ は法 $8$ で逆元をもたない。もし $2x\equiv1\pmod 8$ となる $x$ があれば、$2x-1=8k$（$k$ は整数）と書けて、$2x-8k=1$ となる。左辺 $2(x-4k)$ は偶数、右辺 $1$ は奇数なので、これは起こらない。同じ理由で $4$ と $6$ も逆元をもたない。

図 1 は、法 $7$ と法 $8$ の掛け算の表で、積が $1$ と合同になる欄に色をつけたものである。
法 7 と法 8 の掛け算の表。緑の欄は積が 1 と合同、赤の欄は積が 0 と合同
法 $7$ ではどの行にも緑の欄がちょうど 1 つある。これは ex-cginv-mod7 の表の逆元の位置である。法 $8$ では、$8$ と $1$ より大きい公約数をもつ $2,4,6$ の行に緑の欄がなく、代わりに赤の欄（積が $0$ と合同）がある。図では、この 3 つの行の見出しを濃い灰色にした。ex-cginv-mod8 で $2$ について示した「逆元をもたない」ことが、$4$ と $6$ でも表から読みとれる。

逆元はあれば 1 つ

$ax\equiv1$ かつ $ay\equiv1\pmod n$ ならば、$x\equiv y\pmod n$ である。

1 に置き換えて計算する

方針：$x$ に「$1$ と合同な数 $ay$」を掛けて、$x$ と $y$ を 1 本の合同式でつなぐ。
段 1。$ay\equiv1$ の両辺に $x$ を掛けると、積の規則（合同式の計算規則）により $x(ay)\equiv x\cdot1=x$ である。
段 2。$ax\equiv1$ の両辺に $y$ を掛けると、同じく $(ax)y\equiv1\cdot y=y$ である。
段 3。整数の掛け算の結合法則・交換法則により $x(ay)=(ax)y$ である。段 1 と段 2 をつなぐと
$$ x\equiv x(ay)=(ax)y\equiv y\pmod n $$
となる。$\square$

逆元の候補は法 $n$ で 1 つに重なる

法 $7$ で、$3\cdot5=15=7\cdot2+1$、$3\cdot12=36=7\cdot5+1$ なので、$5$ も $12$ も $3$ の逆元である。prop-cginv-unique により $5\equiv12\pmod 7$ のはずで、実際 $12-5=7$ である。
法 $11$ で、$4\cdot3=12=11\cdot1+1$、$4\cdot(-8)=-32=11\cdot(-3)+1$ なので、$3$ も $-8$ も $4$ の逆元である。実際 $3-(-8)=11$ で、$3\equiv-8\pmod{11}$ である。
逆元になる整数は無数にあるが、それらはすべて法 $n$ で合同で、$0$ 以上 $n$ 未満の範囲にはちょうど 1 つしかない。

逆元は法 $n$ で 1 つに決まるので、$a$ の法 $n$ での逆元を $a^{-1}$ と書くこともある。ただし $a^{-1}$ は分数 $\frac1a$ ではなく、$0$ 以上 $n$ 未満の整数で表せる数である（たとえば法 $7$ で $3^{-1}\equiv5$）。
逆元 $c$ があれば、$ax\equiv b$ の両辺に $c$ を掛けて $x\equiv cb$ と解ける（ex-cginv-try7 の計算）。したがって問題は、どの $a$ が逆元をもつかである。

主定理 1：逆元をもつ条件

Bézout の等式

逆元の条件を調べる鍵は、次の形の等式（Bézoutの等式）である。まず小さな数で見る。

$ax+ny$ の形で最大公約数を作る

$a=3$、$n=7$ では $\gcd(3,7)=1$ であり、$3\cdot5+7\cdot(-2)=15-14=1$ である。
$a=4$、$n=6$ では $\gcd(4,6)=2$ であり、$4\cdot(-1)+6\cdot1=-4+6=2$ である。
$a=5$、$n=13$ では $\gcd(5,13)=1$ であり、$5\cdot(-5)+13\cdot2=-25+26=1$ である。
どの例でも、$a$ と $n$ にそれぞれ整数を掛けて足すと、ちょうど最大公約数が作れている。

最大公約数を $ax+ny$ の形に書く

整数 $a$ と正の整数 $n$ について、$d:=\gcd(a,n)$ とおく。このとき
$$ ax+ny=d $$
を満たす整数 $x,y$ が存在する。

いちばん小さい正の数を選ぶ

方針：$ax+ny$ の形で書ける正の整数のうち、いちばん小さいもの $d_0$ を選ぶ。$d_0$ が $a$ と $n$ の両方を割ること（段 2・段 3）と、$d_0=d$ であること（段 4）を示す。
段 1（最小の数を選ぶ）。整数 $x,y$ を使って $ax+ny$ の形に書ける正の整数全体の集合を $S$ とする。$x=0$、$y=1$ とすると $a\cdot0+n\cdot1=n>0$ なので、$n\in S$ であり、$S$ は空でない。正の整数からなる空でない集合には最小の数があるので、$S$ の最小の数を
$$ d_0=ax_0+ny_0\qquad(x_0,y_0\text{ は整数}) $$
とする。
段 2（$d_0$ は $n$ を割る）。$n$ を $d_0$ で割って $n=qd_0+r$（$q$ は整数、$0\le r< d_0$）とする。余り $r$ を $a$ と $n$ で書くと
$$ r=n-qd_0=n-q(ax_0+ny_0)=a\cdot(-qx_0)+n\cdot(1-qy_0) $$
であり、$r$ も $ax+ny$ の形をしている。もし $r>0$ なら $r\in S$ であり、$r< d_0$ なので $d_0$ が最小であることに反する。よって $r=0$ であり、$n=qd_0$、つまり $d_0$ は $n$ を割る。
段 3（$d_0$ は $a$ を割る）。$a$ を $d_0$ で割って $a=q'd_0+r'$（$0\le r'< d_0$）とする。段 2 と同じように
$$ r'=a-q'd_0=a-q'(ax_0+ny_0)=a\cdot(1-q'x_0)+n\cdot(-q'y_0) $$
であり、$r'>0$ なら最小性に反するので $r'=0$ である。よって $d_0$ は $a$ を割る。
段 4（$d_0=d$）。段 2・段 3 により $d_0$ は $a$ と $n$ の正の公約数なので、最大公約数 $d$ 以下である：$d_0\le d$。一方、$d$ は $a$ と $n$ を割るので、$a=da_1$、$n=dn_1$（$a_1,n_1$ は整数）と書ける。すると
$$ d_0=ax_0+ny_0=d(a_1x_0+n_1y_0) $$
なので $d$ は $d_0$ を割る。$d_0>0$ だから $d\le d_0$ である。2 つの不等式から $d_0=d$ である。$x=x_0$、$y=y_0$ が求める整数である。$\square$

証明は $x,y$ があることを示すだけで、見つけ方は教えてくれない。実際に見つけるには、Euclidの互除法を逆にたどる。

互除法を逆にたどる（5 と 13）

$13$ と $5$ に互除法を使う。
$$ 13=2\cdot5+3,\qquad 5=1\cdot3+2,\qquad 3=1\cdot2+1 $$
最後の式から始めて、余りを 1 つずつ前の式で書き換える。
$$ \begin{aligned} 1&=3-2 &&(3=1\cdot2+1\text{ より})\\ &=3-(5-3)=2\cdot3-5 &&(2=5-3\text{ を代入})\\ &=2\cdot(13-2\cdot5)-5=2\cdot13-5\cdot5 &&(3=13-2\cdot5\text{ を代入}) \end{aligned} $$
よって $5\cdot(-5)+13\cdot2=1$ であり、$5\cdot(-5)\equiv1\pmod{13}$ である。$-5\equiv-5+13=8$ なので、$5$ の法 $13$ での逆元は $8$ である。実際 $5\cdot8=40=13\cdot3+1$ である。

互除法を逆にたどる（17 と 43）

$43$ と $17$ に互除法を使う。
$$ 43=2\cdot17+9,\qquad 17=1\cdot9+8,\qquad 9=1\cdot8+1 $$
下の式から順に余りを書き換えると
$$ \begin{aligned} 1&=9-8=9-(17-9)=2\cdot9-17\\ &=2\cdot(43-2\cdot17)-17=2\cdot43-5\cdot17 \end{aligned} $$
となる。よって $17\cdot(-5)\equiv1\pmod{43}$ であり、$-5\equiv38$ なので、$17$ の法 $43$ での逆元は $38$ である。実際 $17\cdot38=646=43\cdot15+1$ である。

図 2 は、この互除法を「横 $43$、縦 $17$ の長方形から、できるだけ大きな正方形を切り取っていく」操作として描いたものである。$17\times17$ の正方形が $2$ 個とれて横 $9$ が残り（$43=2\cdot17+9$）、次に $9\times9$ が $1$ 個とれて $8$ が残り、……と続き、最後に $1\times1$ の正方形で割り切れる。最後の正方形の一辺 $1$ が $\gcd(43,17)$ である。図 2 が見せるのは、最大公約数を求める前半（互除法の割り算）だけである。逆元 $38$ を得るために式を下から逆にたどる後半は、ex-cginv-euclid43 の計算で行った。
横 43・縦 17 の長方形を正方形で切っていく。正方形の大きさが互除法の割り算に対応する

逆元をもつ条件

整数 $a$ が法 $n$ で逆元をもつための必要十分条件は、$\gcd(a,n)=1$ である。

2 つの向きに分けて示す

方針：「$\gcd(a,n)=1$ ならば逆元がある」は Bézout の等式から、「逆元があれば $\gcd(a,n)=1$」は公約数が $1$ を割ることから示す。
段 1（$\gcd(a,n)=1$ ならば逆元をもつ）。lem-cginv-bezout により $ax+ny=1$ となる整数 $x,y$ がある。移項すると
$$ ax-1=-ny=n\cdot(-y) $$
なので、$ax-1$ は $n$ で割り切れ、$ax\equiv1\pmod n$ である。よって $x$ が $a$ の法 $n$ での逆元である。
段 2（逆元をもてば $\gcd(a,n)=1$）。$ax\equiv1\pmod n$ となる整数 $x$ があるとする。$ax-1=nk$（$k$ は整数）と書けるので、
$$ ax-nk=1 $$
である。$c$ を $a$ と $n$ の正の公約数とすると、$c$ は $ax$ と $nk$ を割るので、その差 $ax-nk=1$ も割る。$1$ を割る正の整数は $1$ だけなので $c=1$ である。よって $a$ と $n$ の正の公約数は $1$ だけであり、$\gcd(a,n)=1$ である。$\square$

法 12 で逆元をもつ数

$1$ から $11$ までの数のうち、$12$ との最大公約数が $1$ なのは $1,5,7,11$ である。thm-cginv-unit により、法 $12$ で逆元をもつのはこの $4$ つだけである。実際
$$ 5\cdot5=25=12\cdot2+1,\qquad 7\cdot7=49=12\cdot4+1,\qquad 11\cdot11=121=12\cdot10+1 $$
なので、$5,7,11$ はそれぞれ自分自身が逆元である。一方 $\gcd(4,12)=4$ なので $4$ は逆元をもたない。実際、$4x$ を $12$ で割った余りは $x=0,1,2,\dots$ に対して $0,4,8,0,4,8,\dots$ で、$1$ にならない。

素数の法では、話がとても簡単になる。

素数を法とすると 0 以外は逆元をもつ

$p$ を素数とする。$p$ で割り切れない整数 $a$ は、法 $p$ で逆元をもつ。

素数の約数を調べる

方針：$\gcd(a,p)=1$ を確かめて thm-cginv-unit を使う。
$p$ は素数なので、$p$ の正の約数は $1$ と $p$ だけである。$\gcd(a,p)$ は $p$ の正の約数なので $1$ か $p$ である。$p$ は $a$ を割らないので $\gcd(a,p)\ne p$ であり、$\gcd(a,p)=1$ である。thm-cginv-unit により、$a$ は法 $p$ で逆元をもつ。$\square$

法 11 での逆元

$11$ は素数なので、cor-cginv-prime により $1$ から $10$ までのすべての数が逆元をもつ。

$a$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
逆元	$1$	$6$	$4$	$3$	$9$	$2$	$8$	$7$	$5$	$10$
積	$1$	$12$	$12$	$12$	$45$	$12$	$56$	$56$	$45$	$100$

積はどれも $11$ で割って $1$ 余る（$12=11+1$、$45=44+1$、$56=55+1$、$100=99+1$）。

逆元があれば、合同式の両辺を「割る」ことができる。

約分できる条件

$\gcd(c,n)=1$ のとき、$ac\equiv bc\pmod n$ ならば $a\equiv b\pmod n$ である。

逆元を掛ける

方針：「$c$ で割る」代わりに「$c$ の逆元を掛ける」。
段 1。thm-cginv-unit により、$cc'\equiv1\pmod n$ となる整数 $c'$ がある。
段 2。$ac\equiv bc$ の両辺に $c'$ を掛けると、積の規則により $(ac)c'\equiv(bc)c'$ である。
段 3。左辺は $(ac)c'=a(cc')\equiv a\cdot1=a$、右辺は $(bc)c'=b(cc')\equiv b\cdot1=b$ である（$cc'\equiv1$ に積の規則を使った）。段 2 とつなぐと
$$ a\equiv a(cc')=(ac)c'\equiv(bc)c'=b(cc')\equiv b\pmod n $$
である。$\square$

約分してよい例

$3\cdot4=12$、$3\cdot9=27$ で、$27-12=15$ は $5$ で割り切れるので $3\cdot4\equiv3\cdot9\pmod 5$ である。$\gcd(3,5)=1$ なので cor-cginv-cancel により $4\equiv9\pmod 5$ である。実際 $9-4=5$ である。
$7\cdot3=21$、$7\cdot13=91$ で、$91-21=70$ は $10$ で割り切れる。$\gcd(7,10)=1$ なので $3\equiv13\pmod{10}$ である。実際 $13-3=10$ である。

合同式の計算規則の反例で見た「積が $0$ と合同なのに、どちらの因数も $0$ と合同でない」ことは、素数の法では起こらない。

素数を法とする積が 0 と合同なら

$p$ を素数とする。$ab\equiv0\pmod p$ ならば、$a\equiv0$ または $b\equiv0\pmod p$ である。言いかえると、$p$ が積 $ab$ を割るならば、$p$ は $a$ か $b$ の少なくとも一方を割る。

0 でない方の逆元を掛ける

方針：$a\not\equiv0$ の場合に $b\equiv0$ を示せばよい（$a\equiv0$ なら主張はすでに成り立つ）。
$a\not\equiv0\pmod p$、つまり $p$ が $a$ を割らないとする。cor-cginv-prime により、$aa'\equiv1\pmod p$ となる整数 $a'$ がある。$ab\equiv0$ の両辺に $a'$ を掛けると、積の規則により
$$ b\equiv(aa')b=a'(ab)\equiv a'\cdot0=0\pmod p $$
である。$\square$

この性質は Euclid の補題の言い換えで、素因数分解の一意性の要になることは素因数分解の一意性で扱う。

素数の法と合成数の法で比べる

法 $7$：$6\cdot35=210=7\cdot30$ なので $6\cdot35\equiv0\pmod 7$ である。$6\not\equiv0\pmod 7$ なので、cor-cginv-zero により $35\equiv0$ のはずで、実際 $35=7\cdot5$ である。
法 $5$：$12\cdot15=180=5\cdot36$ で、$5$ は $12$ を割らず、$15=5\cdot3$ を割る。
法 $6$（素数でない）：$2\cdot3=6\equiv0\pmod 6$ だが、$6$ は $2$ も $3$ も割らない。法が素数でないと、この系は成り立たない（合同式の計算規則の反例と同じ例）。

主定理 2：1 次合同式の解

ex-cginv-try6 では、解が 2 つある式と解がない式があった。どちらになるかは、$a$ と $n$ の最大公約数で決まる。まず例で見る。

$6x\equiv 9\pmod{15}$ と $6x\equiv 7\pmod{15}$

$6x$ を $15$ で割った余りを $x=0,1,\dots,14$ について並べると
$$ 0,\ 6,\ 12,\ 3,\ 9,\ 0,\ 6,\ 12,\ 3,\ 9,\ 0,\ 6,\ 12,\ 3,\ 9 $$
であり、$0,3,6,9,12$（$3$ の倍数）だけが $3$ 回ずつ現れる。

$6x\equiv9\pmod{15}$ の解は $x\equiv4,9,14$ の $3$ つである。$\gcd(6,15)=3$ で、$3$ は $9$ を割る。解は $5$ ずつ離れている（$15\mathbin{÷}3=5$）。
$6x\equiv7\pmod{15}$ には解がない。$\gcd(6,15)=3$ は $7$ を割らない。

1 次合同式の解

整数 $a,b$ について、$d:=\gcd(a,n)$ とおく。

合同式 $ax\equiv b\pmod n$ が解をもつための必要十分条件は、$d$ が $b$ を割ることである。
$d$ が $b$ を割るとき、$a'=\frac ad$、$b'=\frac bd$、$n'=\frac nd$ とおく。$n'\ge2$ のときは、$c$ を $a'$ の法 $n'$ での逆元とすると、解の全体は $x\equiv cb'\pmod{n'}$ である。$n'=1$ のとき（$a$ が $n$ の倍数で $d=n$ のとき）は、すべての整数 $x$ が解である。どちらの場合も、解は法 $n$ で数えるとちょうど $d$ 個ある。
特に $d=1$ なら、解は法 $n$ でただ 1 つである。

公約数で割ってから逆元を掛ける

方針：解があれば $d$ が $b$ を割ることを先に示す（段 1）。次に、式全体を $d$ で割って、$\gcd=1$ の合同式に直し（段 2・段 3）、逆元で解く（段 4）。最後に、法 $n$ で解を数える（段 5）。
段 1（解があれば $d\mid b$）。$x$ が解なら、$ax-b=nk$（$k$ は整数）と書けるので $b=ax-nk$ である。$d$ は $a$ と $n$ を割るので、$ax$ と $nk$ を割り、その差 $b$ も割る。
以下、$d$ が $b$ を割るとし、$a=da'$、$b=db'$、$n=dn'$ と書く。
段 1'（$n'=1$ の場合）。$n'=1$ なら $d=n$ で、$a=na'$、$b=nb'$ である。どの整数 $x$ についても $ax-b=n(a'x-b')$ は $n$ で割り切れるので、すべての整数 $x$ が解である。法 $n$ で数えると $0,1,\dots,n-1$ の $n$ 個で、$n=d$ なので定理のとおり $d$ 個である。この場合の証明はこれで終わる。以下の段 2〜段 5 では $n'\ge2$ とする（def-cginv-inverse の逆元は $2$ 以上の法で考えているので、法 $n'$ での逆元を使う段 4 にはこの約束が必要である）。
段 2（$d$ で割っても解は変わらない）。整数 $x$ について
$$ ax-b=da'x-db'=d(a'x-b') $$
である。$n$ が $ax-b$ を割るとき、$d(a'x-b')=nk=dn'k$ と書け、両辺を $d$（$\ne0$）で割ると $a'x-b'=n'k$ となるので、$n'$ が $a'x-b'$ を割る。逆に $a'x-b'=n'k$ なら、両辺に $d$ を掛けて $ax-b=nk$ となる。よって
$$ ax\equiv b\pmod n\quad\Longleftrightarrow\quad a'x\equiv b'\pmod{n'} $$
である。
段 3（$\gcd(a',n')=1$）。lem-cginv-bezout により $as+nt=d$ となる整数 $s,t$ がある。$a=da'$、$n=dn'$ を代入して両辺を $d$ で割ると
$$ a's+n't=1 $$
である。$a'$ と $n'$ の正の公約数は左辺を割るので $1$ を割り、$1$ に限る。よって $\gcd(a',n')=1$ である。
段 4（逆元で解く）。段 3 と thm-cginv-unit により、$a'$ は法 $n'$ で逆元 $c$ をもつ（$a'c\equiv1\pmod{n'}$）。$a'x\equiv b'$ の両辺に $c$ を掛けると $x\equiv ca'x\equiv cb'\pmod{n'}$ である。逆に $x\equiv cb'$ なら、両辺に $a'$ を掛けて $a'x\equiv a'cb'\equiv b'\pmod{n'}$ である。よって解の全体は $x\equiv cb'\pmod{n'}$ である。
段 5（法 $n$ で数える）。$x_0:=cb'$ とおくと、解は $x=x_0+n'k$（$k$ は整数）の形の整数全体である。$k$ を $d$ で割って $k=dm+j$（$0\le j< d$）とすると
$$ x_0+n'k=x_0+n'j+n'dm=x_0+n'j+nm\equiv x_0+n'j\pmod n $$
なので、どの解も $x_0,\ x_0+n',\ \dots,\ x_0+(d-1)n'$ のどれかと法 $n$ で合同である。この $d$ 個は法 $n$ で互いに合同でない。$0\le j< j'< d$ なら、差 $n'(j'-j)$ は $0< n'(j'-j)< n'd=n$ を満たし、$n$ で割り切れないからである。よって解は法 $n$ でちょうど $d$ 個ある。$\square$

定理の手順で解く

$6x\equiv9\pmod{15}$。$d=\gcd(6,15)=3$ は $9$ を割る。$3$ で割ると $2x\equiv3\pmod 5$ である。$2\cdot3=6\equiv1\pmod 5$ なので $2$ の法 $5$ での逆元は $3$ であり、$x\equiv3\cdot3=9\equiv4\pmod 5$ である。法 $15$ では $x\equiv4,\ 9,\ 14$ の $3$ 個である。確かめると $6\cdot4=24=15+9$、$6\cdot9=54=45+9$、$6\cdot14=84=75+9$ である。
$17x\equiv5\pmod{43}$。$d=\gcd(17,43)=1$ である。ex-cginv-euclid43 により $17$ の逆元は $38$ なので
$$ x\equiv38\cdot5=190=43\cdot4+18\equiv18\pmod{43} $$
である。確かめると $17\cdot18=306=43\cdot7+5$ である。
$4x\equiv6\pmod{10}$。$d=\gcd(4,10)=2$ は $6$ を割る。$2$ で割ると $2x\equiv3\pmod 5$ で、(1) と同じく $x\equiv4\pmod 5$ である。法 $10$ では $x\equiv4,9$ の $2$ 個である（$4\cdot4=16$、$4\cdot9=36$ はどちらも $10$ で割って $6$ 余る）。
$4x\equiv8\pmod 4$。$d=\gcd(4,4)=4$ は $8$ を割り、$n'=4/4=1$ である（段 1' の場合）。どの整数 $x$ でも $4x-8=4(x-2)$ は $4$ で割り切れるので、すべての $x$ が解であり、法 $4$ では $x\equiv0,1,2,3$ の $4=d$ 個である。

大学の言葉で見ると

単元と体

合同式の計算規則で導入した剰余環 $\mathbb{Z}/n\mathbb{Z}$ の言葉では、逆元をもつ剰余類を単元といい、単元全体を $(\mathbb{Z}/n\mathbb{Z})^\times$ と書く。thm-cginv-unit は「$\overline a$ が単元 $\iff\gcd(a,n)=1$」と言いかえられる。正の整数 $n$ について、$1$ 以上 $n$ 以下の整数のうち $n$ と互いに素なものの個数を $\varphi(n)$ と書く（Eulerのφ関数。$\varphi(1)=1$ である）。$n\ge2$ では、thm-cginv-unit により単元の個数は $\varphi(n)$ である。たとえば $\varphi(12)=4$（ex-cginv-mod12 の $1,5,7,11$）、$\varphi(11)=10$（ex-cginv-mod11）である。
$0$ 以外のすべての元が逆元をもつ可換環を体という。cor-cginv-prime により、$p$ が素数なら $\mathbb{Z}/p\mathbb{Z}$ は $p$ 個の元からなる体であり、$\mathbb{F}_p$ と書く。$n$ が合成数 $n=rs$（$1< r,s< n$）なら $\gcd(r,n)=r>1$ なので $\overline r$ は $\overline0$ でないのに逆元をもたず、$\mathbb{Z}/n\mathbb{Z}$ は体ではない。

例と反例

外した仮定	崩れる主張	ボックス
$\gcd(c,n)=1$	約分できる（cor-cginv-cancel）	ex-cginv-nocancel
$\gcd(a,n)=1$	$ax\equiv b$ の解は法 $n$ でただ 1 つ	ex-cginv-many
法が素数	$x^2\equiv1$ の解は $x\equiv\pm1$ だけ	ex-cginv-roots8

反例：公約数があると約分できない

$6\cdot2=12$、$6\cdot7=42$ で、$42-12=30=15\cdot2$ なので $6\cdot2\equiv6\cdot7\pmod{15}$ である。しかし $7-2=5$ は $15$ で割り切れないので $2\not\equiv7\pmod{15}$ である。$\gcd(6,15)=3\ne1$ なので cor-cginv-cancel の仮定を満たさず、「$ac\equiv bc$ ならば $a\equiv b$」が破れる。正しく言えるのは、thm-cginv-linear の段 2 と同じように $3$ で割った $2\equiv7\pmod 5$ である。

反例：公約数があると解は 1 つに決まらない

$2x\equiv4\pmod 6$ の解は $x\equiv2,5$ の $2$ 個である（ex-cginv-try6）。$\gcd(2,6)=2\ne1$ なので、「解は法 $n$ でただ 1 つ」は成り立たない。個数 $2$ は thm-cginv-linear の $d=2$ に一致している。

反例：法 8 では $x^2\equiv 1$ の解が 4 つある

法 $7$ で $x^2$ の余りを調べると、$x=0,1,\dots,6$ に対して $0,1,4,2,2,4,1$ であり、$x^2\equiv1$ の解は $x\equiv1,6$ の $2$ つだけである。これは cor-cginv-zero から説明できる：$x^2-1=(x-1)(x+1)\equiv0\pmod 7$ なので、$x-1\equiv0$ か $x+1\equiv0$、つまり $x\equiv1$ か $x\equiv-1\equiv6$ である。
法 $8$ では、$x=0,1,\dots,7$ に対して $x^2$ の余りは $0,1,4,1,0,1,4,1$ であり、$x^2\equiv1$ の解は $x\equiv1,3,5,7$ の $4$ つある。たとえば $x=3$ では $(x-1)(x+1)=2\cdot4=8\equiv0$ だが、$2\not\equiv0$、$4\not\equiv0\pmod 8$ である。法が素数でないと cor-cginv-zero が使えず、「解は $\pm1$ だけ」が破れることがある。法 $8$ がその例である。
ただし、合成数の法でいつも破れるわけではない。法 $9$ では、$x=0,1,\dots,8$ に対して $x^2$ の余りは $0,1,4,0,7,7,0,4,1$ であり、$x^2\equiv1$ の解は $x\equiv1,8$、つまり $\pm1$ の $2$ つだけである。法 $4,6,10,25$ なども、解は $\pm1$ だけである。

さらに先へ

素数 $p$ を法とすると、逆元は累乗 $a^{p-2}$ でも求められる。これは Fermatの小定理と冪の余りで証明する。
法が互いに素な 2 つの合同式 $x\equiv r\pmod m$、$x\equiv s\pmod n$ を同時に満たす $x$ は、法 $mn$ でただ 1 つある（中国剰余定理）。証明には lem-cginv-bezout を使う。
互除法そのものと、1 次不定方程式 $ax+by=c$ の整数解の全体は整数の割り算と互除法で詳しく扱う。
Bézout の等式と 1 次合同式の解の条件は、標準的な教科書では Sho08 Theorem 1.8・Theorem 2.5 にある。