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

1、整除和因子整除和因子 素数互为素数ab互素，如果它们之间没有共同的素数因子（。例如，815互素，因为1 8 15 仅有的公因子（8 的因1，2，4 815 的因子1，3，5 158 15 的公因子是 1模运算 0 r q= a =qn+ an是一个正整数，则amodn a n的余数注意：a mod n = 0n a 一个因子。数集合0,1.n1)。这个整数集合又称为n的Zn。因此余数集合Zn = 0, 1. , (n 显然，a b mod n 等价于 b a mod n。例如，734mod23mod23一定不能省略不写。abmodnn能够整除(ab)n|(ab)模运算的一些性质(amodn)+

2、 (bmodn)modn=(a+b)mod (amod n)(bmodn)modn=(ab)mod(amod n)(bmodn)modn=(ab)mod例如：11mod 815mod 8 = (11 mod 8)+(15 mod8) mod 8=3+7mod 8 =10mod 8 =(11+ 15)mod 8 =26 mod8= (11 mod8) (15mod8)mod 8= 3 7mod 8= 4(11 mod8) (15mod8)mod 8= 3 7mod 8= 4mod 8=(11 15)mod 8= 4mod8=(11 mod 8) (15 mod8)mod 8 =3 7mod8 =

3、21 mod 8 =(1115)mod 8 =165 mod8 =1723mod551716+4+2+1mod=(171617417217)mod =(1716mod55)(174mod55) (172mod55) (17mod55)mod 172mod 55 =289mod 55 =174mod55=(172mod 55)(172mod55)mod =14 14 mod 55=196 mod55 =1716mod55=(174mod55)(174mod 55)(174mod55)(174mod55)mod =31 31 31 31 mod=923521mod = 16791 55 + 16

4、mod= 1723mod5516311417mod=118048mod =2146 55+ 18 mod = (abmodnacmodnbmodncmod例如，(5 3)mod 815 mod 87 mod(5 11) mod8= 55mod 87 mod 3mod 811mod不互素，则上述结论不能成立。例如，63 18 2 mod 86 7= 42 2 mod3 7 8费马定理an互素 1 mod 1, 2,., (p amod p,2amodp,., (p1)a mod公式(8)中的(p1)个数恰好是某种次序的1,2,.,p 1)。例如，a5,p5mod 8,10mod 8,15 mod

5、8,20 mod8,25 mod 8,30mod 8,35 mod 也就是5,2,7,4,1,6,3。（要从一般意义上证明这一点也很容易。这只需要证明公式(8)中的任意两个数的模 p 都是不同的数即可，读者可自行证明。）将公式(8)中的(p1)个数相乘应当等于公式也就是5,2,7,4,1,6,3。（要从一般意义上证明这一点也很容易。这只需要证明公式(8)中的任意两个数的模 p 都是不同的数即可，读者可自行证明。）将公式(8)中的(p1)个数相乘应当等于公式(7)中的(p1)个数相乘： (a mod p) (2a mod p) . ( (p 1)a mod p) = (p 1)!(amodp)(

6、2amodp).(p1)amod p)modp=(p1)!mod(ap1)(p1)!modp= (p 1)! mod p= 1 (p1)! mod利用公式(5)，因为(p1)!p互素，因此可以从等式两端消去(p1)!ap1modp=1 mod 或ap11mod函数函数(Eulerstotient function)记为(n)，(n)nn互素的正整数个数(p) = p 例如，p11时，(p101111互素的正整数个数10 (n) = (pq) = (p) (q) = (p 1) (q 7,1421,11,2233,等都去除。因此下面就按照这样的思路证明公式(10)(n)= (pq1)(p1) (

7、q1)=pqp q+1 =(p1) (q 1)=(p) 1, 2, 3, 4, 5, 6, 8, 9. 10, 12, 13, 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,7172,7374, 75, 76定理 1 mod a3, n10, (n(10) = 34811mod10a2,n11, (n(11)10, 21010241mod11证明 如果 n 为任意整数，则如果 n 为任意整数，则的正整数个数。设这样的整数集合为 R：R=x1,x2, S=ax1modn,ax2 modn,ax(n)modn S中不存在重复的整数。因为根据公式(5)aximodnaxjmodnxixj。因此，集合 S 中所有的数的乘积应当等于集合 R 中所有的数的乘积：(ax1modn)(ax2modn)(ax(n)modn)=(x1)(x2)(ax1modn)(ax2modn)(ax(n)modn)modn=(x1)(x2)(x(n)mod (ax1)(ax2) (ax(n)mod n=(x1)(x2) (x(n)mod