模除

模除是一種不具交換性的二元運算。

基本介紹

• 中文名：模除
• 學科：數學

簡介

模除（又稱模數、取模操作、取模運算等，英語：modulo有時也稱作 modulus）得到的是一個數除以另一個數的餘數。

給定兩個正整數：被除數a和除數n，amodulon(縮寫為amodn)得到的是使用歐幾里德除法時a/n的餘數。 舉個例子：計算表達式 "5 mod 2" 得到 1，因為 5÷2=2...1（5 除以 2 商 2 余 1）；而 "9 mod 3" 得到 0，因為 9÷3=3...0；注意：如果使用計算器做除法，不能整除時，你不會得到商，而是會得到一個小數，如：5÷2=2.5。

雖然通常情況下a和n都是整數，但許多計算系統允許其他類型的數字操作，如：對浮點數取模。一個整數對n取模的結果範圍為： 0 到n− 1（amod 1恆等於 0；amod 0則是未定義的，在程式語言里可能會導致除零錯誤）。 有關概念在數論中的套用請參閱模算數。

當a和n均為負數時，通常的定義就不適用了，不同的程式語言對結果有不同的處理。

用途

• 取模運算可用於判斷一個數是否能被另一個數整除。對 2 取模即可判斷整數的奇偶性；從 2 到 n-1 取模則可判斷一個數是否為質數。
• 進制之間的轉換。
• 用於求取最大公約數的輾轉相除法使用取模運算。
• 密碼學中的套用：從古老的凱撒密碼到現代常用的RSA、橢圓曲線密碼，它們的實現過程均使用了取模運算。

記號

一些計算器有取模mod()按鈕，很多程式語言里也有類似的函式，通常像mod(a,n)這樣。 有些語言也支持在表達式內使用 "%"、"mod" 或 "Mod" 作為取模或取余操作符。

• a% n

或

• a mod n

或者在一些沒有mod()函式的環境中使用等價的： （注意 'int' 事實上等價於截斷函式an，進行了向 0 取整）

• a - (n * int(a/n))

等價性

一些取模操作，經過分解和展開可以等同於其他數學運算。這在密碼學的證明中十分有用，例如：迪菲-赫爾曼密鑰交換。

• 恆等式：
• (amodn) modn=amodn
• 對所有的正數x有：nmodn= 0
• 如果p是一個質數，且不為b的因數，此時由費馬小定理有：abmodp=amodp

逆運算：

• [(−amodn) + (amodn)] modn= 0.
• bmodn表示模反元素。若且唯若b與n互質時，等式左側有定義：[(bmodn)(bmodn)] modn= 1。

分配律：

• (a+b) modn= [(amodn) + (bmodn)] modn
• abmodn= [(amodn)(bmodn)] modn
• dmod (abc) = (dmoda) +a[(d\a) modb] +ab[(d\a\b) modc]，符號\是歐幾里德除法中的除法操作符，運算結果為商
• cmod (a+b) = (cmoda) + [bc\ (a+b)] modb- [bc\ (a+b)] moda.

除法定義：僅當式子右側有定義時，即b、n互質時有：abmodn= [(amodn)(bmodn)] modn，其他情況為未定義的。

乘法逆元：[(abmodn)(bmodn)] modn=amodn.