《初等数论》习题解答作业3一．选择题1，B 2，C 3，D 4，A二．填空题1，自反律 2，对称性 3，13 4，十进位 5，3 6，2 7，1三．计算题1， 解：由Euler 定理知：（a,m ）=1 则 a φ (m)≡1 (modm)∵(3,100)=1. 3φ (100)=340≡13360≡13364=3360×34≡34 (mod 100)∴34≡81 (mod 100)故：3364的末两位数是81.2, 解：132=169≡4 （mod 5）134=16≡1 (mod 5)1316≡1 (mod 5)1332≡1 (mod 5)1348≡1 (mod 5)1350=1348×1321350≡132≡4 (mod 5)3, 解： ∵(7,9)=1. ∴只有一个解7X －5≡9Y (mod 9)7X －9Y ≡5 (mod 9)解之得：X=2，Y=1∴X=2+9≡11=2 (mod 9)4, 解： ∵（24，59）=1 ∴只有一个解24X ≡7 (mod 59)59Y ≡﹣7 (mod 24)11Y=﹣7 (mod 24)24Z=7 (mod 11)2Z=7 (mod 11)11W=﹣7 (mod 2)W =﹣7 (mod 2)W=﹣1 (mod 2)Z=2711+-= －2 Y=117242-⨯-=－5X=247595+⨯-=2288-=－12 =47(mod59)5 解 ∵（45，132）=3，∴同余式有三个解。

45X ≡21（mod32）15x ≡7 (mod44)44y ≡-7 (mod15)14y ≡-7 (mod15)15z ≡-7 (mod14)z ≡7 (mod14) y=147715-⨯=7 x=157744+⨯=21 ∴x=21+31322⨯=109 (mod132) x=21+31321⨯=65 (mod132) x=21 (mod132)6、解 ∵（12，45）=3, ∴同余式有三个解。

4x+5≡0 (mod15)4x ≡15y-5由观察法：∴x=10, y=3∴x=10 (mod45)x=10+31×45=25 (mod45) x=10+32×45=40 (mod45) 7、解 37x=25 (mod107)107y=-25 (mod37)33y=-25 (mod37)37z= -25 (mod37)4z= 25 (mod37)33w= -25 (mod37)w= -25 (mod37)w=3 z=425333+⨯=31 y=33253137-⨯=331122=34 x=372534107+⨯=373633=99 ∴x=99 (mod321)x=99+3321=2 x=99+33212⨯=313 (mod321) 8、解 ∵(m1,m2) ≠1, 即（15，6）≠1∴方程组无解9、解79.8.7≡1 （mod7）,72x ≡1 (mod7),2x 1≡1 (mod7), x 1 =4 79.8.7≡1 （mod8）,63 x 2≡1 (mod8), 7x 1≡1 (mod8), x 1 ≡779.8.7≡1 (mod9), 56 x 3≡1(mod9), 2x 3≡1 (mod9), x 3 =5x=72×4×1+63×7×2+56×5×3=288+882+840=2010≡498 (mod504)10、解29752⨯⨯⨯ x 1≡ 1， 315 x 1≡1，x ≡1 (mod2) 29752⨯⨯⨯ x 2≡ 1， 126 x 1≡1，x 2≡1 (mod5) 29752⨯⨯⨯ x 3≡ 1， 90x 3≡1，6x 3≡1, x 3 =6 (mod7)29752⨯⨯⨯ x 4≡ 1， 70x 4≡1，7x 4≡1 x 4 =4 (mod9)x=315×1×1+125×1×2+90×6×3+70×4×5=315+252+1620+1400=3587≡437 (mod 630)三、证明题1、证：设a=a n ×10n + a n-1×10n-1+……+ a 2×102+ a 1×10+a 0∵a n ×10n ≡0 （mod5） a n-1×10n-1 ≡0 （mod5）…………a 1×10 ≡0 （mod5）a 0 =5 ≡0 （mod5）∴a ≡0 (mod5)∴5∣a2、证：设 n=2m+1 m=0,1,2……∵22≡1 （mod3）∴22m ≡1 （mod3）又∵2≡-1 （mod3）∴22m+1≡-1 （mod3）∴22m+1≡2n +1≡0（mod3）∴3∣(2n +1)，当n 为奇数时。

