第三章同余例题分析
例1：求3406的末二位数。

解：∵（3，100）=1，∴3)100(φ≡1（mod 100）
φ(100)=φ(22·52)=40,∴340≡1(mol 100)
∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)
∴末二位数为29。

例2：证明（a+b ）p ≡a p +b p (mod p )
证：由费尔马小定理知对一切整数有：a p ≡a （p ），b p ≡b (P )，
由同余性质知有：a p +b p ≡a+b (p )
又由费尔马小定理有（a+b ）p ≡a+b (p )
（a+b ）p ≡a p +b p (p )
例3：设素数p >2，则2P -1的质因数一定是2pk +1形。

证：设q 是2p -1的质因数，由于2p -1为奇数，∴q ≠2，
∴（2·q ）=1,由条件q|2p -1,即2p ≡1（mod q ），又∵（q ,2）=1，2p ≡1（mod q ）设i 是使得2x ≡1（mod p ）成立最小正整数
若1<i <p ，则有i |p 则与p 为素数矛盾
∴i=p ,∴p |q -1
又∵q -1为偶数，2|q -1,
∴2p |q -1,q -1=2pk ,即q =2pk +1
例4：证明13|42n +1+3n +2
证：∵42n +1+3n +2≡4·16n +9·3n
≡3n (4+9)≡13×3n ·≡0(13)
∴13|42n +1+3n +2
例5：证明5y +3=x 2无解
证明：若5y +3=x 2有解，则两边关于模5同余
有5y +3≡x 2(mod 5)
即3≡x 2(mod 5)
而任一个平方数x 2≡0,1,4(mod 5)
∴30,1,4(mod 5)
∴即得矛盾，即5y +3=x 2无解
例6：求
50111......被7除的余数。

解：∵111111被7整除，∴ 50111......≡11（mod 7）≡4（mod 7），即余数为
4。

例7：把..0.04263化为分数。

解：设b =...360420，从而1000b=...3642,
100000b=...364263，99000b=4263-42b=990004221
==11000469。

当然也可用直化分数的方法做。

例8：设一个数为62XY427是9，11的倍数，求X ，Y
解：因为9|62XY427
所以9|6+2+X+Y+4+2+7，即9|21+X+Y
又因为11|62XY427，有11|（7+4+X+6-2-Y-2）
即11|（X-Y+13）
因为0≤X，Y ≤9，所以有21≤21+X+Y ≤39，
4≤X-Y+13≤22，由此可知
21+X+Y=27，X-Y+13=11
或21+X+Y=36，X-Y+13=22
X+Y=6，X-Y=-2
或X+Y=15，X-Y=9，解得X=2，Y=4。

例9：证明：8a+7不可能是三个整数的平方和。

证：由于每一个整数对于8，必同余于0，1，2，3，4，5，6，7这八个数之一
注意到对于模8，有
,002≡,112≡,422≡,
132≡,042≡,152≡,462≡,
172≡因而每一个整数对于模8，必同余于0，1，4这三个数
不能222,,z y x 如何变化，只能有)
8(mod 6,5,4,3,2,1,0222≡++z y x 而)8mod 778≡+a ，故78+a 不同余于222z y x ++关于模8
≠+78a 222z y x ++，从而证明了结论。