模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-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ī)律，如：

規(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 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 + k2) p + (r1 + r2)
 如果(r1 + r2) >= p ，則
    (a+b) mod p = (r1 + r2) -p
 否則
    (a+b) mod 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
 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 顯然成立
 得證

歐拉函數(shù)

歐拉函數(shù)是數(shù)論中很重要的一個函數(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)q} 共計p-1個
        3) {0}
        很顯然，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 = Zn
        1) 由于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，這個由a、p互質(zhì)和消去律可以得出。
        所以，很明顯，S=Zn
        
        既然這樣，那么
        （ax1 × ax2×...×axφ(n)）mod n
         = （ax1 mod n × ax2mod 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ù)，則有ap-1 ≡ 1 mod p
證明這個定理非常簡單，由于φ(p) = p-1，代入歐拉定理即可證明。
同樣有推論：對于不能被質(zhì)數(shù)p整除的正整數(shù)a，有ap ≡ a mod p