定义：若整数a和整数b除以正整数m的余数相等,则称a，b模m同余，记为(a equiv b (mod m ))
性质:
[1.a equiv a(mod m)(自反性)\
2.若a equiv b(mod m),则b equiv a(mod m)（对称性) \
3.若a equiv b(mod m)，b equiv c(mod m),则a equiv c(mod m)(传递性)\
4.若a equiv b(mod m),则a+c equiv b+c(mod m)（同加性) \
5.若a equiv b(mod m),则若a*c equiv b*c(mod m)(同乘性)\
6.若a equiv b(mod m),则若a^n equiv b^n(mod m),则（同幂性)\
7.a*b mod k=(a mod k)*(b mod k) mod k \
8 若a mod p =x,a mod q=x,p perp q，则a mod p*q=x \
9.若a equiv b(mod m),也frac{a}{n}
ot equiv frac{b}{n} (mod m)
]
8.证明:
[设a=s*p+x=t*q+x \
所以s*p=t*q \
因为 p perp q \
所以一定存在整数r使得s=r*q\
所以a=r*q*p+x ,所以a mod p*q =x
]
证毕
同余类与剩余类
$ quad $ 对于(forall a in [0,m-1],集合{a+km}(k in Z))中的所有数模m同余，余数都是a，该集合称为一个模m的同余类，简记为(ar{a})
$ quad $ 模m的同余类共有m个，分别为(ar{0},ar{1},cdots,overline{ m-1 }),它们构成了m的完全剩余系。
$ quad $ 1~m中与m互质的数代表的同余类共有(varphi(m))个，他们构成m的简化剩余系。
$ quad $ 简化剩余系关于模m乘法封闭（查一下"运算封闭"），这是因为若a，b((1 le a,b le m))与m互质，则ab也与m互质。再由余数的定义可得ab mod m也与m互质，即a*b mod m也属于m的简化剩余系