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 顯然成立

得證