同餘

同餘是初等數論裡的一個重要的概念，關於代數系統之間的同餘，詳見代數同餘。

概念

若兩個數$a$與$b$除以$m$的餘數相同，或說$a-b$可被$m$整除，則說$a$與$b$同餘於$m$或$a$等於$b$模$m$。

一般將「$a$與$b$同餘於$m$」記作$a \equiv b \pmod{m}$且有$a \equiv b \pmod{m} \iff m \mid a-b$，而$a \not\equiv b \pmod{m} \iff m \nmid a-b$

除整數集合外，所有整係數多項式所組成的集合，亦有類似整數的同餘存在。

性質

• 同餘是一個等價關係，是因爲它有：

1. 自反性，$a \equiv a \pmod{m};$
2. 對稱性，$a \equiv b \pmod{m} \iff b \equiv a \pmod{m};$
3. 傳遞性：$a \equiv b \pmod{m} ~~\And~~ b \equiv c \pmod{m} \Longrightarrow a \equiv c \pmod{m}.$

• 同余式運算有像通常等式那樣類似的加減乘運算：

1. 若$a \equiv c \pmod{m}$且$b \equiv d \pmod{m}$，則$(a \pm b) \equiv (c \pm d) \pmod{m}$且$ab \equiv cd \pmod{m}$；
2. 若$ac \equiv bc \pmod{m}$則$a \equiv b \pmod{\dfrac{m}{(c, m)}}$，特別地，$(c,m) = 1$，則$a \equiv b \pmod{m}$；

• 若$(a, m) = 1$，則存在一數$c$，使得$ca \equiv 1 \pmod{m}$；
• 若$a \equiv b \pmod{m}$，則$\forall d: d \mid m, a \equiv b \pmod{d}$；
• 若$d>0$，則$a \equiv b \pmod{m} \iff ad \equiv bd \pmod{md}$；
• 若$a \equiv b \pmod{m_i}, 1 \leqslant i \leqslant n$，則$a \equiv b \pmod{[m_1, m_2, \cdots, m_n]}$。

推論

設$f(x)$是整係數多項式，如果$a \equiv b \pmod{m}$，則$f(a) \equiv f(b) \pmod{m}$。

參見

• 費馬小定理
• 中國剩餘定理
• 二次剩餘
• 原根
• 循環群
• 多項式同餘
• 商環

上下節

• 上一節：惟一因子分解定理
• 下一節：同餘類