如果两个整数 a 和 b 除以正整数 m 得到相同的（最小非负）余数，我们就称它们关于模 m 同余。其正式定义如下。
令 a、b 和 m 为整数，其中 m > 0 {\displaystyle m>0} 。如果 m 整除差 a − b {\displaystyle a-b} ，则称整数 a 和 b **关于模 m 同余**，符号表示为 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} 。
当且仅当 a 和 b 除以 m 得到相同的最小非负余数时，我们有 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} 。
证明
令 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} 。则存在整数 c 使得 c m = a − b {\displaystyle cm=a-b\,} 。现在令 q , q ′ , r , r ′ {\displaystyle q,q',r,r'\,} 为整数，满足
a = q m + r , 0 ≤ r < m {\displaystyle a=qm+r,\quad 0\leq r<m}
以及
b = q ′ m + r ′ , 0 ≤ r ′ < m {\displaystyle b=q'm+r',\quad 0\leq r'<m} .
由此可得
c m = a − b = m ( q − q ′ ) + ( r − r ′ ) {\displaystyle cm=a-b=m(q-q')+(r-r')\,}
这产生了 m | ( r − r ′ ) {\displaystyle m|(r-r')\,} 或 m divides ( r − r ′ ) {\displaystyle m\ {\mbox{divides}}\ (r-r')\,} ，因此 r = r ′ {\displaystyle r=r'\,} 。
现在假设 r = r ′ {\displaystyle r=r'\,} 。然后， a − b = m ( q − q ′ ) {\displaystyle a-b=m(q-q')\,} ，这表明 m | ( a − b ) {\displaystyle m|(a-b)\,} 。
首先，如果 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} 且 c ≡ d ( mod m ) {\displaystyle c\equiv d{\pmod {m}}} ，我们得到 a c ≡ b d ( mod m ) {\displaystyle ac\equiv bd{\pmod {m}}} 和 a + c ≡ b + d ( mod m ) {\displaystyle a+c\equiv b+d{\pmod {m}}} 。
因此，如果 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} ，则 a p ≡ b p ( mod m ) {\displaystyle a^{p}\equiv b^{p}{\pmod {m}}}
。如果 m 整除差 
，则称整数 a 和 b **关于模 m 同余**，符号表示为 
。。。则存在整数 c 使得 
。现在令 
为整数，满足
.
或 
，因此 
。。然后，
，这表明 
。 且 
，我们得到 
和 
。，则 
