MOD运算_在线百科全书查询
MOD运算
在计算机程序设计中通常都有MOD运算，它的含义是 取得两个整数相除后结果的余数。
例如：7 mod 3 = 1
因为7 除以 3 商2余1。余数1即执行MOD运算后的结果
模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 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) ≡ 1 mod n
证明：
首先证明下面这个命题：
对于集合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 也一定于p互质，因此
任意x^i, ax^i mod n 必然是Zn的一个元素
2) 对于Zn中两个元素x^i 和x^j，如果x^i ≠ x^j
则ax^i mod n ≠ ax^i mod n，这个由a、p互质和消去律可以得出。
所以，很明显，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) mod n
右边等于x^1 × x^2 × ... × x^φ(n)）mod n
而x^1 × x^2 × ... × x^φ(n)）mod n和p互质
根据消去律，可以从等式两边约去，就得到：
a^φ(n) ≡ 1 mod n推论：对于互质的数a、n，满足a^(φ(n)+1) ≡ a mod n
费马定理
a是不能被质数p整除的正整数，则有a<SUP>p-1</SUP> ≡ 1 mod p
证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。
同样有推论：对于不能被质数p整除的正整数a，有a<SUP>p</SUP> ≡ a mod p
</PRE></PRE>
进一步应用
有关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 ρ)
