设为首页收藏本站

防未病交好友

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 109|回复: 1

MOD函数求余数的计算方法 / MOD运算

[复制链接]
发表于 2014-10-11 23:08:41 | 显示全部楼层 |阅读模式
1 模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的余数。
对右侧进行计算可以得到同样的结果,得证。

2 模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>  以下可以不要看

3 欧拉函数
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数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>

4 欧拉定理
对于互质的整数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

5 费马定理
a是不能被质数p整除的正整数,则有a<SUP>p-1</SUP> ≡ 1 mod p
证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
同样有推论:对于不能被质数p整除的正整数a,有a<SUP>p</SUP> ≡ a mod p
</PRE></PRE>


回复

使用道具 举报

 楼主| 发表于 2014-10-11 23:28:31 | 显示全部楼层
(460004509069055 MOD 1000)MOD 16=?

虽然前面的数字很吓人...,但是只要过了千以上余数都是千以内的数,所以460004509069055 MOD1000=55

然后 易算得,55mod16=7

(460004509069055 MOD 1000)MOD 16=7
回复 支持 反对

使用道具 举报

QQ|申请友链|Archiver|手机版|小黑屋|D1V1网社区 ( 沪ICP备05028199号  

GMT+8, 2018-12-18 18:56 , Processed in 1.312466 second(s), 36 queries .

Powered by Discuz! X3.2 Designed by 999test.cn

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表