中国の剰余定理
一般に、三つずつにして物を数え、一余ると、その度に七十と置く。五で割った余りに二十一をかける。七で割った余りに十五をかける。百六以上ならば、百五を引くことで、答えを得る。
この問題がいつ頃から知られていたかについては定かではない。この問題は、『孫子算経』とともに日本にも伝わり、後に和算の隆盛した江戸時代には、「百五減算」として知られた。
13世紀、南宋末の数学家秦九韶は、一次合同式をユークリッドの互除法と同等の方法で解くことで、中国の剰余定理と同等の結果を得ていた。このことは、宣教師によって19世紀のヨーロッパにも伝えられ、ガウスの方法と同等のものであることが確かめられた。
"Chinese remainder theorem"という名前の使用は、少なくともアメリカの数学者レオナード・E・ディクソンによる著書 Introduction to the Theory of Numbers (1929) の中に見られる。
(解の存在) 二つの整数 m, n が互いに素ならば、ユークリッドの互除法により適当な整数 u, v が存在して、
mu + nv = 1
となるようにできる。このとき、
mu ≡ 1 (mod n),
nv ≡ 1 (mod m)
が成り立つので、
x = anv + bmu
とおくと、
x = a(1 − mu) + bmu = a + (b − a) mu ≡ a (mod m)
また、
x = anv + b(1 − nv) = b + (a − b) nv ≡ b (mod n)
x は与えられた連立合同式の解となる。
(解の一意性) y を任意の解とすると、x − y は
x − y ≡ 0 (mod m),
x − y ≡ 0 (mod n)
を満たす。よって、x − y は m と n との公倍数であるが、m と n とは互いに素なので、それらの最小公倍数 mn の倍数となり、
x − y ≡ 0 (mod mn)
すなわち、x と y とは法 mn に関して合同になる。 Q.E.D.