余数性质

1. 同余式及其应用
定义:设a、b、m为整数（m＞0），若a和b被m除得的余数相同，则称a和b对模m同余.记为 或
一切整数n可以按照某个自然数m作为除数的余数进行分类，即n=pm+r（r=0，1，…，m-1），恰好m个数类.于是同余的概念可理解为,若对n1、n2，有n1=q1m+r，n2=q2m+r，那么n1、n2
对模m的同余，即它们用m除所得的余数相等.
利用整数的剩余类表示,可以证明同余式的下述简单性质:
(1) 若 ,则m|(b-a).反过来,若m|(b-a),则 ;
(2) 如果a=km+b(k为整数),则 ;
(3) 每个整数恰与0,1,…，m-1，这m个整数中的某一个对模m同余；
(4) 同余关系是一种等价关系：
① 反身性 ；
② 对称性 ，则 ，反之亦然.
③ 传递性 ， ，则 ；
（5）如果 ， ，则
① ；
② 特别地