2024年1月4日发(作者：)
高中数学竞赛专题讲座专题训练
同余的概念与应用
概念与性质
1. 定义：若整数,b 被整数m(m≥1)除的余数相同,则称 同余于b 模m,或,b 对模m 同余.记为≡b(modm).余数r:0≤r0,证明必有一个仅由0或1构成的自然数 是m 的倍数.
证明：考虑数字全为1的数:1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的.
例4. 证明从任意m 个整数 1, 2,…, m 中,必可选出若干个数,它们的和(包括只一个加数)能被m 整除. 证明：考虑m 个数
1, 1+ 2, 1+ 2+ 3,…, 1+ 2+…+ m ,如果其中有一个数能被m
整除,则结论成立,否则,必有两个数属于modm 的同一剩余类,这两个数的差即满足要求.
例5. 证明数11,111,1111,…中无平方数.
证明：因任意整数n 2≡0或1(mod4),而11≡111≡1111≡…≡3(mod4),所以,数11,111,1111,…中无平方数. 例6. 确定n
5=1335+1105+845+275.
解：因n 5≡35+05+45+75≡3+4+7≡4(mod10),所以n 个位数字为4,显然n 的首位数字为1,进一步估量:n 5n≥1,求最小的m+n 使得1000|1978m -1978n .
解：令k=m-n,则1978m -1978n ≡0(mod1000)?2n ?989n (1978k -1) ≡0(mod23?53)?
1
?????≡-≥?≡)
5(mod 0119783)2(mod 0233k n n ，∵1978≡3(mod5)
∴19784≡1(mod5)，∵1978≡3(mod25) ∴197820≡320≡
1(mod25)，∵1978≡-22(mod53),(-22)20≡(25-3)20≡320≡(243)4≡74≡(50-1)2≡26(mod53)∴197820≡26 (mod53),
∴197840≡(25+1)2≡51(mod53),197860≡(25+1)(50+1)≡76(mod53),197880≡(50+1)2≡101(mod53),1978100≡
(25+1)(100+1)≡1(mod53),∴100|k ∴k 最小=100,
m+n=m-n+2n 最小=106.
例13. 设123,,,
是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数n ,数123,,,,n 被n 除的余数都各不相同.证明:在数列123,,,
中,每个整数都刚好出现一次. 证明：数列各项同时减去一个整数不改变本题的条件和结论,故不妨设 1=0.此时对每个正整数k 必有∣ k ∣,(p,)=1, x 2,x 3,…,x p+2这p+1个数中必有两个属于modp 的同一剩余类,即有m>n≥2,使得x m ≡x n
(modp),由题意有x m -x n ≡(x m-1-x n-1)≡0(modp),依次类推,有x m-n+1-x 1≡0(modp),即有
p |x m-n+1,因数列增,所以x m-n+1>p, x m-n+1不是质数.
2. 确定所有正整数n,使方程x n +(2+x)n +(2-x)n =0有整1
数解.
解：显然,若n 为偶数,则方程无实数根,若n=1,则x=-4.当n≥3且为奇数时∵方程左端是首项为1,常数项为2n+1的多项式∴其整解只能是-2t (t 为非负整数)形式:若t=0,1,2则x=-1,-2,-4都不是方程的根;若t≥3,则-2nt +(2-2t )n +(2+2t )n
=0?-2n(t-1)+(1-2t-1)n +(1+2t-1)n =0，∵-2n(t-1)+(1-2t-1)n
+(1+2t-1)n ≡2(mod4)∴左端≠0.综上知,仅当n=1时,原方程有唯一整解x=-4.
3. 问是否存在一个无限项素数数列p 1,p 2,…,p n ,…对任意n 满足|p n+1-2p n |=1?请说明理由.
解：若存在,则由p n+1=2p n ±1>p n 知{p n }递增, p
3>3, p 3≡1或2(mod3).若p 3≡1(mod3),则p 4=2p 3-1即p 4≡1(mod3)∴p 5=2p 4-1,…,p n =2p n-1-1∴p n =2n-3p
3-2n-3+1,取n-3=p 3-1则由132-p ≡1(modp 3)
知p n ≡0(modp 3),矛盾!若p 3≡2(mod3), 则p 4=2p
3+1,即p 4≡2(mod3)∴p 5=2p 4+1,…,p n =2p n-1+1,
∴p n =2n-3p 3+2n-3-1,取n-3=p 3-1则由132-p ≡1(modp 3)知p n ≡0(modp 3),矛盾!
4. 设三角形的三边长分别为整数L,m,n,且L>m>n.已知==}10
3{}103{44m L }103{4n ,其中{x}表示x 的小数部分.求三角形周长的最小值.
1
解：∵}10
3{}103{}103{444n
m L ==∴3L ,3m ,3n 的末四位数相同,从而104|3L -3m
=3m (3L-m -1),104|3L-m -1∴L-m =4k,其中k ∈N *.∵3L-m
=81k =(1+80)k =1+k k k k C C C 8++++ ∴104|3L-m -1?104|2218080k k C
C C ++ 33221808080k k k C C C ++?125|23218080k k
k C C C ++=k(40k-39)+2380k C ∵5|2328080k k
C C +∴5|k, 125|2380k C ，∵125|k(40k-39)+2
380k C ，∴125|k(40k-39)∵5?40k-39∴125?40k-39∴125|k,k=125r,其中r ∈N *.即L-m=4k=500r,同理m-n=500s,s ∈N *.∵n>L-m=500r≥500∴n 小=501，∵m=n+500s≥501+500= 1001，∴m 小=1001,L≥500+1001=1501,所求三角形周长的最小值为501+1001+1501=3003.
解法2：由已知得3L ≡3m ≡3n ≡(mod104)即3L ≡3m ≡3n ≡(mod24) ①，3L ≡3m ≡3n ≡(mod54) ②，由①得3m-n
≡1(mod24) ∵34≡1(mod24) ∴4|m-n,m-n=4k,由②得3m-n
≡34k ≡1(mod54),现求满足此式的k:∵34k -1≡ (1+5?24)k -1≡5k?24+2)1(-k k ?52?28+6)2)(1(--k k k ?53?212≡0(mo
d54)?k=53t,m-n=500t,同理L-n= 500r,其中t,r 为正整数，∵L>m>n ∴r>t,即三角形三条边为500r+n, 500t+n 和n,且有1
n>500(r-t)≥500∴仅当t=1,r=2,n=501时,1000+501+500+501+501=3003.
5. 如果整数n 不是2的倍数,也不是5的倍数.证明n 必能整除一个各位都是1的数。
证明：若数
个+n ,,,,中有被n 整除者，则问题得证；否则必有 个m 1111与 个
r 1111(m>r)使得 个m 1111≡)n (mod r
个1111，即 个个个个r r m r m ][|n 11-=-，因n 不是2和5的倍
数，所以
个r m |n -1111，得证。
6. 设 是45687777的各位数之和, b 是 的各位数之和,c
是b 的各位数之和.求c.
解：∵456877771,且(,m)=1.则有 φ(m)≡1(modm).
2. Fermt 定理：设p 是素数,则对任意正整数 有 p ≡(modp).
证明：若p|,则显然成立.若(p,)=1,则,2,…,(p -1) 对modp
余数各不相同(若p|(m-n)(n3是素数，∴p≡1(mod6)或p≡5(mod6)，∴3p -2p -1≡36k+1-26k+1-1≡3- 2-1≡0(mod7)或3p -2p -1≡36k+5-26k+5-1≡5-4-1≡0(mod7)即7|3p -2p -1∴42p|3p -2p -1.
1
例4. 已知m,n 为正整数,且m 为奇数,(m,2n -1)=1.证明:m|∑=m k n k
1.
证明：∵1,2,…,m 构成modm 的完系,(m,2)=1∴2,4,…,2m
也构成modm 的完系∴(mod )
2(1
1m k k m
k n m k n ∑∑==≡ )(mod )
2(11m k k m k n m k n ∑∑==≡即)(mod 0)12(1m k m k
n n ≡-∑=∵(m,2n -1)=1，∴∑=m k n k m 1
|得证. 例5. 求与数列{}2361,1n n n n n =++-≥中所有项都互质的所有正整数.
解：显然(1, n )=1.设m>1是与{ n }中所有项都互质的正整数,p 为m 的一个质因数,若p>3,则由费马小定理得:()12
1mod p p -≡,()131mod p p -≡,()161mod p p -≡，记121p mp -=+,131p np -=+ 31p np -=+,16
1p tp -=+(,,m n t Z ∈),则2222p p p p
mp np tp ----+++=++-=++-= 323266
mp np tp m n t p ++++==?，∵由 p-2为整数,(,6)1p =，∴6|3m+2n+t,2p p -这与(m, p-2)=1矛盾!若p=2或3,则
2=48=24?3,p| 2也矛盾!故与{}n 中所有项都互质的正整数只有1.
1
例6. 求使得7d ≡1(mod2r )(整数r≥3)的最小正整数d 0.
解：∵Φ(2r )=2r (1-21)=2r-1及d 0|Φ(2r )∴d 0=2k , 0≤k≤r -1.先证:对任意奇数,必有)2(mod 122r r ≡-:
归纳法,设=2t+1,当r=3时, 2=4t(t+1)+1≡1(mod23),设当r=n 时,)2(mod 122n n ≡-,则当
r=n+1时,)1)(1(1221222+-=----n n n 可被2n+1整除,即有)2(mod 1121+≡-n n ,故结论成立. 由此可知d 0=2k
中的k 满足0≤k≤r -2.我们证明:对任意整数r≥3,必有327-r ?1(mod2r
):归纳法,当r=3时,显然成立,设当r=n
时,327-n ?1(mod2n )∵3
27-n ≡1(mod2n-1) ∴3
27-n =1+s?2n-1,其中整数2?s,∴s n n 1(1)7
(722232+==-- n n s s n n 2)21(1)7(722
2232-?++==--,2?1+s?2n-2,即227-n ?1(mod2n+1)∴327-r ?1(mod2r ),由此推
得:j 27?1(mod2r ),0≤j≤r -3,故d 0=2r-2为所求.
例7求所有的正整数对(p,n)满足:(ⅰ)p 是素数; (ⅱ)n≤2p;
(ⅲ)n p-1|(p-1)n +1.
解：显然(p,1)和(2,2)是满足题意的正整数对，下设n≥2,p≥3.∵(p-1)n +1为奇数∴n 为奇数且n1989即m 2≥45∴m 2
=49或81.若m 2=49即+b+c+d=49.∵,b,c,d 的最大者为1
d=n 2∴4n 4≥ 2+b 2+c 2+d 2=1989∴n≥5,∵+b+c= 49-n 2∴5≤n≤6即n=5或6,d=25或36.+b+c=24或13, 2+b 2+c
2 =1364或693,∵(+b+c)2=242=576> 2+ b 2+c 2或(+b+c)2=132=169> 2+b 2+c 2 ,∴此时方程无解.∴m
2=+b+c+n 2=81, 2+b 2+c 2+n 4=1989,∵4n 2≥81 ∴n≥5∵1989-n 4≥3即n 4≤1992∴5≤n≤6即n=5或6. 当n=5时,+b+c=56, 2+b 2+c 2 =1364,∵4|1364= 2+ b 2+c 2∴,b,c
均为偶数:=2 1,b=2b 1,c=2c 1且 12+b 12+c 12 =341,
1+b 1+c 1=28∵ 12+b 12+c 12 =341≡1(mod4)
∴ 1,b 1,c 1必定两个偶数一个奇数: 1=2 2,b 1=2b 2,c
1=2k-1且2( 2+b 2+k)=29矛盾!当n=6时,+b+c=45, 2+ b
2+c 2 =693,∵693≡1(mod4)∴=2 1,b=2b 1,c=2k-1且 1+b
1+k=23, 12+b 12+k(k-1) =173,∵k(k-1)为偶数∴ 1,b 1一奇一偶: 1=2 2,b 1=2r-1且2 2+2r+k=24,4 22+4r(r-1)+k(k-1)
=172∴2|k,4|k(k-1)∴4|k,又
∵173-k(k-1) =2)23(2)(2
2112
121k b b -=+≥+,即有k 2-16k+61≤0∴7≤k≤9,∵4|k
∴k=8, 2+r=8, 22+ r(r-1)=29,消去 2得2r 2-17r+35=0,解得r=5,(,b,c,d)=(12,18,15,36)∴m 2=81,n 2=36,(m,n)=(9,6).
8. 求方程2x ?3y -5z ?7w =1的所有非负整数解(x,y,z,w).
解:(1)若y=0,则2x -5z ?7w =1,当z≠0时, 2x ≡1(mod5)∵1
24≡1(mod5)∴4|x,从而3|2x -1=5z ?7w ,这不可能∴z=0, 2x
-7w =1,当x=1,2,3时,(x,w)=(1,0),(3,1);当x≥4时, 7w =2x -1≡-1(mod16),但当w 为偶数时7w ≡ 1(mod16),当w 为奇数时7w ≡7(mod16),矛盾.∴这时解为(1,0,0,0),(3,0,0,1);(2)若y>0.①当x=1时,2?3y - 5z ?7w =1,则5z ?7w ≡-1(mod3),即(-1)z
≡-1(mod3)∴z 为奇数∴2?3y ≡1(mod5)∵34≡1(mod5),∴y≡1(mod4)即y=4m+1.当w≠0时, 2?3y ≡1(mod7)∵36≡1(mod7)∴y≡4(mod6),y=6n +4=4m+1,即6n=4m-3矛盾∴必有w=0, 2?3y -5z =1,当y=1时,z=1;当y≥2时,5z ≡-1(mod9)∵56≡1(mod9)∴z≡3(mod6),53+1|5z +1,7|5z +1=2?3y 矛盾!
∴这时解为(1,1,1,0),②当x≥2时,∵5z ?7w ≡-1(mod4),5z ?7w
≡-1(mod3)即(-1)w ≡-1(mod4),(-1)z ≡-1(mod3)∴w,z 都是奇数,2x ?3y =5z ?7w +1≡35+1≡4(mod8),∴x=2,y=2k,方程为4?3y -5z ?7w =1∴4?3y ≡1(mod5),y≡2(mod4),
4?3y ≡1(mod7),y≡2(mod6)∴y≡2(mod12),设y=12m+2(m≥0),则5z ?7w
=4?312m+2-1=(2?36m+1-1)(2?36m+1+1)
∵2?36m+1+1≡0(mod7),(2?36m+1-1,2?36m+1+1)=1∴5|2?36m+1-1,∴?????=+?=-?++w m z m 713
251321616,若m≥1,则5z ≡ -1(mod9),由①的证明知不可能.若m=0,则y=2,?????=+?=-?w z 7
1325132得z=w=1,得解(2,2,1,1).故原方程的所有解1
为:(x,y,z,w)=(1,0,0,0),(3,0,0,1),(1,1,1,0),(2,2,1,1).
9. 求方程5x +1=2y +2z ?5t 的所有正整数解(x,y,z,t).
解:设(x,y,z,t)是方程的正整数解,则2y ≡1(mod5)∵24≡1(mod5)∴4|y,对方程两边mod4得2z ≡2(mod4)∴z=1.设y=4r,得5x +1=24r +2?5t 即5x -2?5t =16r -1,两边mod3得:(-1)x +(-1)t ≡0(mod3)∴x,t 一奇一偶∵5t ≡1或5(mod8)∴对5x =2?5t +16r -1,两边mod8得: 5x ≡2?5t -1≡1(mod8)∴x
为偶数,t 为奇数.(1)若t=1,则5x =16r +9,设x=2m,则(5m
-3)(5m +3)=16r .∵(5m -3,5m +3)=(5m -3,6)=2∴5m
-3=2,5m +3=24r-1,∴m=1,24r-1=23 ∴r=1,y=4,x=2,得解(x,y,z,t)=(2,4,1,1);(2)若t>1,则t≥3,x≥4,53|5x -2?5t =16r -1∵16r -1=(15+1)r =15r +…+
2215?r C +151?r
C ∴5|r,令r=5k,则165k -1≡55k -1≡(5?32)k -1≡0(mod11),∴11|5x -2?5t =5t (5x-t -2),即11|5x-t -2,但5n ≡1,3,4,5,9(mod11),即11?5x-t -2,矛盾!故原方程有唯一解(x,y,z,t)=(2,4,1,1).
1
