《计算机系中有关mod的常识》由会员分享，可在线阅读，更多相关《计算机系中有关mod的常识(5页珍藏版)》请在人人文库网上搜索。
1、在计算机程序设计中通常都有MOD!算，它的含义是取得两个整数相除后结果 的余数。例如： 7 mod 3 = 1因为7除以3商2余1。余数1即执行MOD!算后的结果模p运算给定一个正整数p,任意一个整数n, 定存在等式n = kp + r 其中 k、r 是整数，且 0 ? r =p，贝U(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 =。
2、 b mod p可以证明，此时 a、b 满足 a = kp + b ，其中 k 是某个整数。对于模p相等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则ac = bc 可以得出 a =b但是在模 p 运算中，这种关系不存在，例如：(3 x 3) mod 9 = 0(6 x 3) mod 9 = 0但是3 mod 9 = 36 mod 9 =6定理(消去律)：如果 gcd(c,p) = 1 ，贝U ac = be mod p 可以推出a = b mod p证明：因为 ac = bc mod p所以 ac = bc + kp ，也就是 c(a-b) = kp。
3、因为c和p没有除1以外的公因子，因此上式要成立必须满足下面两个条件 中的一个1) c 能整除 k2) a = b如果 2 不成立，则 c|kp因为c和p没有公因子，因此显然c|k，所以k = ck因此 c(a-b)kp 可以表示为 c(a-b) =ckp因此 a-b = kp ，得出 a = b mod p如果a = b，则a = b mod p 显然成立得证欧拉函数欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n,小于n且和n互质的正整数的个数，记做： (n)，其中 被定义为1,但是并没 有任何实质的意义。定义小于n且和n互质的数构成的集合为Zn,称呼这个集合为n的完全余 数。
4、集合。显然，对于素数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)欧拉定理对于互质的整数a和n，有aA (n) =。
5、 1 mod n证明：首先证明下面这个命题：对于集合Zn=xA1,xA2,.,xA (n),考虑集合S = axA1 mod n,axA2mod n，,axA (n) mod n贝U S = Zn1) 由于a,n互质，xAi也与n互质，则axAi也一定于p互质，因此任意xAi, axAi mod n 必然是Zn的一个元素2) 对于Zn中两个元素xAi和xAj，如果xAi工xAj贝U axAi mod n 工axAi mod n，这个由a、p互质和消去律可以得出。 所以，很明显， S=Zn既然这样，那么(axA1 x axA2 x . x axA (n) ) mod n=(axA1 mod nx。
6、 axA2mod nx . x axA(门 mod n ) mod n=(xA1 x xA2x .x xA (n)mod n考虑上面等式左边和右边左边等于 (aA(n) x (xA1 x xA2 x . x xA (n) )mod n) mod n 右边等于 xA1 x xA2 x . x xA (n) )mod n而 xA1 x xA2 x . x xA (n) ) mod n 和 p 互质 根据消去律，可以从等式两边约去，就得到：aA (n) = 1 modn 推论：对于互质的数 a、n，满足 aA( (n)+1) = a modn费马定理a 是不能被质数p整除的正整数，则有ap-1三1 mod p证明这个定理非常简单，由于 (p) = p-1 ，代入欧拉定理即可证明。同样有推论：对于不能被质数p整除的正整数a,有apv/SUPw a modp。