數學英文

同餘運算

最早的同餘運算 (Modular arithmetic) 問題出自《孫子算經》的「物不知數」， 俗稱為「韓信點兵」；在主流的數學史上，它出自高斯 (Carl Gauss) 在西元 1789 年寫成的劃時代巨著《算術研究》(Disquisitiones Arithmeticae， 這是拉丁文，英譯為 Arithmetic Investigations)。

同餘運算已經逐漸移出了中學數學課程，但是它還留在潛課程裡： 保存在課外練習與考古題庫裡。

同餘運算的基本觀念是模除 (modulo operation)，它是一種二元運算： 當 \(m\) 與 \(n\) 皆為正整數時，modulo 就是取整數除法的餘數。 例如 \(15\bmod 4=3\)：15 modulo 4 is equal to 3，其中 modulo 可以讀作 mod。 在數學裡，modulo 沒有專屬的算子符號 (operator)，就寫 mod； 但是電腦程式語言經常以百分號 % 表示 modulo，例如 \(14\;\text{%}\;4\) 得到 2， 此時應將 % 讀作 mod。 當 modulo 的兩個運算元素不全是正整數時，例如 \((-14)\;\text{%}\;4\) 或者 \(14 \;\text{%}\;(-4)\)，它們沒有全球公認的定義， 需要先確認它的定義。

但是模除的精彩之處是定義了正整數之間的一種關係：同餘關係 (Congruence Modulo)。 給定一個大於 1 的整數 \(p\)：Given an integer \(p\gt1\)， 用它當作「模」或「模數」(modulus)， 則 \(m\) 與 \(n\) 對 \(p\) 同餘記作 \(m\equiv n \pmod p\)， 讀作 \(m\) is congruent to \(n\) mod \(p\)， 或者 \(m\) is equivalent to \(n\) mod \(p\)， 其中 mod 仍然是 modulo 的縮寫， 意思是 \(m\) 除以 \(p\) 和 \(n\) 除以 \(p\) 的餘數相等， 用 modulo operation 表達就是 \[m\bmod p=n\bmod p\] 例如 \(17\equiv 3\pmod4\)。 「韓信點兵」問題就是一元聯立同餘方程 (system of modular equations in one variable)： \[\left\{\begin{matrix} x\equiv 2 \pmod3\\ x\equiv 3 \pmod5 \\ x\equiv 2 \pmod7 \end{matrix}\right.\] 則 \(x\) 之所有可能解是對 105 同餘 23 的正整數：\(x\equiv 23\pmod{105}\)，

All possible solutions of \(x\) are positive integers equivalent to twenty-three mod one hundred and five.