网络近期复习常见问题问题9

1、 素数 互为素数ab互素，如果它们之间没有共同的素数因子（。例如，815互素1 8 15 仅有的公因子（8 的因子1，2，4 8，而15 的因子1，3，5 15，可见 8 15 的公因子是 模运算 0 r q=a = qn + 注意：a mod n = 0n a 一个因子。Zn。因此余数集= 0, 1. , (n modnabmodn。显然，a b mod n 等价于 b a mod n。例如，734mod23mod23一定不能省略不写。(amodn) +(bmodn)modn=(a+ b)mod (amodn)(bmodn)modn=(ab)mod(amodn)(bmodn)modn=(ab

2、)mod例如：11mod815mod8=(11mod8)+(15mod8)mod8= 3+7mod8= 10mod8= (11+15) mod8=26mod8=(11mod8) (15mod8)mod8=3(11mod8) (15mod8)mod8=37mod8= 4mod8=(1115) mod8=4mod8=(11mod8) (15mod8)mod8=37mod8=21mod8=(1115) mod8=165mod8= =(171617417217) mod=(1716mod55)(174mod55)(172mod55)(17mod55)mod172 mod55= 289mod55= 17

3、4mod55=(172 mod55) (172 mod55)mod=1414mod55=196mod55=1716mod55=(174 mod55)(174mod55)(174mod55)(174mod55)mod= 3131 3131mod =923521mod=1679155+16mod = 1723mod5516311417mod=118048mod=214655+18mod = (abmodnacmodnbmodncmod例如，(53) mod815mod87mod(511) mod8= 55mod87mod3mod811mod不互素，则上述结论不能成立。例如，63 18 2 mod

4、867=422mod3 7 8费马定理 1 mod 1, 2,., (p amodp,2amodp,.,(p1) amod公式(8)中的(p1)个数恰好是某种次序的1,2,.p1)。例如，a5,p5mod8,10mod8,15mod8,20mod8,25mod8,30mod8,35mod也就是5,2,7,4,1,6,3。（要从一般意义上证明这一点也很容易。这只需要证明公式(8)中的任意两个数的模 p 都是不同的数即可，读者可自行证明。）也就是5,2,7,4,1,6,3。（要从一般意义上证明这一点也很容易。这只需要证明公式(8)中的任意两个数的模 p 都是不同的数即可，读者可自行证明。）将公式(

5、8)中的(p1)个数相乘应当等于公式(7)中的(p1)个数相乘： (a mod p) (2a mod p) .p 1)a mod p) = (p 1)!(amodp)(2amodp).(p1)amodp)modp=(p1)! mod(ap1)(p1)!modp=(p1)!modp= 1(p1)!mod ap1modp=1mod或ap1 1 mod函数 (p) = p (n) = (pq) = (p) (q) = (p 1) (q (n)= (pq 1) (p 1)(q 1)= pqp q+ 1= (p1)(q 1) = (p) 1,2, 3, 4, 5, 6,8, 9. 10, 12, 13,

6、 15,16, 17, 18, 19, 20,23, 24, 25,26, 27,29, 30, 31, 32, 36, 37, 38,39, 40, 41, 43, 45,46, 47,48, 50,51, 52, 53, 54, 57, 58,59, 60,61, 62, 64, 65, 67,69,71,72,7374,75,76定理 1 mod a3,n10, (n(104, 34811mod10a2,n11, (n(1110, 21010241mod11证明 如果 n 为任意整数，则如果 n 为任意整数，则的正整数个数。设这样的整数集合为 R：R= x1,x2, S =ax1 modn,ax2 modn,ax(n) modn1. aximodnaxj modnxixj因此，集合S中所有的数的乘积应当等于集合 R(ax1 modn)(ax2 modn)(ax(n) modn)=(x1)(x2)(ax1 modn)(ax2 modn)(ax(n) modn)modn=(x1)(x2)(x(n)mod(ax1)(ax2) (ax(n)modn= (x1) (x2)(x(n)mod(a(n)(x1) (x2