如果兩個整數 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 使得 
。現在令 
為整數，滿足
.
或 
，因此 
。。然後，
，這表明 
。 且 
，我們得到 
和 
。，則 