3、见作业1《初等数论》习题解答作业4一、计算题1、 解：⎥⎦⎤⎢⎣⎡593438=⎥⎦⎤⎢⎣⎡5932⎥⎦⎤⎢⎣⎡593219=215932121981593)1(*)1(2-⋅----*⎥⎦⎤⎢⎣⎡219593=⎥⎦⎤⎢⎣⎡219155 =1155215564155219)1(62121921155-=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡--*- 所以，同余式x 2≡438 (mod593)无解2、 解：⎥⎦⎤⎢⎣⎡1847365⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡-=-⋅-365236511365223651847)1(21184721365 =()1)1(112113651)1(81112136521118136522=--=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-⋅----- 所以，同余式()1847mod 3652≡x 有解。

3、 解：2111-=5 12≡1，22≡4 32≡9 42≡16≡5，52= 25≡3所以1、2、3、4、59是11的平方剩余。

2、6、7、8、是11的平方非剩余。

4、 解：2117-=8 12≡1，22≡4，32≡9，42≡1652≡8，62≡2，72≡15，82≡13 所以 1、2、4、8、9、13、15、16是17的平方剩余3、5、6、7、10、11、12、14是17的平方非剩余。

5、解：()()⎥⎦⎤⎢⎣⎡--=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-⋅---⋅-6742911429674292429134429563)1(5634292142921678142921563214292=()()11311327127132767167272127211321672127=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-*--⋅- 6、解：()⎥⎦⎤⎢⎣⎡--=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡-⋅--⋅-15383)1(383153832383238344314433832138321152144321383 =()11115215833811532==⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡- 二、证明题：1、 证设相邻两整数分别为n,n+1(n+1)3-n=n 3+3n 2+3n+1-n 3=3n 23n+1设：3n 2+3n+1≡0 （mod5）21n 2+2m+7≡0n 2+(21+5)n+7≡0(n+13)2≡132-7=162≡2((mod5)又设x 2=2(mod5) [52]=(-1)=-1,故x 2≡2(mod5)无解 故（n+13）2≡2(mod 5)无解。

故相邻两整数的立方差不能被5整除。

2、 证：设m ≡-1(mod4)又设 m=x 2+y 2.对于模4，X 与y 的剩余的解是-1，1，2，0，x 2与y 2对模4的剩余仅是0，1因此，m=x 2+y 2(mod4)仅能与0,2同余，即m=0,m=2(mod4)这与m=-1(mod4)相矛盾，故m=4n-1不能写成两平方数之和。

3、 证：（1）m=a 2+b 2,n=r 2m,n=(a 2+b 2)r 2=r 2a 2+r 2b 2=(ra)2+(rb)2(2) m=a 2+b 2, n=c 2+d 2m,n=(a 2+b 2)(c 2+d 2)=a 2c 2+a 2d 2+b 2c 2+b 2d 2=(a 2c 2+b 2d 2+2abcd)+(a 2d 2+b 2c 2-2abcd)=(ac+bd)2+(ad-bc)24、 证：设 p=a 2+b 2=c 2+d 2p 2=(a 2+b 2)(c 2+d 2)=(ac+bd)2+(ad-bc)2 ------(1)=(ac-bd)2+(ad+bc)2 ------(2)又(ac+bd)(ad+bc)=a 2cd+b 2cd+abc 2+abd 2=(a 2+b 2)cd+(c 2+d 2)ab=p(ab+cd) -------(3)故p\(ac+bd) 或p\(ad+bc)。

4、如果p\(ac+bd)则ac+bd=kp,由此代入(1)则p2=k2p2=(ad-bc)2于是 ad-bcv=0,即 a=rc,b=rd 故p=a2+b2=r2(c2+d2)则必有a=c,b=d.5、如果p\(ad+bc)则ad+bc=kp将此代入（2），与（1）一样推得a=d,b=c综合（1）（2），故有a2+b2=c2+d2故素数写成平方和的形式是唯一的。