數學英文

同餘運算

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

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

同餘運算的基本觀念是模除 (modulo operation),它是一種二元運算: 當 \(m\) 與 \(n\) 皆為正整數時,modulo 就是取整數除法的餘數。 例如 \(17\bmod 4=3\):17 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.
也就是 \(x=23+105k\),其中 \(k\) 為正整數或 0。

[語音講解:modulo.mp3]

[ 回上層 ]


Created: July 17, 2022
Last Revised: 7/30, 9/18
© Copyright 2022 Wei-Chang Shann 單維彰     [Home Page]
shann@math.ncu.edu.tw