中国の剰余定理
ガウスは『整数論』(1801年)において、法 m1, m2, ..., mk に関して対称な解法を示した。
(解の存在) 整数 m1, m2, ..., mk がどの二つも互いに素ならば、
M = m1m2...mk ,
M = m1M1 = m2M2 = ... = mkMk
と置くと、各 mi と Mi とは互いに素なので、補助定理により、i = 1, 2, ..., k に対して、
Miti ≡ 1 (mod mi),
となる ti が存在する。このとき、
x ≡ a1M1t1 + a2M2t2 + ... + akMktk (mod M)
は与えられた連立合同式の解になる。 例えば、x の第1項の法 m1 に関する剰余は a1 に合同であり、第2項から第 k 項は M2 から Mk が m1 の倍数となるので、x は法 m1 に関して a1 と合同になる。 i = 2, 3, ..., k に関しても同様にして、
x ≡ ai (mod mi)
を満たすことがわかる。
(解の一意性) y を任意の解とすると、x − y は
x − y ≡ 0 (mod m1),
x − y ≡ 0 (mod m2)
...
x − y ≡ 0 (mod mk)
を満たす。よって、x − y は法 m1, m2, ..., mk で割り切れる。m1, m2, ..., mk は互いに素なので、x − y は法の最小公倍数 M で割り切れる。
x − y ≡ 0 (mod M)
すなわち、x と y とは法 M に関して合同になる。Q.E.D.