同餘
定義 給定一個整數m（m>1）, 如果任意兩個整數a, b被m除時所得的餘數相同，那麼我們就說a和b是模m同餘的。記為a≡b（mod m）, 如果餘數不相同，就說a和b對模m不同餘，記為ab（mod m）.
此時13≡17（mod 4），繼續思考②-①，得到17-13=4×1，即4|(17-13).抽象的看對於a≡b（mod m），可知
用③-④有 a-b=(q-p)×m，故m|(a-b). 反之，若m|(a-b)，可知
(a-b)≡0（mod m）, 由此易知
a≡b（mod m）. 所以a和b是模m同餘的。
綜上分析可知
a≡b（mod m） iff m|(a-b).
特別的
換句話說，整除也可以由同餘來定義。注:iff 意思是 若且唯若。
1. a和b是模m同餘的,即a≡b（mod m）.
同餘符號記法的優點:在形式上同餘式具有普通等式的性質。對於等式來說，有
性質
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條性質，只需證明 m|(a-c).
由於
a≡b（mod m）,
b≡c（mod m）,
可知
m|(a-b),
m|(b-c),
因此存在整數q, p使得
a=b+qm,
b=c+pm,
所以
a=b+qm，
c=b-pm,
兩式相減
a-c=(q+p)m,
知
m|(a-c). □
注:對於普通等式有 a-b=0 iff a=b,
同餘式也有
(a-b)≡0（mod m） iff a≡b（mod m）.