中国の剰余定理
与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同式
x ≡ a (mod m),
x ≡ b (mod n)
を満たす整数 x が mn を法として一意的に存在する。
前述の『孫子算経』の問題を考える。すなわち、連立合同式
x ≡ 2 (mod 3),
x ≡ 3 (mod 5),
x ≡ 2 (mod 7)
を同時に満たす整数 x を求める。まず、1番目の式より x = 3m1 + 2 (m1 ∈ Z) と表せる。これを2番目の式に代入し、両辺から 2 を引くと、
3m1 ≡ 1 (mod 5).
を得る。この式の両辺に 2 をかけると、(左辺)= 6m1 = 5m1 + m1 ≡ m1 (mod 5) である(これは、 Z/5Z において 2 が 3 の乗法に関する逆元であることに他ならない。)ので、
m1 ≡ 2 (mod 5)
を得る。したがって、m1 = 5m2 + 2 (m2 ∈ Z) と表せ、これにより x = 15m2 + 8 を得る。更にこれを連立合同式の3番目の式に代入すると、
15m2 + 8 ≡ 2 (mod 7)
を得る。この式の両辺から 8 を引き、また 15m2 = 14m2 + m2 ≡ m2 (mod 7) であることに注意すると、
m2 ≡ −6 (mod 7).
更にこれは、−6 ≡ 1 (mod 7) より
m2 ≡ 1 (mod 7)
と書き直せるので、m2 = 7m3 + 1 (m3 ∈ Z) と表せ、これにより x = 105m3 + 23 を得る。すなわち、
x ≡ 23 (mod 105)
が求める解である。この方法は、計算が煩雑なものになるという欠点がある一方、連立合同式の法が互いに素とならない状況、すなわち中国の剰余定理が適用できない場合においても利用できる。