模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*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
假設
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是某個整數。
</PRE>對於模p相等和模p乘法來說，有一個和四則運算中迥然不同的規則。在四則運算中，如果c是一個非0整數，則
ac = bc 可以得出 a =b
</PRE>但是在模p運算中，這種關係不存在，例如：
(3 x 3) mod 9 = 0
(6 x 3) mod 9 = 0
但是
3 mod 9 = 3
6 mod 9 =6
</PRE> 定理（消去律）：如果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 顯然成立
得證
</PRE>
歐拉函式
歐拉函式是數論中很重要的一個函式，歐拉函式是指：對於一個正整數n，小於n且和n互質的正整數的個數，記做：φ(n)，其中φ(1)被定義為1，但是並沒有任何實質的意義。
定義小於n且和n互質的數構成的集合為Zn，稱呼這個集合為n的完全餘數集合。
顯然，對於素數p，φ(p)= p -1.對於兩個素數p、q，他們的乘積n = pq 滿足φ(n) =(p-1)(q-1)
證明：對於質數p,q，滿足φ(n) =(p-1)(q-1)
考慮n的完全餘數集Zn = { 1,2,....,pq -1}
而不和n互質的集合由下面三個集合的並構成：
1) 能夠被p整除的集合{p,2p,3p,....,(q-1)p} 總計q-1個
2) 能夠被q整除的集合{q,2q,3q,....,(p-1)q} 總計p-1個
3)很顯然，1、2集合中沒有共同的元素，因此Zn中元素個數 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)
</PRE>
歐拉定理
對於互質的整數a和n，有a^φ(n) mod n = 1
證明：
首先證明下面這個命題：
對於集合Zn={x^1,x^2,...,x^φ(n)}，考慮集合
S = {ax^1 mod n,ax^2mod n,...,ax^φ(n) mod n}
則S = Zn
1) 由於a,n互質，x^i 也與n互質，則ax^i 也一定於n互質，因此
任意x^i, ax^i mod n 必然是Zn的一個元素
2) 對於Zn中兩個元素x^i 和x^j，如果x^i ≠ x^j
則ax^i mod n ≠ ax^j mod n，這個由a、n互質和消去律可以得出。
所以，很明顯，S=Zn
既然這樣，那么
（ax^1 × ax^2×...×ax^φ(n)）mod n
= （ax^1 mod n × ax^2 mod n × ... × ax^φ(n) mod n）mod n
= （x^1 × x^2 × ... × x^φ(n）mod n
考慮上面等式左邊和右邊
左邊等於( (a^φ(n) × （x^1 × x^2 × ... × x^φ(n)）)mod n
右邊等於(x^1 × x^2 × ... × x^φ(n)）mod n
而(x^1 × x^2 × ... × x^φ(n)）mod n和p互質
根據消去律，可以從等式兩邊約去，就得到：
a^φ(n) mod n = 1 推論：對於互質的數a、n，滿足a^(φ(n)+1) mod n = a
費馬定理
a是不能被質數p整除的正整數，則有a≡ 1 mod p
證明這個定理非常簡單，由於φ(p) = p-1，代入歐拉定理即可證明。
同樣有推論：對於不能被質數p整除的正整數a，有a≡ a mod p
進一步套用
有關mod的一道證明題
不用算數基本定理，證明[a,b](a,b)=|ab|
證明：在數論中，證明等式有一種常用的方式，就是證明兩邊互為整除，此題也不例外，只是要先移
項。
|ab|/(a,b)=|a|(|b|/(a,b))=>
a|(|ab|/(a,b))
同理有：b|(|ab|/(a,b))
於是，|ab|/(a,b)是a,b的公倍數，即[a,b]|(|ab|/(a,b))
∵|a||[a,b]
∴(|a|/(a,b))|([a,b]/(a,b))
同理：(|b|/(a,b))|([a,b]/(a,b))
又∵(|a|/(a,b))與(|b|/(a,b))互質
∴（|ab|/(a,b)²）|([a,b]/(a,b))
∴(|ab|/(a,b))|[a,b]
綜上所述，[a,b](a,b)=|ab|.
設m,m′都是正整數，d=(m,mˆ)，b≡bˆ(mod d).證明系統
x≡b(mod m) ①
x≡bˆ(mod mˆ) ②
的任意兩個解都是模ρ同餘，其中ρ=lcm{m，mˆ}.
證明:設y是滿足題設的另外一個解，則有：y≡b(mod m) ③
y≡bˆ(mod mˆ) ④
∵x≡b(mod m)，∴x≡b(mod m/d), y≡b(mod m/d)
兩式相減，則有x-y≡b-b≡0≡(mod m/d)
∴x≡y(mod m/d)
同理：x≡y(mod mˆ/d)
∵(m/d,mˆ/d)=1
∴x≡y(mod mmˆ/d²)
設y=x+kmmˆ/d²
分別代入③，④中，並結合①，②，則有
x+kmmˆ/d²≡b≡x(mod m) =>kmmˆ/d²≡0(mod m)
x+kmmˆ/d²≡bˆ≡x(mod mˆ) =>kmmˆ/d²≡0(mod mˆ)
即：m|kmmˆ/d²=>kmˆ/d²為整數=>(mˆ/d)(k/d)為整數
mˆ|kmmˆ/d²=>km/d²為整數=>(m/d)(k/d)為整數
顯然，(mˆ/d,d)=1與(m/d,d)=1至少有一個成立，否則(m,mˆ)=d²,矛盾.
∴k=ld,y=x+lmmˆ/d,
而mmˆ/d=|mmˆ|/(m,mˆ)=[m,mˆ]=ρ=lcm{m，mˆ}
∴y=x+lρ=>
y≡x(mod ρ)
○
