数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。

同余符号

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对模m同余或a同余于b模m。记作a≡b(mod m) 【定义】 设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)。显然有如下事实： 1、若a≡0(mod m)，则m|a; 2、a≡b(mod m)等价于a与b分别用m去除，余数相同。 证明：
充分性：
若a和b用m相除留下相同的余数r，则 a=q1m+r, b=q2m+r,q1和q2为某两个整数，由此的a-b=(q1m+r)-(q2m-r)=m(q1-q2)，根据整除定义，我们有m|(a-b)，由同余式定义得出结论：a≡b(mod m) 必要性：
若a和b用m相除留下相同的余数r，则 a=q1m+r,b=q2m+r,所以a-b=m(q1-q2) 故 m|(a-b)。

性质

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) 4、同余式相加：若a≡b(mod m)，b≡c(mod m)，则a ± c≡b ± d(mod m) 5、同余式相乘：若a≡b(mod m)，b≡c(mod m)，则ac≡bd(mod m) 6、线性运算：如果a≡b(mod m)，c≡d(mod m)，那么a ± c≡b ± d(mod m)，且a * c≡b * d(mod m) 7、除法：若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数。特殊地 ,gcd(c,m)=1 则a ≡ b (mod m) 8、幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m) 9、若a ≡ b (mod m)，n|m,则 a ≡ b (mod n) 10、若a ≡ b (mod mi) (i=1,2…n) 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍数

相关定理

1、欧拉定理 2、费马小定理 3、中国剩余定理（孙子定理）