对于整数除以某个正整数的问题，如果只关心余数的情况，就产生同余的概念。
定义1 用给定的正整数m分别除整数a、b，如果所得的余数相等，则称a、b对模m同余，记作a≡b(mod m)，如 56≡0 (mod 8)
定理1 整数a,b对模m同余的充要条件是 a-b能被m整除（即m|a-b）。
证 ：设a=mq1+r1, 0<=r1<m; b=mq2+r2, 0<=r2<m.
若a≡b(mod m)，按定义1，r1=r2,于是a-b=m(q1+q2),即有m|a-b.
反之，若m|a-b,即m|m(q1-a2)+r1-r2，则m|r1-r2，但|r1-r2|<m，故r1=r2,即a≡b(mod m)。
推论 a≡b(mod m)的充要条件是a=mt+b（t为整数）。
表示对模m同余关系的式子叫做模m的同余式，简称同余，同余式的记号是高斯（Gauss）在1801年首先使用的。
定理2 同余关系具有反身性、对称性与传递性，即
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), c≡d (mod m),则
1）a+c≡b+d (mod m);
2）a-c≡b-d (mod m);
3）ac≡bd (mod m).
多于两个的同模同余式也能够进行加减乘运算。
对于乘法还有下面的推论：
推论 若a≡b(mod m),n为自然数，则an≡bn (mod m)。
