以前听老师说，初等数论要到大四学，今天翻到一本书，不知道讲得全不全，原来就是余数定理那一块知识，回想起来初中的时候老爹就教过我，那个时候他说的是‘中国余数定理’。

这个定理呢是老外的叫法，叫“Chinese remainder theorem”，在中国叫“孙子定理”，源于《孙子算经》（这本书的作者是不是叫孙子，不清楚，应该不会，谁愿意叫这么个名儿），书中有这样一个题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”，小时候老爹跟我说的时候，我觉得这还不简单，不就列几个方程呗，然后就不知道怎么列，还要设商，三个商不知道，加一个未知数，四个未知数三个方程，怎么解？

我们记这样一个运算：Mod，a Mod b的结果表示a除以b的余数，且是一个非负的小于b的数（a,b皆非负）。简单的理解就是，模运算是将整数打个折都射到[0,1,...b-1]这样一个区间上。

另外还有这样一个关系：≡，表示同余关系，a≡b(Mod m)就是说a Mod m=b Mod m，比如7≡2(Mod 5)。我们在自然数集上考虑这个关系，它满足：
1）自反性
a≡a(Mod m)
2）对称性
if a≡b(Mod m)，then b≡a(Mod m)
3）传递性
if a≡b(Mod m)，b≡c(Mod m)，then a≡c(Mod m)

也就是说它是一种‘等价’关系，它划分了[0],[1],...[m-1]这样m个等价类，也叫同余类。

同余式有一些非常有用的运算定律：
1）if a≡b(Mod m) and c≡d(Mod m) , then a+c≡b+d(Mod m)
2）if a≡b(Mod m) and c≡d(Mod m) , then ac≡bd(Mod m)
3）if a≡b(Mod m) k>0 , then ak≡bk(Mod mk)
4）if a≡b(Mod m) and d|a,d|b,d|m , then a/d≡b/d(Mod m/d)
5）if a≡b(Mod m) and d|m , then a≡b(Mod d)
6）if ca≡cb(Mod m) and d=gcd(c,m) , then a≡b(Mod m/d)

评论