1.模p運(yùn)算編輯

給定一個(gè)正整數(shù)p，任意一個(gè)整數(shù)n，一定存在等式

n = kp + r其中k、r是整數(shù)，且 0 ≤ r < p，稱呼k為n除以p的商，r為n除以p的余數(shù)。[1]

對(duì)于正整數(shù)p和整數(shù)a,b，定義如下運(yùn)算：

取模運(yùn)算：a mod p 表示a除以p的余數(shù)。

模p加法：(a + b) mod p ，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說(shuō)，(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運(yùn)算和普通的四則運(yùn)算有很多類似的規(guī)律，如：[1]

結(jié)合律 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p((ab) mod p * c)mod p = (a * (bc) 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
簡(jiǎn)單的證明其中第一個(gè)公式：

((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進(jìn)行模p和運(yùn)算，得到

結(jié)果為 r1 + r2 + r3 的算術(shù)和除以p的余數(shù)。

對(duì)右側(cè)進(jìn)行計(jì)算可以得到同樣的結(jié)果，得證。

2.模p相等編輯

如果兩個(gè)數(shù)a、b滿足a mod p = b mod p，則稱他們模p相等，記做

a ≡ b (mod p)

可以證明，此時(shí)a、b滿足 a = kp + b，其中k是某個(gè)整數(shù)。[2]

對(duì)于模p相等和模p乘法來(lái)說(shuō)，有一個(gè)和四則運(yùn)算中迥然不同的規(guī)則。在四則運(yùn)算中，如果c是一個(gè)非0整數(shù)，則

ac = bc 可以得出 a =b

但是在模p運(yùn)算中，這種關(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)

證明：

因?yàn)閍c ≡ bc (mod p)

所以ac = bc + kp，也就是c(a-b) = kp

因?yàn)閏和p沒(méi)有除1以外的公因子，因此上式要成立必須滿足下面兩個(gè)條件中的一個(gè)

c能整除k

a = b

如果2不成立，則c|kp

因?yàn)閏和p沒(méi)有公因子，因此顯然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 顯然成立

得證

3.歐拉函數(shù)編輯

歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù)，歐拉函數(shù)是指：對(duì)于一個(gè)正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)的個(gè)數(shù)，記做：φ(n)，其中φ(1)被定義為1，但是并沒(méi)有任何實(shí)質(zhì)的意義。

定義小于n且和n互質(zhì)的數(shù)構(gòu)成的集合為Zn，稱呼這個(gè)集合為n的完全余數(shù)集合。

顯然，對(duì)于素?cái)?shù)p，φ§= p -1.對(duì)于兩個(gè)素?cái)?shù)p、q，他們的乘積n = pq 滿足φ(n) =(p-1)(q-1)

證明：對(duì)于質(zhì)數(shù)p,q，滿足φ(n) =(p-1)(q-1)

考慮n的完全余數(shù)集Zn = { 1,2,…,pq -1}

而不和n互質(zhì)的集合由下面三個(gè)集合的并構(gòu)成：

能夠被p整除的集合{p,2p,3p,…,(q-1)p} 共計(jì)q-1個(gè)

能夠被q整除的集合{q,2q,3q,…,(p-1)q} 共計(jì)p-1個(gè)

3)很顯然，1、2集合中沒(méi)有共同的元素，因此Zn中元素個(gè)數(shù) = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

4.歐拉定理編輯

對(duì)于互質(zhì)的整數(shù)a和n，有a^φ(n) mod n = 1[3]

證明：

首先證明下面這個(gè)命題：

對(duì)于集合Zn={x^1,x2,…,x^φ(n)}，考慮集合

S = {ax^1 mod n,ax^2mod n,…,ax^φ(n) mod n}

則S = Zn

由于a,n互質(zhì)，x^i 也與n互質(zhì)，則ax^i 也一定于n互質(zhì)，因此

任意x^i, ax^i mod n 必然是Zn的一個(gè)元素

對(duì)于Zn中兩個(gè)元素x^i 和x^j，如果xi ≠ x^j

則ax^i mod n ≠ ax^j mod n，這個(gè)由a、n互質(zhì)和消去律可以得出。

所以，很明顯，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互質(zhì)

根據(jù)消去律，可以從等式兩邊約去，就得到：

a^φ(n) mod n = 1推論：對(duì)于互質(zhì)的數(shù)a、n，滿足a^(φ(n)+1) mod n = a

5.費(fèi)馬定理編輯

a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有ap-1≡ 1 mod p

證明這個(gè)定理非常簡(jiǎn)單，由于φ§ = p-1，代入歐拉定理即可證明。

同樣有推論：對(duì)于不能被質(zhì)數(shù)p整除的正整數(shù)a，有ap≡ a mod p[3]

6進(jìn)一步應(yīng)用編輯
有關(guān)mod的一道證明題

不用算數(shù)基本定理，證明a,b=|ab|

證明：在數(shù)論中，證明等式有一種常用的方式，就是證明兩邊互為整除，此題也不例外，只是要先移

項(xiàng)。

|ab|/(a,b)=|a|(|b|/(a,b))=>a|(|ab|/(a,b))

同理有：b|(|ab|/(a,b))

于是，|ab|/(a,b)是a,b的公倍數(shù)，即[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))互質(zhì)

∴（|ab|/(a,b)2）|([a,b]/(a,b))

∴(|ab|/(a,b))|[a,b]

綜上所述，a,b=|ab|.

設(shè)m,m′都是正整數(shù)，d=(m,m?)，b≡b?(mod d).證明系統(tǒng)

x≡b(mod m) ①

x≡b?(mod m?) ②

的任意兩個(gè)解都是模ρ同余，其中ρ=lcm{m，m?}。

證明：設(shè)y是滿足題設(shè)的另外一個(gè)解，則有：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?/d2)

設(shè)y=x+kmm?/d2

分別代入③，④中，并結(jié)合①，②，則有

x+kmm?/d2≡b≡x(mod m) =>kmm?/d2≡0(mod m)

x+kmm?/d2≡b?≡x(mod m?) =>kmm?/d2≡0(mod m?)

即：m|kmm?/d2=>km?/d2為整數(shù)=>(m?/d)(k/d)為整數(shù)

m?|kmm?/d2=>km/d2為整數(shù)=>(m/d)(k/d)為整數(shù)

顯然，(m?/d,d)=1與(m/d,d)=1至少有一個(gè)成立，否則(m,m?)=d2,矛盾.

∴k=ld,y=x+lmm?/d,

而mm?/d=|mm?|/(m,m?)=[m,m?]=ρ=lcm{m，m?}

∴y=x+lρ=>y≡x(mod ρ)

總結(jié)

以上是生活随笔為你收集整理的MOD的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。