1.3.1　同余的性质

1.同余的定义

两个整数除以同一个整数，若得相同余数，则二整数同余.最先引用同余的概念与符号者为德国数学家高斯.

设m是大于1的正整数，a，b是整数，如果m|（a-b），则称a与b关于模m同余，记作a≡b（mod m），读作a与b对模m同余，或a同余于b模m.

对同余，也可以理解成相同的余数，当然要求除数是相同的.

mod m称为模运算，或求余运算.C语言的运算符“％”就是求余运算.模运算在数论和信息技术领域都有着广泛的应用，从奇偶数的判别到素数的判别，从最大公约数的求法到孙子问题求解，从恺撒密码到公钥密码，都涉及模运算.

2.同余与整除的关系

显然，有如下事实：

（1）若a≡0（mod m），则m|a；

（2）a≡b（mod m）等价于a与b分别用m去除，余数相同.

证　充分性：设a=mq1+r1，b=mq2+r2，0≤r1<m，0≤r2<m.

因为a≡b（mod m），a-b≡0（mod m），m|（a-b），a-b=m（q1-q2）+（r1-r2），则有m|（r1-r2）.

因为0≤r1<m，0≤r2<m，所以0≤|r1-r2|<m，即r1-r2=0，所以r1=r2.

必要性：设a，b用m去除余数为r，即a=mq1+r，b=mq2+r，a-b=m（q1-q2），所以m|（a-b），故a≡b（mod m）.

3.同余的性质

（1）反身性：a≡a（mod m）；

（2）对称性：若a≡b（mod m），则b≡a（mod m）；

（3）传递性：若a≡b（mod m），b≡c（mod m），则a≡c（mod m）.

证　上述性质很容易证明，下面仅证明（3）.

因为a≡b（mod m），所以m|（a-b），同理m|（b-c），故m|[（a-b）+（b-c）]，所以m|（a-c）.故a≡c（mod m）.

4.线性运算

如果a≡b（mod m），c≡d（mod m），那么：

（1）a±c≡b±d（mod m）；

（2）ac≡bd（mod m）.

证　（1）因为a≡b（mod m），故m|（a-b），同理m|（c-d），所以m|[（a-b）±（c-d）]，故m|[（a±c）-（b±d）]，即a±c≡b±d（mod m）.

（2）因为ac-bd=ac-bc+bc-bd=c（a-b）+b（c-d），又m|（a-b），m|（c-d），故m|（ac-bd），所以a*c≡b*d（mod m）.

5.除法，消去律

若ac≡bc（mod m），c≠0，则a≡b（mod（m/（c，m））），其中（c，m）表示c，m的最大公约数.

特殊地若（c，m）=1，则a≡b（mod m）.

6.乘方

如果a≡b（mod m），那么an≡bn（mod m）.

7.其他

（1）若a≡b（mod m），n|m，则a≡b（mod n）；

（2）若a≡b（mod mi），i=1，2，…，n，则a≡b（mod [m1，m2，…，mn]），其中[m1，m2，…，mn]表示m1，m2，…，mn的最小公倍数.