计算机系中有关mod的常识.doc

在计算机程序设计中通常都有MOD运算，它的含义是 取得两个整数相除后结果的余数。例如：7 mod 3 = 1 因为7 除以 3 商2余1。余数1即执行MOD运算后的结果模p运算给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r 其中k、r是整数，且 0 r = 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是某个整数。对于模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 ，则 ac bc mod p 可以推出 a b mod p证明：因为ac bc mod p所以ac = bc + kp，也就是c(a-b) = kp因为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)被定义为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)欧拉定理对于互质的整数a和n，有a(n) 1 mod n 证明：首先证明下面这个命题：对于集合Zn=x1,x2,.,x(n)，考虑集合S = ax1 mod n,ax2mod n,.,ax(n) mod n则S = Zn1) 由于a,n互质，xi 也与n互质，则axi 也一定于p互质，因此任意xi, axi mod n 必然是Zn的一个元素2) 对于Zn中两个元素xi 和xj，如果xi xj则axi mod n axi mod n，这个由a、p互质和消去律可以得出。所以，很明显，S=Zn既然这样，那么（ax1 ax2.ax(n)）mod n= （ax1 mod n ax2 mod n . ax(n mod n）mod n= （x1 x2 . x(n）mod n考虑上面等式左边和右边左边等于(a(n) （x1 x2 . x(n)）mod n) mod n右边等于x1 x2 . x(n)）mod n而x1 x2 . x(n)）mod n和p互质根据消去律，可以从等式两边约去，就得到：a(n) 1 mod n推论：对于互质的数a、n，满足a(n)+1) a mod n费马定理 a是不能被质数p整除