中国余数定理(Chinese Remainder Theory,CRT)目前我还没有看出什么用处，作为数论里一个知识罗列一下吧。所以叫中国余数 定理，是因为据信他是中国古代数学家在公元100年左右发现的。

笛卡儿积

笛卡儿积是集合论中很重要的概念，已知一组集合S₁、S₂、...、S_n，他们的笛卡儿积S定义为：

 S = {(x1,x2,...,n) |
  x1 ∈S1，
  x2 ∈S2，
  ......
  xn ∈Sn}

一个相关的概念叫关系，集合族S₁、S₂、...、S_n的一个关系定义为 他们的笛卡儿积S的一个子集。如果这个子集是空集或者S本身，则称这个关系是一个平凡关系。

举例而言，集合N和N的笛卡儿集合为二维空间集合{(x,y) | x,y∈N}，而关系y=2x可以表示为笛卡儿集合的一个子集 {(x,2x)|x∈N}

映射

集合X和Y，如果存在一种关系，使得X中的任意一个元素x都对应于集合Y的一个元素y或者一组元素y，则称呼这种关系为X集合到 Y集合的一个映射，记做f:x→y。其中x称作y在X中的原象，y称为x在Y中的象。有时，映射也记做y = f(x)

如果X中任意一个元素在Y中只有一个象，称这个映射为一个单射。如果y中任意一个元素在X中都存在一个原象，则称呼映射为满射。

映射f:x→y，如果能找到象到原象的映射，则称为该映射的逆映射。

一个映射如果既是单射又是满射，则称该映射为一个一一映射

距离算子

集合S上定义的距离算子ρ指得是S×S到非负实数集合R+上得一个映射满足：

1. ρ(x,y) ≥0，且当且仅当x=y时取0，非负律
2. ρ(x,y) = ρ(y,x) 交换律
3. ρ(x,y) + ρ(y,z) ≥ ρ(x,z) 三角公式

运算

集合S上定义的二元运算是指S×S 到S的一个单射，即任意x,y∈S 存在z∈S，z = x⊙y是S×S中元素(x,y)在S中的象，其中⊙称呼 为这个运算的运算符，运算也可以表示为一个二元函数关系，记做z = ⊙(x,y)

同态映射和同构映射

集合X到Y上的一个一一映射f，X、Y上分别定义了运算+和×（注意，这是抽象运算，和四则运算中的对应符号没有关系），
如果对于X中的任意元素x1、x2，他们在Y中的象分别是y1、y2，如果
 x3=x1 +x2
 y3=y1 ×y2
则y3是x3在Y上的象，也就是说
f(x1 +x2) = f( x1) × f( x2)
则称这个映射f为集合X到Y的一个同态映射。如果X,Y上还定义距离算子ρ和ρ'，且满足ρ(x1,x2) ＝ρ'(y1,y2) ，则称
这个同态映射为同构映射。

中国余数定理

也就是说，存在映射关系

    A ∽(a1,a2,...,an)
    B ∽(b1,b2,...,bn)
    则
    (A+B) mod M ∽((a1+b1) mod m1,(a2+b2) mod m2,..,(an+bn) mod mn)
    (A-B) mod M ∽((a1-b1) mod m1,(a2-b2) mod m2,..,(an-bn) mod mn)
    (A×B) mod M ∽((a1×b1) mod m1,(a2×b2) mod m2,..,(an×bn) mod mn)

A 到(a₁,a₂,...,a_n)的映射很简单，用关系式

 ai = A mod mi 

计算即可。

对于反向映射，可以这样计算：

 定义Mi = M / mi
 则由于mi和其他任意mj互质，Mi和mi也互质，根据
 欧几里德算法和扩展欧几里德算法一文中所述，Mi
 存在唯一的模mi的逆元Mi，令
  ci = Mi Mi
 则A = (a1c1 + a2c2 + ... + ancn) mod M

下面举一个例子，假设整数4×9×25 ＝ 900，数729是900的完全余数集中的一个元素，则按照上述关系可以得到对应关系

 729  ->   (1,0,4)
 由(1,0,4)计算729可以这样进行：
 M1 = 9*25 = 225，M1-1 mod 4 = 1
 M2 = 4*25 = 100，M2-1 mod 9 = 1
 M3 = 4*9 = 36，M3-1 mod 25 = 16
 则729 = ( 1* 1 * 225 + 0 * 1 * 100 + 4 * 16 *36) mod 900

这也是一个古题的传统解法：一个数，被3除余一，被5除余2，被7除余一，问这个数是多少？套用上面公式，计算也太简单了。 也就是M=3×5×7=105，计算105和(3,5,7)完全余数集之间的映射关系而已。

这个问题可以统一表述为：已知整数m₁、m₂、...、m_n彼此互质，则求整数x的 方程

 x mod m1 = a1
 x mod m2 = a2
                 .......
 x mod mn = an
有模M的唯一解，M =所有mi的乘积
实际上，上述叙述是CRT的另外一种表示形式，证明也很容易，在此我就不在赘述了。