1、1第一章 整数的可除性1证明：因为 2|n 所以 n=2k , k Z5|n 所以 5|2k ， 又（5，2）=1，所以 5|k 即 k=5 k1 ，k 1 Z7|n 所以 7|2*5 k1 ,又（7，10）=1，所以 7| k1 即 k1=7 k2，k 2 Z所以 n=2*5*7 k2 即 n=70 k2, k2 Z因此 70|n2证明：因为 a3-a=(a-1)a(a+1)当 a=3k，k Z 3|a 则 3|a3-a当 a=3k-1，k Z 3|a+1 则 3|a3-a当 a=3k+1，k Z 3|a-1 则 3|a3-a所以 a3-a 能被 3 整除。3证明：任意奇整数可表示为 2 k
2、0+1， k0 Z（2 k 0+1） 24 k 02+4 k0+1=4 k0 (k0+1)+1由于 k0 与 k0+1 为两连续整数，必有一个为偶数，所以 k0 (k0+1)=2k所以（2 k 0+1） 2=8k+1 得证。4证明：设三个连续整数为 a-1,a,a+1 则(a-1)a(a+1)= a 3-a由第二题结论 3|（a 3-a） 即 3|(a-1)a(a+1)又三个连续整数中必有至少一个为偶数，则 2|(a-1)a(a+1)又（3，2）=1 所以 6|(a-1)a(a+1) 得证。5证明：构造下列 k 个连续正整数列：(k+1)！+2, (k+1)！+3, (k+1)！+4, (k+
3、1)！+(k+1), k Z对数列中任一数 (k+1)！+i=i(k+1)k(i+1)(i-1)2*1+1, i=2,3,4,(k+1)所以 i|(k+1)！+i 即(k+1)！+i 为合数所以此 k 个连续正整数都是合数。6证明：因为 1911/214 ,小于 14 的素数有 2，3，5，7，11，13经验算都不能整除 191 所以 191 为素数。因为 5471/224 ,小于 24 的素数有 2，3，5，7，11，13，17，19，23经验算都不能整除 547 所以 547 为素数。由 737=11*67 ,747=3*249 知 737 与 747 都为合数。8解：存在。eg：a=6,
4、b=2,c=910证明：p 1 p2 p3|n， 则 n= p1 p2 p3k，k N+又 p1 p 2 p 3，所以 n= p1 p2 p3kp 13 即 p13n 1/3p1为素数 则 p12，又 p1 p 2 p 3，所以 n= p1 p2 p3k2 p 2 p32p 22 即 p2(n/2) 1/2 得证。11解：小于等于 5001/2的所有素数为 2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：12证明：反证法假设 3k+1 没有相同形式的素因数，则它一定只能表示成若干形如 3k-1 的素数相乘。 (3 k1+1)(3 k2+1)=( 3 k1+1) k2
5、+ k1*3+1 显然若干个 3k+1 的素数相乘，得到的还是 3k+1 的形式，不能得出 3k-1 的数，因此假设不成立，结论得证。同理可证其他。13证明：反证法假设形如 4k+3 的素数只有有限个，记为 p1, p2, pn因为 4k+3=4k-1=4k-1 构造 N=4*p1*p2*pn-13 *p1*p2*pn所以 Np i (i=1,2,n) N 为 4k-1 形式的素数，即为 4k+3 的形式，所以假设不成立。原结论正确，形如 4k+3 的素数有无穷多个。28 （1）解：85=1*55+3055=1*30+25230=1*25+525=5*5所以(55,85)=5（2）解：282=
6、1*202+80202=2*80+4280=1*42+3842=1*38+438=9*4+24=2*2所以（202,282）=229 （1）解：2t+1=1*(2t-1)+22t-1=(t-1)*2+12=2*1所以（2t+1,2t-1）=1（2）解：2(n+1)=1*2n+22n=n*2所以（2n,2(n+1)）=232 （1）解：1=3-1*2=3-1*(38-12*3)=-38+13*(41-1*38)=13*41-14*(161-3*41)=-14*161+55*(363-2*161)=55*363+(-124)*(1613-4*363)=(-124)*1613+551*(3589-2
7、*1613)=551*3589+(-1226)*1613所以 s=-1226 t=551（2）解：1=4-1*3=4-1*(115-28*4)=-115+29*(119-1*115)=29*119+(-30)*(353-2*119)=-30*353+89*(472-1*353)=89*472+(-119)*(825-1*472)=(-119)*825+208*(2947-3*825)=208*2947+(-743)*(3772-1*2947)=951*2947+(-743)*3772所以 s=951 t=-74336证明：因为（a，4）=2 所以 a=2*(2m+1) m Z所以 a+b=4m
8、+2+4n+2=4(m+n)+4=4(m+n+1)即 4|a+b所以（a+b,4）=437证明：反证法假设 n 为素数，则 n| a2- b2=(a+b)(a-b)由 1.4 定理 2 知 n|a+b 或 n|a-b,与已知条件矛盾所以假设不成立，原结论正确，n 为合数。40证明：（1）假设是 21/2有理数，则存在正整数 p，q，使得 21/2=p/q,且（p, q）=1平方得：p 2=2q2, 即 2|p2，所以 p=2m, m N因此 p2=4m2=2q2 q2=2m2 q=2n, n N3则（p, q）=(2m,2n)=2(m, n)2 与（p, q）=1 矛盾所以假设不成立，原结论正
9、确，2 1/2不是有理数。（2）假设是 71/2有理数，则存在正整数 m，n，使得 71/2=p/q,且（m, n）=1平方得：m 2=2n2, 即 7|m2将 m 表示成 n 个素数 pi 的乘积，m= p 1 p2 p3 pn ， pi 为素数。因为 7 为素数，假设 7 !| m，则 7 !p 1 ，p 2，p 3 ，p n所以 m2= p12 p22 p32 pn 2=( p1 p2 p3 pn)( p1 p2 p3 pn)所以 7 !| m2，与 7|m2矛盾，故 7|m, m=7k同理可知：7|n, n=7 k 0所以(m, n)=(7k,7 k 0)=7(k, k0)7 与已知矛
10、盾故原结论正确，7 1/2不是有理数。（3）同理可证 171/2不是有理数。41证明：假设 log210 是有理数，则存在正整数 p, q,使得 log210=p/q,且（p, q）=1又 log210=ln10/ln2=p/q Ln10q=ln2p 10q=2p(2*5)q=2p 5q=2p-q所以只有当 q=p=0 是成立，所以假设不成立故原结论正确，log 210 是无理数。同理可证 log37，log 1521 都是无理数。50 （1）解：因为 8=23, 60=22*3*5所以8,60=2 3*3*5=12051 （4）解：(47 1179111011001,411183111101
11、1000)= 4104707908301011000=1011000471179111011001,4111831111011000= 4111471179111831111011001第二章同余1解：（1）其中之一为 9，19，11，21，13，23，15，25，17（2）其中之一为 0，10，20，30，40，50，60，70，80（3）.（1）或（2）中的要求对模 10 不能实现。2证明：当 m2 时，因为(m-1) 2=m2-2m+1=m(m-2)+1所以(m-1) 21(mod m)即 1 与(m-1) 2在同一个剩余类中，故 02,12,(m-1)2一定不是模 m 的完全剩余系。6
12、解：2 12(mod7), 2 24(mod7), 2 31(mod7)又 20080509=6693503*3所以 220080509=(23)66935031(mod7)故 220080509是星期六。7证明：（i）因为 ai b i (modm),1ik 所以 ai=bi+kim又 a1+a2+ +ak=a i=(b i+kim)=b i+m*k i所以有a ib i (mod m)即 a1+a2+ +ak=b1+b2+ +bk (mod m)（ii）因为 ai b i (mod m),1ik 所以 ai(mod m)=bi (mod m)所以（a 1a2ak）mod m(a 1mod
13、m)( a2mod m)(ak mod m)mod m(b 1mod m)( b2mod m)(bk mod m)mod m（b 1b2bk）mod m所以 a 1a2aka 1a2ak(mod m)8证明：如果 a2b 2(mod p) 则 a2= b2+kp , k Z 即 kp=a2-b2=(a+b)(a-b) 所以 p|(a+b)(a-b) 又 p 为素数，根据 1.4 定理 2 知 p|a+b 或 p|a-b 得证。9证明：如果 a2b 2(mod n) 则 a2= b2+kn , k Z 4即 kn=a2-b2=(a+b)(a-b) 所以 n|(a+b)(a-b) 由 n=pq 知
14、 kpq=a2-b2=(a+b)(a-b)因为 n!|a-b, n!|a+b，所以 p,q 不能同时为 a-b 或 a+b 的素因数。不妨设 p|a-b, q|a+b ,则 q!|a-b, p!|a+b 即(q, a-b)=1,(p, a+b)=1因此(n, a-b)=(pq, a-b)=(p, a-b)=p1(n, a+b)=(pq, a+b)=(q, a+b)=q1故原命题成立。10证明：因为 ab (mod c) 则 a=cq+b , q Z根据 1.3 定理 3 知(a, c)=(b, c)17解：（1）a k+ak-1+ +a0=1+8+4+3+5+8+1=30因为 3|30 ,9!
15、|30 所以 1843581 能被 3 整除，不能被 9 整除。（2）a k+ak-1+ +a0=1+8+4+2+3+4+0+8+1=31因为 3!|31 , 9!|31 所以 184234081 不能被 3 整除，也不能被 9 整除。（3）a k+ak-1+ +a0=8+9+3+7+7+5+2+7+4+4=56因为 3!|56 , 9!|56 所以 8937752744 不能被 3 整除，也不能被 9 整除。（4）a k+ak-1+ +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58因为 3!|58 , 9!|58 所以 4153768912246 不能被 3 整除，也不能被
16、9 整除。20解：（89878*58965）mod9(89878mod9)*(58965mod9)mod9(4*6)mod96(mod9) 5299?56270(mod9)又 5299?56270(45+?)mod9?(mod9)所以 ?=6 即未知数字为 6。21解：（1）因为 875961*2753(36mod9)(17mod9)mod9 0(mod9)241052063326(mod9) 8(mod9)所以等式 875961*2753=2410520633 不成立（2）因为 14789*23567(29mod9)(23mod9)mod9 1(mod9)34853236741(mod9)
17、5(mod9)所以等式 14789*23567=348532367 不成立（3）因为 24789*43717(30mod9)(22mod9)mod9 3(mod9)109270071330(mod9) 3(mod9)所以等式 24789*43717=1092700713 可能成立（4）这种判断对于判断等式不成立时简单明了，但对于判断等式成立时，可能会较复杂。22解：因为 7 为素数，由 Wilso 定理知：(7-1)! -1(mod7) 即 6！-1（mod7）所以 8*9*10*11*12*131*2*3*4*5*6(mod7) 6!(mod7) -1(mod7)31证明：因为 c1,c2,
18、c (m)是模 m 的简化剩余系对于任一 ci，有 m-ci也属于模 m 的简化剩余系所以 ci+(m-ci)0(modm)因此 c1+c2+c (m)0(modm)32证明：因为 a (m)1(modm) 所以 a (m)-10(modm)a (m)-1=(a-1)(1+a+ a2+ a (m)-1) 0(modm)又（a-1,m）=1所以 1+a+ a2+ a (m)-1 0(modm)33证明：因为 7 为素数，由 Fermat 定理知 a7 a(mod7)又（a，3）=1 所以(a,9)=1 由 Euler 定理知 a (9)a 61(mod9) 即 a7a(mod9)又(7,9)=1
19、, 所以 a7a(mod7*9) 即 a7a(mod63)34证明：因为 32760=23*32*5*7*13 又(a,32760)=1 所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=15有：a (13)1(mod13) 即 a121(mod13)a (8)a 41(mod8) 即 a121(mod8)a (5)a 41(mod5) 即 a121(mod5)a (7)a 61(mod7) 即 a121(mod7)a (9)a 61(mod9) 即 a121(mod9)又因为5,7,8,9,13=32760所以 a121(mod32760)35证明：因为(p,q)=1 p,q
20、 都为素数 所以 (p)=p-1, (q)=q-1由 Euler 定理知：p (q)1(modq) q (p)1(modp)即 pq-11(modq) q p-11(modp)又 q p-10(modq) p q-10(modp)所以 pq-1+qp-11(modq) q p-1+pq-11(modp)又p,q=pq 所以 pq-1+qp-11(modpq)36证明：因为(m,n)=1 由 Euler 定理知：m (n)1(modn) n (m)1(modm) 所以 m (n)+n (m)(m (n)modn)+ (n (m)modn)1+01(modn) 同理有：m (n)+n (m) 1(
21、modm)又m,n=mn 所以 第三章.同余式1 （1）解：因为（3，7）=1 | 2 故原同余式有解又 3x1（mod7） 所以 特解 x05（mod7）同余式 3x2（mod7）的一个特解 x02* x 0=2*53（mod7）所有解为：x3（mod7）（3）解：因为（17，21）=1 | 14 故原同余式有解又 17x1（mod21） 所以 特解 x05（mod21）同余式 17x14（mod21）的一个特解 x014* x 0=14*57（mod21）所有解为：x7（mod21）2 （1）解：因为（127，1012）=1 | 833 故原同余式有解又 127x1（mod1012） 所以
22、 特解 x0255（mod1012）同余式 127x833（mod1012）的一个特解 x0833* x 0=833*255907（mod1012）所有解为：x907（mod1012）3见课本 3.2 例 17 （1）解：因为（5，14）=1 由 Euler 定理知，同余方程 5x3（mod14）的解为：x5 (14)-1*39（mod14）（2）解：因为（4，15）=1 由 Euler 定理知，同余方程 4x7（mod15）的解为：x4 (15)-1*713（mod15）（3）解：因为（3，16）=1 由 Euler 定理知，同余方程 3x5（mod16）的解为：x3 (16)-1*57（m
23、od16）11证明：由中国剩余定理知方程解为：xa 1M1M1+ a2M2M2+ akMkMk（mod m）因为 mi两两互素，又中国剩余定理知：M iMi1（mod m i）又 Mi=m/mi 所以（m，M i）1（mod m i）所以 MiMi=Mi (mi)（mod m i）代入方程解为 xa 1 M1 (m1)+ a2 M2 (m2)+ ak Mk (mk)(mod m) 得证。612 （1）解：由方程组得：3x+3y2(mod7)6x+6y4(mod7) x+y-4(mod7)X5(mod 7) y5 (mod 7)（2）解：由方程组得：2x+6y2(mod7) 2x-y2(mod7
24、)6x+8y4(mod7) x-y-4(mod7)X6(mod 7) y3 (mod 7)13见课本 3.2 例 414同课本 3.2 例 3 21000000562（mod1309）15 （1）解：等价同余式组为：23x1（mod4）23x1（mod5）23x1（mod7）所以 x3（mod4） x2（mod5） x4（mod7）所以 x3*35*3 + 2*28*2 + 4*20*667（mod140）（2）解：等价同余式组为：17x1（mod4）17x1（mod5）17x1（mod7）17x1（mod11）所以 x1（mod4） x2（mod5） x-3（mod7） x7（mod11）所
25、以 x1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 557（mod1540）19解：3x 14+4x13+2x11+x9+x6+x3+12x2+x0（mod7）左边=(x 7-x)( 3x7+4x6+2x4+x2+3x+4)+ x6+2x5+2x2+15x2+5x所以原同余式可化简为：x 6+2x5+2x2+15x2+5x0（mod7）直接验算得解为：x0（mod7） x6（mod7）20解：f(x) 4x 3+7（mod243）直接验算的同余式 f（x）0(mod3)有一解：x 11（mod3）f(x1) 4*1 3*7=-1(mod3) f(x1)-1-
26、1(mod3)所以 t1-f（x 1）*( f(x 1)-1(mod3)/311(mod 3)x2 x 1+3 t14(mod 9)t2-f（x 2）*( f( x1)-1(mod3)/322(mod 3)x3 x 2+32 t222(mod 27)t3-f（x 3）*( f( x1)-1(mod3)/330(mod 3)x4 x 3+33 t322(mod 81)t5-f（x 4）*( f( x1)-1(mod3)/342(mod 3)x5 x 4+34 t4184(mod 243)所以同余式 f（x）0(mod243)的解为：x 5 184(mod 243)第四章二次同余式与平方剩余2解：
27、对 x=0,1,2,3,4,5,6 时，分别求出 yx=0,y21(mod7),y1,6(mod7)x=4,y24(mod7),y2,5(mod7)当 x=1,2,3,5,6 时均无解5解：对 x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 时，分别求出 yx=0,y21(mod17),y1,16(mod17)x=1,y23(mod17),无解x=2,y211(mod17),无解x=3,y214(mod17),无解7x=4,y21(mod17),y1,16(mod17)x=5,y212(mod17),无解x=6,y22(mod17),y6,11(mod17
28、)x=7,y211(mod17),无解x=8,y211(mod17),无解x=9,y28(mod17),y5,12(mod17)x=10,y28(mod17),y5,12(mod17)x=11,y20(mod17),y0(mod17)x=12,y27(mod17),无解x=13,y21(mod17),y1,16(mod17)x=14,y25(mod17),无解x=15,y28(mod17),y5,12(mod17)x=16,y216(mod17),y4,13(mod17)10解：(1）.（17/37）=(-1) (17-1)(37-1)/(2*2)*(37/17)=-1(4）.（911/200
29、3）=(-1) (2003-1)(911-1)/(2*2)*(2003/911)=1/3=1(6）.（7/20040803）=(-1) (7-1)(20040803-1)/(2*2)*(20040803/7)=112解：（1）.因为（-2/67）=(65/67)=1所以-2 是 67 的平方剩余所以 x2-2(mod67)有 2 个解。（4）.因为（2/37）=(-1) (37*37-1)/8=-1所以 2 是 37 的平方非剩余所以 x22(mod37)无解。14证明：（1）因为 p 为其素数，模 p 的所有二次剩余个数为(p-1)/2 个，设为 a1, a2, a3, a(p-1)/2 则
30、 a1*a2*a3a(p-1)/21 2*22*32(p-1)/2)2(mod p)1*2*3(p-1)/2)*(-(p-1)*(-(p-2)*(-(p-(p-1)/2)(mod p)1*2*3(p-1)/2)*(p-(p-1)/2)*(p-2)*(p-1)(-1) (p-1)/2(mod p)(p-1)!*(-1) (p-1)/2(mod p)(-1)*(-1) (p-1)/2(mod p) （2.4 定理 3）(-1) (p+1)/2(mod p)所以模 p 的所有二次剩余乘积模 p 的剩余为(-1) (p+1)/2得证。（2）1，2，3,p-1 为 p 的一个完全剩余系1*2*2*(p-
31、1)-1(mod p) (-1) (p+1)/2(-1)(p-1)/2(mod p)因为模 p 的所有二次剩余乘积模 p 的剩余为(-1) (p+1)/2所以模 p 的所有非二次剩余乘积模 p 的剩余为(-1) (p1)/2（3）当 p=3 时，其二次剩余只有 1，所以 p=3 时，模 p 的所有二次剩余之和模 p 的剩余为 1当 p3 时，由（1）得 a1+a2+a3+a(p-1)/2p(p-1)(p+1)/24(mod p)因为 p 为奇素数，所以 p 只能取 3k-1 或 3k+1 形式，代入上式得 0所以当 p3 时，模 p 的所有二次剩余之和模 p 的剩余为 0。（4）因为模 p 的
32、所有二次非剩余之和与所有二次剩余之和的和可以被 p 整除所以由(3)得，当 p=3 时，模 p 的所有二次非剩余之和模 p 的剩余为-1;当 p3 时，模 p 的所有二次非剩余之和模 p 的剩余为 0。16解：(1）.因为（7/227）=(-1) (227-1)(7-1)/(2*2)*(227/7)= 1所以 7 是 227 的二次剩余所以 x27(mod227)有解(3）.因为 11 对 91 的逆元是 58所以原同余方程等价于 x216(mod91)8又 16 是 91 的平方剩余所以 11x2-6(mod91)有解21证明：应用模重复平方法11=20+21+23令 x=23,b=2,a=
33、1(1)x0=1 a0=a*b2(mod23) b 1=b24(mod23)(2)x1=1 a1=a0*b18(mod23) b 2=b1216(mod23)(3)x2=0 a2=a1*b208(mod23) b 3=b223(mod23)(4)x3=1 a3=a2*b31(mod23) 所以 2111(mod23) 即 23|211-147|223-1 与 503|2251-1 应用同样的方法得证。第五章原根与指标1解：因为 (13)=12,所以只需对 12 的因数 d=1,2,3,4,6,12,计算 ad(mod12)因为 212, 2 24, 2 38, 2 43, 2 6-1, 2 1
34、21(mod13)所以 2 模 13 的指数为 12；同理可得：5 模 13 的指数为 4，10 模 13 的指数为 6。2解：因为 (19)=18,所以只需对 18 的因数 d=1,2,3,6,9,18 计算 ad(mod12)因为 313, 3 29, 3 38, 3 67, 3 9-1, 2 181(mod13)所以 3 模 19 的指数为 18；同理可得：7 模 19 的指数为 3，10 模 19 的指数为 18。3解：因为 (m)= (81)=54=2*33,所以 (m)的素因数为 q1=2,q2=3,进而(m)/q1=27, (m)/q2=18这样，只需验证：g 27,g18模 m
35、 是否同余于 1。对 2，4，5，6逐个验算：因为 227 1(mod81) 218 1(mod81) 根据 5.2 定理 8 得所以 2 是模 81 的原根7证明：因为（a, m）=1, 故由 ordm(a)=st 知：a st1(mod m) 即(a s)t1(mod m)不妨令 ordm(as)=r 则 asr1(mod m) 所以 st|sr由(a s)t1(mod m)得 r|t 即 tk*r k N1 rt 所以 srst所以 sr=st 所以 r=t所以 ordm(as)=t8解：存在举例：如 n=7,d=3 因为 (7)=6 d=3|6存在 a=2 (2,7)=1, 2 (7)
36、1(mod 7) 又 231(mod 7)所以 ord7(2)=3 满足条件。10证明：因为 p 为一个奇素数，p-1/2 也是一个奇素数所以 (p)=p-1=2*(p-1)/2 即 (p)的不同素因数为 2，p-1/2又因为 a (p)/2=ap-1/2 1(mod p) a (p)/(p-1)/2=a2 1(mod p)根据 5.2 定理 8 得 a 是模 p 的原根。15证明：反证法假设 n 是一个合数，令 ordn(a)=m 则 am1(mod n)因为 an-11(mod n) 所以由 5.1 定理 1 得 m|n-1 即 n-1=k*m对 n-1 的所有素因数 q，必可找到一个 q1使 m|(n-1)/q1)所以 an-1/q=am*t1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。16解：因为 d=(n, (m)=(22, (41)=(22,40)=2 ind5=22所以(n, (m)|ind5，同余式有解等价同余式为 22indxind5(mod40) 即 11indx11(mod20)解得：indx=1,21(mod40)9所以原同余式解为 x=6,35(mod41)17解：因为 d=(n, (m)=(22, (41)=(22,40)=2 ind29=7(2,7)=1 所以原同余式无解。
