在算法中mod指的是什么意思

小編給大家分享一下在算法中mod指的是什么意思，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

在算法中，mod的意思是取模，就是取余數。mod運算，即求余運算，是在整數運算中求一個整數x除以另一個整數y的余數的運算，且不考慮運算的商。

mod運算，即求余運算，是在整數運算中求一個整數 x 除以另一個整數y的余數的運算，且不考慮運算的商。在計算機程序設計中都有MOD運算，其格式為： mod(nExp1,nExp2)，即是兩個數值表達式作除法運算后的余數。

模p運算編輯

給定一個正整數p，任意一個整數n，一定存在等式

n = kp + r 其中k、r是整數，且 0 ≤ r < p，稱呼k為n除以p的商，r為n除以p的余數。

對于正整數p和整數a,b，定義如下運算：

取模運算：a mod p 表示a除以p的余數。

模p加法：(a + b) mod p ，其結果是a+b算術和除以p的余數，也就是說，(a+b) = kp +r，則 (a+b) mod p = r。

模p減法：(a-b) mod p ，其結果是a-b算術差除以p的余數。

模p乘法：(a × b) mod p，其結果是 a × b算術乘法除以p的余數。

可以發現,模p運算和普通的四則運算有很多類似的規律，如：

簡單的證明其中第一個公式：

((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p

假設

a = k1*p + r1

b = k2*p + r2

c = k3*p + r3

a+b = (k1 + k2) p + (r1 + r2)

如果(r1 + r2) >= p ，則

(a+b) mod p = (r1 + r2) -p

否則

(a+b) mod p = (r1 + r2)

再和c進行模p和運算，得到

結果為 r1 + r2 + r3 的算術和除以p的余數。

對右側進行計算可以得到同樣的結果，得證。

模p相等

如果兩個數a、b滿足a mod p = b mod p，則稱他們模p相等，記做

a ≡ b (mod p)

可以證明，此時a、b滿足 a = kp + b，其中k是某個整數。

對于模p相等和模p乘法來說，有一個和四則運算中迥然不同的規則。在四則運算中，如果c是一個非0整數，則

ac = bc 可以得出 a =b

但是在模p運算中，這種關系不存在，例如：

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

但是

3 mod 9 = 3

6 mod 9 =6

定理（消去律）：如果gcd(c,p) = 1 ，則 ac ≡ bc mod p 可以推出 a ≡ (b mod p)

證明：

因為ac ≡ bc (mod p)

所以ac = bc + kp，也就是c(a-b) = kp

因為c和p沒有除1以外的公因子，因此上式要成立必須滿足下面兩個條件中的一個

1) c能整除k

2) a = b

如果2不成立，則c|kp

因為c和p沒有公因子，因此顯然c|k，所以k = ck'

因此c(a-b)=kp可以表示為c(a-b) =ck'p

因此a-b = k'p，得出a ≡ b (mod p)

如果a = b，則a ≡ b mod p 顯然成立

得證

以上是“在算法中mod指的是什么意思”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！