mod運算，即求余運算跃须，是在整數(shù)運算中求一個整數(shù) x 除以另一個整數(shù)y的余數(shù)的運算冒萄，且不考慮運算的商池摧。在計算機(jī)程序設(shè)計中都有MOD運算，其格式為： mod(nExp1,nExp2)红伦，即是兩個數(shù)值表達(dá)式作除法運算后的余數(shù)英古。
模p運算
給定一個正整數(shù)p，任意一個整數(shù)n昙读，一定存在等式
n = kp + r其中k召调、r是整數(shù)，且 0 ≤ r < p蛮浑，稱呼k為n除以p的商唠叛，r為n除以p的余數(shù)
p是除數(shù) k 相當(dāng)于商 n相當(dāng)于被除數(shù) r 相當(dāng)于余數(shù)
余數(shù)一定是比除數(shù)小的 ,即r<p
對于正整數(shù)p和整數(shù)a,b，定義如下運算：
- 取模運算：a mod p 表示a除以p的余數(shù)沮稚。
- 模p加法：(a + b) mod p 艺沼，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說蕴掏，(a+b) = kp +r障般，則 (a+b) mod p = r调鲸。
- 模p減法：(a-b) mod p ，其結(jié)果是a-b算術(shù)差除以p的余數(shù)剩拢。
- 模p乘法：(a × b) mod p线得，其結(jié)果是 a × b算術(shù)乘法除以p的余數(shù)。
運算規(guī)律
| 結(jié)合律 | ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a×b) mod p×c)mod p = (a× (b×c) mod p) mod p |
| 交換律 | (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p |
| 分配律 | ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p (a×b) mod c=(a mod c * b mod c) mod c (a+b) mod c=(a mod c+ b mod c) mod c (a-b) mod c=(a mod c- b mod c) mod c |
證明
((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p
假設(shè)
a = k1p + r1
b = k2p + r2
c = k3p + r3
a+b = (k1 + k2) p + (r1 + r2)
如果(r1 + r2) >= p 徐伐，則
(a+b) mod p = (r1 + r2) -p
否則
(a+b) mod p = (r1 + r2)
如果(r1 + r2) >= p,將 (a+b) mod p = (r1 + r2) -p 帶入
(1) 那么 (a+b) mod p + c = (r1 + r2) -p + k3p + r3 = r1+r2+r3+(k3-1)p
如果(r1+r2)<p ,將(a+b) mod p = (r1 + r2) 帶入
(2) 那么(a+b) mod p + c = r1+r2+ k3p + r3 = r1+r2+r3 +k3p
綜合(1)(2)兩處, ((a+b) mod p + c) mod p的結(jié)果是 r1+r2+r3的算數(shù)和除以p的余數(shù)
同理右邊一樣的算法可證.
證明
((a\*b) mod p\* c)mod p = (a\* (b\*c) mod p) mod p
假設(shè)
a = k1*p + r1
b = k2*p + r2
c = k3*p + r3
a*b = ( k1*p + r1)(k2*p + r2) = k1k2p2+(k1r2+k2r1)p+r1r2=(k1k2p+k1r2+k2r1)p+r1*r2;
如果r1*r2 >=p ,則
(ab) mod p = r1*r2 -m*p (m>0 ,屬于正整數(shù))
否則r1*r2 < p,則
(a*b) mod p = r1*r2
如果r1*r2 >=p ,那么將(a*b) mod p 帶入
(1) 那么 (ab) mod p * c = ( r1*r2 -mp)(k3*p + r3) =( -mk3p+r1r2k3-mk3)p + r1r2r3 ( (m>0 ,屬于正整數(shù)))
如果r1r2<p 那么將(a*b) mod p帶入
(2)那么 (ab) mod p * c = r1r2(k3p+r3)=k3r1r2p+r1r2r3
綜合(1)(2)兩處 ((a*b) mod p* c)mod p 的結(jié)果是 r1r2r3的算術(shù)乘積除以p的余數(shù)
同理右邊一樣的算法
這里交換律一看就能看出來不證明了
證明
((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
假設(shè)
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)
如果(r1 + r2) >= p,將 (a+b) mod p = (r1 + r2) -p 帶入
(1) 那么(a +b)mod p × c =( r1+r2-p)×( k3×p + r3) =( -k3×p+r1k3+r2k3-k3)×p + (r1+r2)×r3
如果(r1+r2)<p ,將(a+b) mod p = (r1 + r2) 帶入
(2) 那么(a+b) mod p × c =( r1+r2) ×( k3*p + r3) = (r1k3+r2k3) p +(r1+r2)×r3
綜合(1)(2)兩處, ((a+b) mod p × c) mod p的結(jié)果是(r1+r2)×r3的算數(shù)值 除以p的余數(shù)
證明右邊
(a × c) = (k1p+r1)(k3p+r3) =( k1k3p+k1r3+r1k3) p + r1r3;
如果r1r3>=p ,則
(a × c) mod p = r1r3-mp (m>0的正整數(shù))
如果 r1r3<p ,則
(a × c) mod p = r1r3
同理 (b × c) mod p
如果r2r3>=p ,則 (b × c) mod p = r2r3-np (n>0的正整數(shù))
如果r2r3<p ,則 (b × c) mod p = r2r3
排列組合 四種情況
第一種情況 r1r3>=p && r2r3>=p
那么(a × c) mod p + (b × c) mod p = r1r3-mp + r2r3-np = (-m-n)p+ (r1+r2)r3
第二種情況 r1r3<p && r2r3>=p
那么(a × c) mod p + (b × c) mod p = r1r3 + r2r3-np = (-n)p+ (r1+r2)r3
第一種情況 r1r3>=p && r2r3<p
那么(a × c) mod p + (b × c) mod p = r1r3-mp + r2r3 = (-m)p+ (r1+r2)r3
第二種情況 r1r3<p && r2r3<p
那么(a × c) mod p + (b × c) mod p = r1r3 + r2r3 = (r1+r2)r3
以上四種情況的結(jié)果都是(r1+r2)×r3的算數(shù)值 除以p的余數(shù) 和左邊的結(jié)果相等
證明
(a×b) mod c=(a mod c * b mod c) mod c
假設(shè)
a = k1*p + r1
b = k2*p + r2
c= p
(a × b) mod c 的結(jié)果有兩種情況.(在上面證明過)
如果r1r2>=p ,那么(a × b) mod c = r1r2-mc (m>0)
如果r1r2< p ,那么 (a × b) mod c = r1r2
以上兩種的結(jié)果都是r1r2乘積 除以c (也是p)的余數(shù).
證明右邊
amodc = amodp = r1;
bmodc =bmodp = r2;
a mod c * b mod c = r1*r2;
因此和左邊是相等的.
(a+b) mod c=(a mod c+ b mod c) mod c 和(a-b) mod c=(a mod c- b mod c) mod c的證明和(a×b) mod c=(a mod c * b mod c) mod c證明一樣,略
模p相等
如果兩個數(shù)a、b滿足a mod p = b mod p办素，則稱他們模p相等角雷，記做
a ≡ b (mod p)
可以證明，此時a性穿、b滿足 a = kp + b勺三，其中k是某個整數(shù)。
證明
假設(shè)
a = k1p+r1;
b = k2p+ r2;
如果 a mod p = b mod p ,那么r1 = r2;
所以 a= k1p+ r1= k1p+b-k2p = (k1-k2)p + b;
因此 a = kp+b;
對于模p相等和模p乘法來說需曾，有一個和四則運算中迥然不同的規(guī)則.
在四則運算如果c是一個非0整數(shù)吗坚，則ac = bc 可以得出 a =b
但是在模p運算中，這種關(guān)系不存在. 舉例如下
(3 x 3) mod 9 = 0
(6 x 3) mod 9 = 0
但是
3 mod 9 = 3
6 mod 9 =6
那么如何才能消除呢?執(zhí)行消除需要滿足定理條件
定理（消去律）：如果gcd(c,p) = 1 呆万，則 ac ≡ bc mod p 可以推出 a ≡ (b mod p)
gcd 函數(shù)解釋
GCD函數(shù)是 返回兩個或多個整數(shù)的最大公約數(shù)
最大公約數(shù)是能分別將各個參數(shù)除盡的最大整數(shù)商源。
例如 2 和4的最大公約數(shù)是 2, 2和3的最大公約數(shù)是1
gcd(c,p)=1 ,表示沒有公約因子
證明
因為ac ≡ bc (mod p)
所以ac = bc + kp，也就是c(a-b) = kp (模等可以這樣轉(zhuǎn)換)
因為c和p沒有除1以外的公因子谋减，因此上式要成立必須滿足下面兩個條件中的一個
1) c能整除k
2) a = b
第一種情況 ,a-b = kp/c; 因為c和p沒有除1以外的公因子, 所以 a-b = k1p; k1 = k/c .所以 a = b+k1p ; 所以 a ≡ b (mod p)
第二種情況 a = b牡彻，則a ≡ b mod p 顯然成立
