合同式
概要
合同式（congruence）とは、正の整数 $n$ が $a-b$ を割り切るとき $a\equiv b\pmod n$ と書き、整数 $a,b$ を $n$ で割った余りが等しいことを表す式である。時計や曜日の計算のように余りだけに注目して整数を扱う言葉で、記号 $\equiv$ は Gauss が導入した。合同は同値関係であり、和・差・積・冪と両立するので、大きな数の余りを途中で余りに置き換えながら計算できる。一方、両辺から共通の因子 $c$ を無条件に消せるのは $c$ と $n$ が互いに素なときであり（$2\cdot1\equiv2\cdot3\pmod4$ だが $1\not\equiv3\pmod4$）、$ax\equiv1\pmod n$ が解をもつのも $a$ と $n$ が互いに素なときに限る。Fermatの小定理や中国剰余定理も合同式で述べられる。
前提知識: 整数, 除法の原理, 最大公約数, Bézoutの等式, 同値関係
時計の針は $12$ 時間で一回りするので、$10$ 時の $5$ 時間後は $15$ 時ではなく $3$ 時と読む。$15$ と $3$ は $12$ で割った余りが等しく、時計の上では同じ位置を指す。同じように、曜日は $7$ 日ごとにくり返すので、木曜日である 2026 年 9 月 24 日の $100$ 日後は、$100=7\cdot14+2$ より木曜日の $2$ 日後の土曜日である。このように「ある数 $n$ で割った余りだけに注目して整数を計算する」ための言葉が合同式である。$15$ と $3$ は「$12$ を法として合同」であるといい、$15\equiv3\pmod{12}$ と書く。
合同式の便利さは、和・差・積が余りだけで計算できることにある。たとえば $7^{2026}$ の一の位を知りたければ、$10$ で割った余りを追えばよい。$7^2=49$ の一の位は $9$、$7^4=2401$ の一の位は $1$ なので $7^4\equiv1\pmod{10}$ であり、$2026=4\cdot506+2$ から
$$
7^{2026}=(7^4)^{506}\cdot7^2\equiv1^{506}\cdot49\equiv9\pmod{10}
$$
となって、$1713$ 桁もある $7^{2026}$ を計算せずに一の位が $9$ だと分かる。一方、割り算は自由にはできない（ex-congruence-relation-cancellation-fails）。以下では定義を述べ、どの計算が許されどの計算が許されないかを証明とともに整理する。
定義
以下、$n$ は正の整数とする。整数 $d,a$ について $d\mid a$ は、$a=dk$ となる整数 $k$ があること（$d$ が $a$ を割り切ること）を表す。
$n$ を正の整数、$a,b$ を整数とする。$n\mid a-b$ であるとき、$a$ と $b$ は $n$ を法として合同（congruent modulo $n$）であるといい、
$$
a\equiv b\pmod n
$$
と書く。この形の式を合同式（congruence）といい、$n$ をその法（modulus）という。$n\nmid a-b$ のときは $a\not\equiv b\pmod n$ と書き、$a$ と $b$ は $n$ を法として合同でないという。
たとえば $n\mid a-0$ は $n\mid a$ と同じなので、$a\equiv0\pmod n$ は「$a$ が $n$ で割り切れる」ことの言い換えである。$a\equiv0\pmod2$ は $a$ が偶数、$a\equiv1\pmod2$ は $a$ が奇数であることを表す。$n=1$ ではすべての整数が互いに合同になる。
法を負の整数 $-n$ にしても $-n\mid a-b$ と $n\mid a-b$ は同じ条件なので、法は正にとってよい。法 $0$ を許す流儀では $0\mid a-b$ が $a=b$ を意味するので、合同は等号に一致する。本記事では法を正の整数に限る。
記号 $\equiv$ は Gauss が著書 Disquisitiones Arithmeticae（1801 年）の冒頭で導入したもので、Gauss は等号とよく似た性質をもつことからこの記号を選んだと述べている（Gau01 Art. 1–2）。
$n$ を正の整数、$a,b$ を整数とする。次は同値である。
- $a\equiv b\pmod n$。
- $a$ と $b$ を $n$ で割った余り（除法の原理で $0$ 以上 $n-1$ 以下にとったもの）が等しい。
- ある整数 $k$ について $a=b+kn$。
1 ⇔ 3 は定義 $n\mid a-b$ の書き直しである。
2 ⇒ 1：$a=qn+r$、$b=q'n+r$（$0\le r\le n-1$）なら $a-b=(q-q')n$ である。
1 ⇒ 2：$a=qn+r$、$b=q'n+r'$（$0\le r,r'\le n-1$）とすると $r-r'=(a-b)-(q-q')n$ は $n$ で割り切れる。$-(n-1)\le r-r'\le n-1$ の範囲にある $n$ の倍数は $0$ だけなので $r=r'$ である。$\square$
剰余類
合同は次の節で示すとおり同値関係である（prop-congruence-relation-equivalence）。そこで同値類を考える。
整数 $a$ と合同な整数全体
$$
\bar a:=a+n\mathbb{Z}=\{a+kn\mid k\in\mathbb{Z}\}
$$
を、$a$ の法 $n$ の剰余類（residue class、合同類）という。$\bar a=\bar b$ であることと $a\equiv b\pmod n$ であることは同値である。法 $n$ の剰余類全体の集合を $\mathbb{Z}/n\mathbb{Z}$ と書く。
$n$ 個の整数 $r_1,\dots,r_n$ が、どの 2 つも $n$ を法として合同でないとき、これを法 $n$ の完全剰余系（complete residue system）という。
prop-congruence-relation-remainder により、各整数はちょうど 1 つの $r\in\{0,1,\dots,n-1\}$ と合同である。したがって $\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}$ はちょうど $n$ 個の元からなり、$0,1,\dots,n-1$ は完全剰余系である（群の言葉では、加法群 $\mathbb{Z}$ の部分群 $n\mathbb{Z}$ による剰余類であり、剰余類 の記事の命題「法 n の剰余類の個数」と同じ内容である）。どの 2 つも合同でない $n$ 個の整数は各剰余類から 1 つずつとったものになるので、たとえば法 $7$ では $-3,-2,-1,0,1,2,3$ も完全剰余系である。
直感
合同式 $a\equiv b\pmod n$ は「$a$ と $b$ は $n$ の倍数の違いを無視すれば等しい」という主張である。整数を $n$ で割った余りだけを見る世界では、$n$ はゼロと同じに扱われる。時計の文字盤は $n=12$、曜日は $n=7$、偶数・奇数の区別は $n=2$ の場合である。
等式と同じように、両辺に同じ数を足したり掛けたりしてよく、合同式どうしを辺ごとに足したり掛けたりしてもよい（prop-congruence-relation-arithmetic）。そのため、大きな数の余りを、途中で何度も余りに置き換えながら計算できる。ただし等式との違いが 2 つある。第 1 に、両辺を同じ数で割ることは一般にはできない。第 2 に、冪の指数を法 $n$ の余りに置き換えることはできない（ex-congruence-relation-exponent）。
例と反例
$10\equiv1\pmod9$ なので、prop-congruence-relation-arithmetic により $10^k\equiv1\pmod9$（$k\ge0$）である。したがって $10$ 進表記 $a=d_m10^m+\dots+d_110+d_0$ について
$$
a\equiv d_m+\dots+d_1+d_0\pmod9
$$
であり、整数を $9$ で割った余りは各桁の数字の和を $9$ で割った余りに等しい。たとえば $123456789$ の数字の和は $45$ で、$9$ で割り切れるので $123456789$ も $9$ で割り切れる。$10\equiv1\pmod3$ でもあるので、$3$ についても同じ判定法が成り立つ。$10\equiv-1\pmod{11}$ からは、$a\equiv d_0-d_1+d_2-\cdots\pmod{11}$（一の位から交互に足し引きした和）が得られる。
法 $4$ の完全剰余系 $0,1,2,3$ の平方は $0,1,4,9\equiv0,1,0,1\pmod4$ である。任意の整数はこのどれかと合同なので、平方数を $4$ で割った余りは $0$ か $1$ に限る。2 つの平方数の和を $4$ で割った余りは $0,1,2$ のどれかであり、$3$ にはならない。よって $4$ で割って $3$ 余る整数（$3,7,11,\dots$）は 2 つの平方数の和で書けない（逆にどの整数が 2 つの平方数の和になるかは Fermatの二平方定理 が答える）。同様に、奇数 $1,3,5,7$ の平方はすべて $1\pmod8$ である。
$2\cdot1\equiv2\cdot3\pmod4$ である（差は $4$）が、$1\not\equiv3\pmod4$ である。同様に $2\cdot3\equiv4\cdot3\pmod6$ だが $2\not\equiv4\pmod6$ である。1 つ目では消した数 $2$ と法 $4$ の最大公約数が $2$、2 つ目では消した数 $3$ と法 $6$ の最大公約数が $3$ であり、どちらも消した数が法と互いに素でない。この例は「$ca\equiv cb\pmod n$ かつ $c\not\equiv0\pmod n$ ならば $a\equiv b\pmod n$」という含意を破る。消してよい条件は thm-congruence-relation-cancellation で与える。
$1\equiv4\pmod3$ であるが、$2^1=2$ と $2^4=16\equiv1$ は $3$ を法として合同でない。この例は「$k\equiv k'\pmod n$ ならば $a^k\equiv a^{k'}\pmod n$」という含意を破る。冪の指数を置き換えてよいのは法 $n$ ではなく別の数を法とする場合であり、$a$ と $n$ が互いに素なら指数を Eulerのφ関数 の値 $\varphi(n)$ を法として置き換えてよい（Eulerの定理(整数論)）。冒頭の $7^{2026}$ の計算で指数 $2026$ を $4$ で割った余りに置き換えたのはこの形である。
$x^2\equiv1\pmod8$ は $x\equiv1,3,5,7\pmod8$ の 4 個の解をもつ（ex-congruence-relation-squares）。素数 $p$ を法とすれば、最高次の係数が $p$ で割り切れない $d$ 次の整数係数多項式 $f$ について、$f(x)\equiv0\pmod p$ の解は法 $p$ で高々 $d$ 個である（平方剰余 の記事の補題「法 p での根の個数」）が、この例は法が素数であるという仮定を外すと「2 次の合同式の解は高々 2 個」という含意が破れることを示す。法 $8$ では $2\cdot4\equiv0$ となる $0$ でない剰余類の積があり、ex-congruence-relation-cancellation-fails と同じく割り算ができないことが原因である。
性質
同値関係であること
$n$ を正の整数とする。任意の整数 $a,b,c$ について
- （反射律）$a\equiv a\pmod n$。
- （対称律）$a\equiv b\pmod n$ ならば $b\equiv a\pmod n$。
- （推移律）$a\equiv b\pmod n$ かつ $b\equiv c\pmod n$ ならば $a\equiv c\pmod n$。
$a-a=0=n\cdot0$ である。$a-b=nk$ なら $b-a=n(-k)$ である。$a-b=nk$、$b-c=nl$ なら $a-c=(a-b)+(b-c)=n(k+l)$ である。$\square$
和・差・積との両立
$n$ を正の整数とし、$a\equiv a'\pmod n$、$b\equiv b'\pmod n$ とする。このとき
- $a+b\equiv a'+b'\pmod n$、$a-b\equiv a'-b'\pmod n$。
- $ab\equiv a'b'\pmod n$。
- 任意の整数 $k\ge0$ について $a^k\equiv a'^k\pmod n$。
- 任意の整数係数の多項式 $f$ について $f(a)\equiv f(a')\pmod n$。
$a-a'=ns$、$b-b'=nt$ とおく。
- $(a+b)-(a'+b')=n(s+t)$、$(a-b)-(a'-b')=n(s-t)$ である。
- $ab-a'b'=a(b-b')+b'(a-a')=n(at+b's)$ である。
- $k=0$ では両辺とも $1$ である。$a^k\equiv a'^k$ なら、2 を $a^k\equiv a'^k$ と $a\equiv a'$ に使って $a^{k+1}\equiv a'^{k+1}$ を得る。$k$ に関する帰納法による。
- $f(x)=c_mx^m+\dots+c_1x+c_0$（$c_i\in\mathbb{Z}$）とすると、3 と 2（$c_i\equiv c_i$ との積）により $c_ia^i\equiv c_ia'^i$ であり、1 を繰り返して和をとればよい。$\square$
この命題により、剰余類どうしの和と積を
$$
\bar a+\bar b:=\overline{a+b},\qquad \bar a\,\bar b:=\overline{ab}
$$
と代表元を使って定めても、代表元の選び方によらない。こうして $\mathbb{Z}/n\mathbb{Z}$ は零元 $\bar0$、単位元 $\bar1$ をもつ可換環になる（剰余環 の記事の例「整数の剰余環」）。合同式による計算は、この環での計算と同じことである。
約分の条件
$n$ を正の整数、$a,b,c$ を整数とし、$d:=\gcd(c,n)$ とおく。このとき
$$
ca\equiv cb\pmod n\iff a\equiv b\pmod{\frac nd}
$$
である。特に $c$ と $n$ が互いに素ならば、$ca\equiv cb\pmod n$ と $a\equiv b\pmod n$ は同値である。
$c=0$ なら $d=n$ で、両辺とも常に成り立つ（左辺は $0\equiv0$、右辺は法 $1$）。以下 $c\neq0$ とし、$c=dc'$、$n=dn'$ と書く。$\gcd(c',n')=1$ である（Bézoutの等式により $cx+ny=d$ となる整数 $x,y$ があり、両辺を $d$ で割ると $c'x+n'y=1$ となるので、$c'$ と $n'$ の公約数は $1$ を割り切る）。
(⇐) $a-b=n'k$ なら $ca-cb=dc'n'k=nc'k$ なので $ca\equiv cb\pmod n$ である。
(⇒) $n\mid c(a-b)$ とすると $dn'\mid dc'(a-b)$ で、$d\neq0$ で割って $n'\mid c'(a-b)$ である。$c'x+n'y=1$ の両辺に $a-b$ を掛けると
$$
a-b=x\cdot c'(a-b)+n'y(a-b)
$$
であり、右辺の 2 項はどちらも $n'$ で割り切れるので $n'\mid a-b$ である。$\square$
ex-congruence-relation-cancellation-fails の $2\cdot1\equiv2\cdot3\pmod4$ では $d=\gcd(2,4)=2$ なので、この定理から正しく言えるのは $1\equiv3\pmod2$ である。Gauss は Art. 22 で、消す数 $k$ が法 $m$ と互いに素なら法はそのまま、最大公約数 $e$ をもつなら法が $m/e$ に下がることを述べている（Gau01 Art. 22）。
逆元と一次合同式
整数 $a$ について、$ax\equiv1\pmod n$ となる整数 $x$ を、$a$ の法 $n$ での逆元という。これは環 $\mathbb{Z}/n\mathbb{Z}$ で $\bar a$ が単元であり $\bar x$ がその逆元であることと同じである。
$n$ を正の整数、$a$ を整数とする。$ax\equiv1\pmod n$ となる整数 $x$ が存在するための必要十分条件は、$a$ と $n$ が互いに素であることである。このとき $x$ は法 $n$ でただ 1 つに決まる。
$\gcd(a,n)=1$ なら、Bézoutの等式により $ax+ny=1$ となる整数 $x,y$ があり、$ax\equiv1\pmod n$ である。逆に $ax=1+nk$ なら $ax-nk=1$ なので、$a$ と $n$ の公約数は $1$ を割り切り、$\gcd(a,n)=1$ である。$ax\equiv ax'\equiv1$ なら、thm-congruence-relation-cancellation（$\gcd(a,n)=1$）により $x\equiv x'\pmod n$ である。$\square$
たとえば $3\cdot7=21\equiv1\pmod{10}$ なので $7$ は法 $10$ での $3$ の逆元である。一方 $2$ と $10$ は互いに素でないので、$2x\equiv1\pmod{10}$ は解をもたない（$2x-1$ は奇数で、$10$ で割り切れない）。実際に逆元を求めるには、拡張Euclid互除法で Bézout の等式の係数を計算すればよい（Bézoutの等式 の記事の命題「互除法による係数の計算」）。この命題から、$n$ が素数 $p$ のときは $p$ の倍数でないすべての整数が逆元をもち、$\mathbb{Z}/p\mathbb{Z}$ は体になる。$n\ge2$ が合成数 $n=rs$（$1< r,s< n$）なら $\bar r\,\bar s=\bar0$ で $\bar r\neq\bar0$ なので $\bar r$ は逆元をもたず、$\mathbb{Z}/n\mathbb{Z}$ は体でない。
$n$ を正の整数、$a,b$ を整数とし、$d:=\gcd(a,n)$ とおく。合同式 $ax\equiv b\pmod n$ が整数解 $x$ をもつための必要十分条件は $d\mid b$ である。解をもつとき、解は法 $n$ でちょうど $d$ 個あり、1 つの解を $x_0$ とすると解全体は
$$
x\equiv x_0,\ x_0+\frac nd,\ x_0+2\frac nd,\ \dots,\ x_0+(d-1)\frac nd\pmod n
$$
である。
解 $x$ があれば $b=ax-nk$ は $a$ と $n$ の公約数 $d$ で割り切れる。
逆に $d\mid b$ とし、$a=da'$、$b=db'$、$n=dn'$ と書く。$d\ge1$ なので $n\mid ax-b$ は $n'\mid a'x-b'$ と同値であり、$ax\equiv b\pmod n$ は $a'x\equiv b'\pmod{n'}$ と同値である。$\gcd(a',n')=1$ なので（prf-congruence-relation-cancellation と同じ理由）、prop-congruence-relation-inverse により法 $n'$ での $a'$ の逆元 $u$ があり、$a'x\equiv b'\pmod{n'}$ は $x\equiv ub'\pmod{n'}$ と同値である（掛けて $a'u\equiv1$ を使う方向と、$a'$ を掛け戻す方向）。よって解全体は $x_0+n'\mathbb{Z}$（$x_0=ub'$）である。$x_0+n'j$（$j\in\mathbb{Z}$）の法 $n$ での類は $j$ を $d$ で割った余りだけで決まり（$n'd=n$）、$j=0,1,\dots,d-1$ に対する $d$ 個は、差 $n'(j-j')$（$0<|j-j'|< d$）が $n$ で割り切れないので互いに合同でない。$\square$
たとえば $6x\equiv4\pmod{10}$ では $d=2\mid4$ なので解は法 $10$ で 2 個ある。$3x\equiv2\pmod5$ に直し、$3$ の法 $5$ での逆元 $2$ を掛けて $x\equiv4\pmod5$、すなわち $x\equiv4,9\pmod{10}$ である。実際 $6\cdot4=24$、$6\cdot9=54$ はどちらも $10$ で割って $4$ 余る。$6x\equiv5\pmod{10}$ は $2\nmid5$ なので解をもたない。合同式を複数連立させた場合は 中国剰余定理 が、法が合成数のときの高次の合同式は 合成数を法とする合同式 の記事が扱う。
法の取り替え
$m,n$ を正の整数、$a,b$ を整数とする。
- $m\mid n$ かつ $a\equiv b\pmod n$ ならば $a\equiv b\pmod m$ である。
- $a\equiv b\pmod m$ かつ $a\equiv b\pmod n$ ならば、$m$ と $n$ の最小公倍数 $L$ について $a\equiv b\pmod L$ である。特に $m,n$ が互いに素なら $a\equiv b\pmod{mn}$ である。
2 は、互いに素な法ごとの情報を 1 つの法にまとめる操作であり、中国剰余定理 の一意性の部分にあたる。
補足
合同式は初等整数論の基本言語であり、次の定理はすべて合同式で述べられる。素数 $p$ と $p$ の倍数でない $a$ について $a^{p-1}\equiv1\pmod p$ となる Fermatの小定理、それを一般の法に広げた Eulerの定理(整数論)、$(p-1)!\equiv-1\pmod p$ を述べる Wilsonの定理、連立合同式を解く 中国剰余定理、冪がすべての既約な剰余類を尽くす 原始根、平方数の余りを調べる 平方剰余 である。計算の場面では、検算（ex-congruence-relation-casting-out-nines）や、RSA暗号などの公開鍵暗号における大きな数の冪の余りの計算に使われる（Ste17 の PDF 版 §2.3（p. 31）、§3.3（p. 56））。
prop-congruence-relation-arithmetic は「和と積の演算と両立する同値関係」という性質を述べている。一般に、演算をもつ集合（群・環・モノイドなど）の上の同値関係で演算と両立するものを合同関係（congruence relation）といい、合同関係による商集合には演算が自然に定まる。整数の合同式はその原型であり、環 $\mathbb{Z}$ の合同関係はイデアル $n\mathbb{Z}$ と 1 対 1 に対応する（環の合同関係とイデアルの対応）。モノイドの場合は 可換モノイドの合同関係 の記事が扱う。
関連項目
- 前提: 整数, 除法の原理, 最大公約数, Bézoutの等式, 同値関係
- 比較: 剰余類, 剰余環, 可換モノイドの合同関係
- 直後に読む: 中国剰余定理, Fermatの小定理, Eulerのφ関数, Eulerの定理(整数論)
- 発展: 合成数を法とする合同式, 平方剰余, 原始根, Wilsonの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
