計算機系中有關(guān)mod的常識

1、在計算機程序設(shè)計中通常都有MOD運算，它的含義是 取得兩個整數(shù)相除后結(jié)果的余數(shù)。例如：7 mod 3 = 1 因為7 除以 3 商2余1。余數(shù)1即執(zhí)行MOD運算后的結(jié)果 模p運算給定一個正整數(shù)p，任意一個整數(shù)n，一定存在等式 n = kp + r 其中k、r是整數(shù)，且 0 r < p，稱呼k為n除以p的商，r為n除以p的余數(shù)。對于正整數(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-

2、b) mod p ，其結(jié)果是a-b算術(shù)差除以p的余數(shù)。 模p乘法：(a × b) mod p，其結(jié)果是 a × b算術(shù)乘法除以p的余數(shù)。 可以發(fā)現(xiàn),模p運算和普通的四則運算有很多類似的規(guī)律，如： 簡單的證明其中第一個公式： (a+b) mod p + c) mod p = (a + (b+c) mod p) mod p假設(shè)a = k1*p + r1b = k2*p + r2c = k3*p + r3a+b = (k1 + k2) p + (r1 + r2)如果(r1 + r2) >= p ，則(a+b) mod p = (r1 + r2) -p否則(a+b) mod

3、p = (r1 + r2)再和c進行模p和運算，得到結(jié)果為 r1 r2 + r3 的算術(shù)和除以p的余數(shù)。對右側(cè)進行計算可以得到同樣的結(jié)果，得證。 模p相等如果兩個數(shù)a、b滿足a mod p = b mod p，則稱他們模p相等，記做 a b mod p可以證明，此時a、b滿足 a = kp + b，其中k是某個整數(shù)。對于模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

4、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能整除k2) 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 顯然成立得證歐拉函數(shù)歐拉函數(shù)是數(shù)論中很重要

5、的一個函數(shù)，歐拉函數(shù)是指：對于一個正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)的個數(shù)，記做：(n)，其中(1)被定義為1，但是并沒有任何實質(zhì)的意義。定義小于n且和n互質(zhì)的數(shù)構(gòu)成的集合為Zn，稱呼這個集合為n的完全余數(shù)集合。顯然，對于素數(shù)p，(p)= p -1.對于兩個素數(shù)p、q，他們的乘積n = pq 滿足(n) =(p-1)(q-1)證明：對于質(zhì)數(shù)p,q，滿足(n) =(p-1)(q-1)考慮n的完全余數(shù)集Zn = 1,2,.,pq -1而不和n互質(zhì)的集合由下面三個集合的并構(gòu)成：1) 能夠被p整除的集合p,2p,3p,.,(q-1)p 共計q-1個2) 能夠被q整除的集合q,2q,3q,.,(p-1)

6、q 共計p-1個3) 很顯然，1、2集合中沒有共同的元素，因此Zn中元素個數(shù) pq - (p-1 + q- 1 + 1) = (p-1)(q-1) 歐拉定理對于互質(zhì)的整數(shù)a和n，有a(n) 1 mod n 證明：首先證明下面這個命題：對于集合Zn=x1,x2,.,x(n)，考慮集合S = ax1 mod n,ax2mod n,.,ax(n) mod n則S = Zn1) 由于a,n互質(zhì)，xi 也與n互質(zhì)，則axi 也一定于p互質(zhì)，因此任意xi, axi mod n 必然是Zn的一個元素2) 對于Zn中兩個元素xi 和xj，如果xi xj則axi mod n axi mod n，這個由

7、a、p互質(zhì)和消去律可以得出。所以，很明顯，S=Zn既然這樣，那么（ax1 × ax2×.×ax(n)）mod n= （ax1 mod n × ax2 mod n × . × ax(n mod n）mod n= （x1 × x2 × . × x(n）mod n考慮上面等式左邊和右邊左邊等于(a(n) × （x1 × x2 × . × x(n)）mod n) mod n右邊等于x1 × x2 × . × x(n)）mod n而x1 × x2 × . × x(n)）mod n和p互質(zhì)根據(jù)消去律，可以從等式兩邊約去，就得到：a(n) 1 mod n推論：對于互質(zhì)的數(shù)a、n，滿足a(n)+1) a mod n 費馬定理       a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有a<S