nbhkdz.com冰点文库

高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题)

时间:2013-03-18

同余的概念与应用
概念与性质 1. 定义: 若整数 a,b 被整数 m(m≥1)除的余数相同,则称 a 同余于 b 模 m,或 a,b 对模 m 同余.记为 a≡b(modm). 余数 r:0≤r<1. 2. 性质:(ⅰ )a≡b(modm) ? m|a-b,即 a=b+mk,k∈ Z. (ⅱ a≡b(modm),b≡c(modm),则 a≡c(modm). )若 (ⅲ a1≡b1(modm),a2≡b2(modm),则 a1± 2≡b1± 2(modm),a1a2≡b1b2(modm); )若 a b n n-1 n (ⅳ f(x)=anx +an-1x +…+a1x+a0,g(x)=bnx +bn-1xn-1+…+b1x+b0 是两个整系数多项式,满足 ai≡ )设 bi(modm)(0≤i≤n).若 a≡b(modm),则 f(a)≡f(b)(modm).(ⅴ )ac≡bc(modm) ? a≡b(mod

m ), ( c, m)

(ⅵ m≥1,(a,m)=1,则存在整数 c 使得 ac≡1(modm).称 c 为 a 对模 m 的逆或倒数,记为 c=a-1(modm); )若 (ⅶ ? )

?a ? b(modm1 ) 同时成立 ? a ? b (mod[m1,m2]);(ⅷ a≡b(modm1),a≡b(modm2),且(m1,m2)= )若 a ? b(modm2 ) ?

1,则 a≡b(modm1m2). 3. 剩余类:设 m 为正整数,把全体整数按对模 m 的余数分成 m 类,相应 m 个集合记为:K0,K1,…,Km-1, 其中 Kr={qm+r|q∈ Z,0≤余数 r≤m-1}称为模 m 的一个剩余类。 性质:(ⅰ Z ? )
0 ?i ? m ?1

? K i 且 Ki∩Kj=φ(i≠j).

(ⅱ )每一整数仅在 K0,K1,…,Km-1 一个里. (ⅲ )对任意 a、b∈ Z,则 a、b∈ r ? a≡b(modm). K 4. 完全剩余系:设 K0,K1,…,Km-1 为模 m 的全部剩余类,从每个 Kr 里任取一个 ar,得 m 个数 a0,a1,…,am-1 组成的数组,叫做模 m 的一个完全剩余系。0,1,2,…,m-1 叫做模 m 的最小非负完全剩余系。 性质:(ⅰ 个整数构成模 m 的一完全剩余系 ? 两两对模 m 不同余。 )m (ⅱ )若(a,m)=1,则 x 与 ax+b 同时跑遍模 m 的完全剩余系。 5. 既约剩余系:如果 Kr 里的每一个数都与 m 互质,则 Kr 叫与 m 互质的剩余类,在与模 m 互质的全部剩 余类中,从每一类任取一个数所做成的数组,叫做模 m 的一个既约剩余系。 性质:(ⅰ r 与模 m 互质 ? Kr 中有一个数与 m 互质; )K (ⅱ )与模 m 互质的剩余类的个数等于 ?( m ) ; (ⅲ )若(a,m)=1,则 x 与 ax+b 同时跑遍模 m 的既约剩余系。 (ⅳ )设(a,p)=1,则 d0 是 a 对于模 p 的阶 ? ado≡1(modp),且 1,a,…,ado-1 对模 p 两两不同余.特别地,do= Φ(p) ? 1,a,…,aΦ(p)-1 构成模 p 的一个既约剩余系. 例 1. 设 xi∈ {-1,1},i=1,2,…,101,证明:x1+2x2+…+100x101≠0. 证明:∵ 1+2x2+…+100x101≡1+2+…+101≡51≡1(mod2)∴ x 成立. 例 2. 设 p 为质数.求证: Cn
p

?n? ? ? ?(modp) . ? p? ? n ? n?i ? p? p ? ?
.∴ n(n-

证明:∵ n≡0,1,2,…,p-1(modp)∴ 必有某一个 i(0≤i≤p-1)使得 n≡i(modp),从而 ?
p

1)…(n-i+1)(n-i-1)…(n-p+1)≡i(i-1)…1(p-1)…(i+1)≡(p-1)!(modp),∴ (p-1)! C n =(p-1)!n(n-1)…(n-i+1)(n-i1

1)…(n-p+1)

n?i ?n? n?i n?i n?i p p ? ? ?(modp ≡(p-1)! (modp),即(p-1)! C n ≡(p-1)! (modp),因((p-1)!,p)=1∴Cn ? p! p p p ? p?

p n

?

n?i ?n? ? ? ?(modp) . p ? p?
例 3. 设 m>0,证明必有一个仅由 0 或 1 构成的自然数 a 是 m 的倍数. 证明: 考虑数字全为 1 的数:1,11,111,1111,…中必有两个在 modm 的同一剩余类中,它们的差即为所求 的 a. 例 4. 证明从任意 m 个整数 a1,a2,…,am 中,必可选出若干个数,它们的和(包括只一个加数)能被 m 整除. 证明:考虑 m 个数 a1,a1+a2,a1+a2+a3,…,a1+a2+…+am,如果其中有一个数能被 m 整除,则结论成立,否 则,必有两个数属于 modm 的同一剩余类,这两个数的差即满足要求. 例 5. 证明数 11,111,1111,…中无平方数. 证明: 因任意整数 n2≡0 或 1(mod4),而 11≡111≡1111≡…≡3(mod4),所以,数 11,111,1111,…中无平方数. 例 6. 确定 n5=1335+1105+845+275. 解:因 n5≡35+05+45+75≡3+4+7≡4(mod10),所以 n 个位数字为 4,显然 n 的首位数字为 1,进一步估

5 ?5? 5 计:n <2×133 +(84+27) <3×133 < ? ? ? 133 ,所以,n< ? 133 <167,所以 n 可取 134,144,154,164,又 4 ? 4?
5 5 5 5

5

n5≡15+(-1)5≡3(mod3),故 n=144. 注:欧拉猜测 4 个自然数的 5 次方之和不是 5 次方,于 1962 年被三位美国数学家推翻,例 6 就是他们举的 反例. 例 7. 求 32006 的个位数及末两位数字. 解: (1)即求 a(0≤a≤9),使得 32006≡a(mod10).∵ 2≡9≡-1(mod10),∴ 4≡1(mod10),32006≡32004+2≡34X501+2≡ 3 3 2 2006 2006 3 (mod10),故 3 的 个 位 数 是 9;(2) 即 求 b(0≤b≤99), 使 得 3 ≡b(mod100). 注 意 到 :4 X25=100 且 4 (4,25)=1,3 ≡81≡1(mod5),∵ 4≡81≡6(mod25),38≡36≡11(mod25),∴ 12≡66≡-9(mod25),316≡-54≡-4(mod25) 3 3 20 2 20 ∴ ≡-24≡1(mod25) ① 3 ≡1(mod4)∴ ≡1(mod4) ② 3 ;∵ 3 ,由① 得 320≡1(mod100),∴ 2006≡ ,② 3 20 X100 6 2006 3 ?3 ≡29(mod100),故 3 的末两位数字是 29. 例 8. 求 1 X3 X5 X 7 X…X2005 的末 3 位数字. 解:注意到:8X125=1000 且(8,125)=1,∵ (2n-3)(2n-1)(2n+1)(2n+3)≡(4n2-9)(4n2-1)≡1(mod8),及 M= 1 X3 X5 X 7 X…X2005=125m 是 1003 个奇数之积,∴ M≡1 X3 X5≡7(mod8), 125m≡5m≡7(mod8),∴ m≡ 3(mod8),∴ M≡125m≡125X3≡375(mod8),∴ M≡125m≡375(mod8).即 1 X3 X5 X 7 X…X2005 的末 3 位数 字为 375. 例 9. 求大于 5 的素数平方被 30 除的余数. 解:设 p 是大于 5 的素数,且 p≡r(mod30)(r<30),∵ (p,30)=1∴ (r,30)=1,r=1,7,11,13,17,19,23,29,∵ 2≡ 1 2 2 2 2 2 2 2 2 11 ≡19 ≡29 ≡1(mod30), 7 ≡13 ≡17 ≡23 ≡19(mod30),∴ ≡1 或 19(mod30) p k 例 10. 设 n,k 为正整数,求证:存在无限多个形如 n?2 -7 的平方数. 解: 即求使得 m2+7≡0(mod2k)成立的整数 m.当 k=1,2,3 时,取 m=1+4r(r 为正奇数),则有 m2+7≡0(mod2k). 设对 k(≥3)有整数 m 使得 m2+7≡0(mod2k),显然 m 为奇数,对于 k+1,∵ (m+a?2k-1)2+7≡m2+7+ma?2k≡

m2 ? 7 + 2 (am+b)(mod2 ),其中 b= ∈ ,取正整数 a,b 同奇偶,则有(m+a?2k-1)2+7≡0(mod2k+1), 对任意正 Z ∴ 2k
k k+1

整数 k 存在无限多个整数 m 使得 m2+7≡0(mod2k). 例 11. 设对任意正整数 n≥1,b 的质因数都大于 n.证明:n!|a(a+b)(a+2b)(a+3b)…[a+(n-1)b] 证明:∵ 的质因数都大于 n,∴ b (b,n!)=1∴ -1≡1(modn!),∴ -1)na(a+b)(a+2b)(a+3b)…[a+(n-1)b]≡ bb (b -1 -1 -1 -1 -1 -1 (ab )(ab +1)(ab +2)(ab +3)…[ab +(n-1)]≡0(modn!),∵ ,n!)=1,∴ (b n!|a(a+b)(a+2b)(a+3b)…[a+(n-1)b]
2

例 12. 设 m>n≥1,求最小的 m+n 使得 1000|1978m-1978n. 解:令 k=m-n,则 1978m-1978n≡0(mod1000) ? 2n?989n(1978k-1) ≡0(mod23?53) ?
3 ? n ?2 ? 0(mod2 ) ? n ? 3 ,∵ 1978≡3(mod5) ∴ 19784≡1(mod5),∵ 1978≡3(mod25) ∴ 197820≡320≡ ? k 3 ?1978 ? 1 ? 0(mod5 ) ?

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∴ 最小=100, m+n=m-n+2n 最小=106. k 例 13. 设 a1 , a2 , a3 ,? 是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数 n , 数 a1 , a2 , a3 ,?, an 被 n 除的余数都各不相同.证明:在数列 a1 , a2 , a3 ,? 中,每个整数都刚好出现一次. 证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设 a1=0.此时对每个正整数 k 必有 ∣ k∣ a <k:若∣ k∣ a ≥k,取 n=∣ k∣ a1≡ak≡0(mod n),矛盾.现在对 k 归纳证明 a1,a2,…,ak 适当重排后是绝对值 a ,则 小于 k 的 k 个相邻整数.k=1 显然.设 a1,a2,…,ak 适当重排后为-(k-1-i),…,0,…,i (0≤i ≤ k-1),由于 a1,a2,…,ak,ak+1 是(mod k+1)的一个完全剩余系,故必 ak+1≡i+1(mod k+1), 但∣ k+1∣ a <k+1,因此 ak+1 只能是 i+1 或-(k-i),从而 a1,a2,…,ak,ak+1 适当重排后是绝对值小于 k+1 的 k+1 个相邻整数. 由此得到:1).任一整 数在数列中最多出现一次;2).若整数 u 和 v (u<v) 都出现在数列中,则 u 与 v 之间的所有整数也出现在数列 中.最后由正负项均无穷多个(即数列含有任意大的正整数及任意小的负整数)就得到:每个整数在数列中 出现且只出现一次. 例 14. 偶数个人围着一张圆桌讨论,休息后,他们依不同次序重新围着圆桌坐下,证明至少有两个人,他 们中间的人数在休息前与休息后是相等的。 证明:将座号依顺时针次序记为 1,2,…,2n,每个人休息前后的座号记为(i,j),则 i 与 j 跑遍完全剩余系 mod2n。如果两个人(i1,j1),(i2,j2)休息前后在他们中间的人数不相等,则有 j2-j1≡i2-i1mod2n,即 j2-i2≡ j1-i1(mod2n),因此,j-i 也跑遍完全剩余系 mod2n∴ j-i 的和=

? j ? ?i ≡0(mod2n),而任一完全剩余系

mod2n 的和≡1+2+…+2n-1≡n(2n-1)≡0(mod2n),矛盾!故结论成立。 例 15. 证明:不论 n 和 k 是怎样的正整数,2n3k+4nk+10 不可能是连续正整数之积. 证明:令 p=nk,则 2n3k+4nk+10=2p3+4p+10 是偶数,取 mod3,∵ 3+4p+10=(3p3+3p+9)-(p-1)p(p+1)+1 2p 3 3 ∴ +4p+10≡1(mod3),从而 2p +4p+10 不是 3 个或 3 个以上连续正整数之积,而两个连续正整数之积按 2p mod3 分类: 3m(3m+1)≡0(mod3),(3m+1)(3m+2)≡2(mod3),(3m+3)(3m+2)≡0(mod3)∴ 原式也不是两个正整 数之积.综上知:2n3k+4nk+10 不可能是连续正整数之积. 例 16. 设正整数 a,b 使得 15a+16b 和 16a-15b 都是正整数的平方,求这两个平方数所可能取的最小值 (IMO37-4)。 解:设 15a+16b=x2 和 16a-15b=y2,x,y∈ +,则 15x2+16y2=(13· Z 37)a,16x2-15y2=(13· 37)b,若(37,y)=1,设 2 2 2 2 2 yy1≡1(mod37),则由 15x +16y ≡0(mod37),16x -15y ≡0(mod37),得 15(xy1) ≡-16(mod37),16(xy1)2≡ 15(mod37) ? (xy1)2≡-6(mod37),这是不可能的,因仅有 r2≡0,±1,±3,±4,±7,±9,±10,±12,±16(mod37)∴ x= 2 2 2 2 2 2 2 2 37u,y=37v,0≡15u +16v ≡2u +3v (mod13),0≡16u -15v ≡3u -2v (mod13),若(13,u)=1,设 uu1≡1(mod13), 则 2(vu1)2≡-3(mod13),3(vu1)2≡2(mod13) ? (vu1)2≡5(mod13),这是不可能的,因仅有 r2≡0,±1,±3,±4(mod13) ∴ u=13s,v=13t,x=37· 13s,y=37· 13t,取 s=t=1 得 x2,y2 的最小值为 x2=y2=(13· 2=231361,此时,a= 37) 13· 31,b=13· 37· 37。 练习题 1. 设 a,b,x0∈ *,xn=axn-1+b ,n=1,2, ….证明 x1,x2,…不可能都是质数. N 证明:设 x1=p 是质数,则 p>a,(p,a)=1, x2,x3,…,xp+2 这 p+1 个数中必有两个属于 modp 的同一剩余类, 即有 m>n≥2,使得 xm≡xn(modp),由题意有 xm-xn≡a(xm-1-xn-1)≡0(modp),依次类推,有 xm-n+1-x1≡0(modp),即有 p|xm-n+1,因数列增,所以 xm-n+1>p, xm-n+1 不是质数.
3

2. 确定所有正整数 n,使方程 xn+(2+x)n+(2-x)n=0 有整数解. 解:显然,若 n 为偶数,则方程无实数根,若 n=1,则 x=-4.当 n≥3 且为奇数时∵ 方程左端是首项为 1,常数 n+1 t 项为 2 的多项式∴ 其整解只能是-2 (t 为非负整数)形式:若 t=0,1,2 则 x=-1,-2,-4 都不是方程的根;若 t≥3,则 nt t n t n -2 +(2-2 ) +(2+2 ) =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. 问是否存在一个无限项素数数列 p1,p2,…,pn,…对任意 n 满足|pn+1-2pn|=1?请说明理由. 解:若存在,则由 pn+1=2pn± n 知{pn}递增, p3>3, p3≡1 或 2(mod3).若 p3≡1(mod3),则 p4=2p3-1 即 1>p p4≡1(mod3)∴ 5=2p4-1,…,pn=2pn-1-1∴ n=2n-3p3-2n-3+1,取 n-3=p3-1 则由 2 p p
p3 ?1

≡1(modp3)

知 pn≡0(modp3),矛盾!若 p3≡2(mod3), 则 p4=2p3+1,即 p4≡2(mod3)∴ 5=2p4+1,…,pn=2pn-1+1, p ∴ n=2n-3p3+2n-3-1,取 n-3=p3-1 则由 2 p
p3 ?1

≡1(modp3)知 pn≡0(modp3),矛盾!

3n 3L 3m 4. 设三角形的三边长分别为整数 L,m,n,且 L>m>n.已知 { 4 } ? { 4 } ? { 4 } ,其中{x}表示 x 的小数部 10 10 10
分.求三角形周长的最小值. 解:∵{

3L 3m 3n } ? { 4 } ? { 4 } ∴ L,3m,3n 的末四位数相同,从而 104|3L-3m=3m(3L-m-1),104|3L-m-1∴ 3 L-m 104 10 10
1 2 2 3 3 k 1 2 2

=4k,其中 k∈ *.∵ L-m=81k=(1+80)k=1+ C k 80 ? C k 80 ? C k 80 ? ? ? 80 ∴ 4|3L-m-1 ? 104| C k 80 ? C k 80 ? C k N 3 10
1 2 3 1 2 3 2 3 3 5| 5|k, C k 80 ? C k 802 ? C k 803 ? 125| C k ? C k 80 ? C k 802 =k(40k-39)+ C k 802 ∵ C k 80 ? C k 802 ∴
3 3 125| C k 802 ,∵ 125|k(40k-39)+ C k 802 , ∴ 125|k(40k-39)∵ 40k-39∴ 5? 125? 40k-39∴ 125|k,k=125r, 其中

3

r∈ *.即 L-m=4k=500r,同理 m-n=500s,s∈ *.∵ N N n>L-m=500r≥500∴ 小=501,∵ n m=n+500s≥501+500= 1001,∴ 小=1001,L≥500+1001=1501,所求三角形周长的最小值为 501+1001+1501=3003. m 解法 2:由已知得 3L≡3m≡3n≡(mod104)即 3L≡3m≡3n≡(mod24) ① L≡3m≡3n≡(mod54) ② ,3 ,由① 得 m-n 4 4 4 m-n 4k 4 4k 3 ≡1(mod2 ) ∵ ≡1(mod2 ) ∴ 3 4|m-n,m-n=4k,由② 3 ≡3 ≡1(mod5 ),现求满足此式的 k:∵ -1≡ 得 3 (1+5?24)k-1≡5k?24+

k (k ? 1) 2 8 k (k ? 1)( k ? 2) 3 12 ?5 ?2 + ?5 ?2 ≡0(mod54) ? k=53t,m-n=500t,同理 L-n= 2 6

500r,其中 t,r 为正整数,∵ L>m>n∴ r>t,即三角形三条边为 500r+n, 500t+n 和 n,且有 n>500(r-t)≥500∴ 仅当 t=1,r=2,n=501 时,1000+501+500+501+501=3003. 5. 如果整数 n 不是 2 的倍数,也不是 5 的倍数.证明 n 必能整除一个各位都是 1 的数。
n 个 ?? ?m个? ??? ? ? ? ??? ??1? 证明: 若数 1,11 ,111 , ? ,111 ?1 中有被 n 整除者, 则问题得证; 否则必有 111?1 与 111?1 (m>r)

r个

m 个 r ?m个? ??? ??? ?个 ? ? ?r个 ? ? ??r? ? ? ?m个? ??? ? ? ?r个 ? ? 使得 111?1 ≡ 111 ?1(mod n ) ,即 n | [111 ?1 ? 111 ?1] ? 111 ?10 ? 0 ,因 n 不是 2 和 5 的倍

m 个 ??? ?? r? 数,所以 n | 111 ?1 ,得证。

6. 设 a 是 45687777 的各位数之和, b 是 a 的各位数之和,c 是 b 的各位数之和.求 c. 解:∵ 45687777<100007777=104×7777 共 4×7777+1=31109 位数,∴ a<9×31109=279981,b<2+5×9=47,
4

c<4+9=13,∵ 45687777≡57777≡53×2592+1≡5(-1)2592≡5(mod9),∴ a≡b≡c≡5(mod9) ∴ c=5. 7. 对于给定的正整数 k,用 f1(k)表示 k 的各位数之和的平方,并设 fn+1(k)=f1(fn(k))(n≥1).试求 f2005(22006)的值. 解:注意到 10m≡1(mod9)∴ 正整数 N=an×10n+…+a1×10+a0≡an+…+a1+a0(mod9).设 f1(22006)=a12,则 a1≡22006≡23×668?4≡4(mod9), 设 f2(22006)=f1(a12)=a22,则 a2≡a12≡7(mod9),设 f3(22006)= f1(a22)=a32,则 a3≡a22≡ 4(mod9),,∵ 2006=2006×lg2<700∴1(22006)<(9×700)2<4×107,f2(22006)<(3+9×7)2<4500,f3(22006)<(3+ lg2 f 2 2 2006 3×9) =30 ∵ 3<30∴ 3=4,13,22.,f3(2 )∈ a a {16,169,242}, f3(22006)=16 时, f4(22006)=72=49, f5(22006)=132= 169,f6(22006)=162=256, f7(22006)=132=169,…,f2n(22006)=162=256,f2n+1(22006)=132=169∴2005(22006)=169. f 8. 试求 7
7?
7

(100 个 7)的末四位数.
7?
7

解:∵ 7≡-1(mod4)∴7
4 4k

≡-1(mod4)(98 个 7),设 7
7?
7

7?

7

=4k+3(98 个 7),k∈ ,则 7 Z
+

7?

7

=74k+3(99 个

7)∵ ≡1(mod100)∴ ≡1(mod100), 7 7 7

≡7

4k+3

≡7 ≡43(mod100).又设 7
3

7?

7

=7100m+43(100 个 7),m∈ +. Z

∵ 4≡2401(mod10000)∴ 8≡4801(mod10000), 716≡9601(mod10000),732≡9201(mod10000), 764≡ 7 7 100 8401(mod10000),7 ≡74?732?764≡2401?9201?8401≡1(mod10000),7100m≡1(mod10000),7100m+43≡743≡ 7 ?7 ?7 ≡2343 (mod10000), 7 ∴
3 8 32

7?

7

(100 个 7)≡7

100m+43

≡2343(mod10000), 7

7?

7

(100 个 7)的末四位数

为 2343. 三. 重要定理及应用 1. Euler 定理:设整数 m>1,且(a,m)=1.则有 aφ(m)≡1(modm). 2. Fermat 定理:设 p 是素数,则对任意正整数 a 有 ap≡a(modp). 证明:若 p|a,则显然成立.若(p,a)=1,则 a,2a,…,(p-1)a 对 modp 余数各不相同(若 p|(m-n)a(n<m≤p-1), 则 p|m-n,m=n,矛盾!).所以,a?2a?…?(p-1)a≡1?2?…?(p-1)(modp),即 ap-1?(p-1)!≡(p-1)!(modp),∵ (p,p-1)=1, p ∴ ≡a(modp). a 3. 设(a,m)=1,c 是使得 ac≡1(modm)的最小正整数,则 c|φ(m). 4. Wilson 定理:设 p 是素数,则(p -1)!≡-1(mod p). 5.中国剩余定理:设 K≥2,而 m1,m2,…,mk 是 K 个两两互质的正整数,令 M=m1m2…mk=m1M1=m2Mk=…=

? x ? a1 (modm1 ) ? x ? a (modm ) ? 2 2 mkMk,则下列同余式组:?? 的正整数解是 x≡a1M1M1-1+a2M2M2-1+…+akMkMk-1(modM). ? ? ? x ? a k (modm k ) ?
例 1. (Ⅰ )设 n 为大于 1 的整数,证明 2n-1 不能被 n 整除。 (Ⅱ )试求所有能使 2n+1 被 n2 整除的素数 n。 证明: )若 n 为偶数,则结论成立;若 n 为奇素数,则 2n-1≡1(modn),结论成立;若 n 为奇合数, (Ⅰ 则 n 的质因数(奇素数)都不整除 2n-1,即 n 不整除 2n-1,故结论为真。 (Ⅱ )易知使 2n+1≡0(modn2)的素数 n 为奇数,∴ (2,n)=1,2n≡2(modn)∵ n+1≡0(modn)∴ 2 3≡0(modn) 即 n|3,n=3 显然满足题意。 例 2.

x5 x3 7x ? ? 证明对任意整数 x, 是整数. 5 3 15
,由 Fermat 定理得 x5≡x(mod5),∴ 5+5x3+7x≡3x+7x≡10x≡0(mod5), 3x

3x 5 ? 5 x 3 ? 7 x 证明:即 15

∵ 3≡x(mod3)∴ 5+5x3+7x≡5x+7x≡12x≡0(mod3),∵ x 3x (3,5)=1∴ 5+5x3+7x≡0(mod15),得证. 3x
5

例 3. 设 p 是大于 3 的素数.求证:42p|3p-2p-1. 证明:∵ 42=2×3×7,2|3p-2p-1,3|3p-2p-1,由 Fermat 定理得 3p≡3(modp), 2p≡2(modp),∴ p-2p-1≡ 3 6 6 p p 6k+1 6k+1 0(modp)∵ ≡1(mod7), 2 ≡1(mod7),p>3 是素数,∴ 3 p≡1(mod6)或 p≡5(mod6),∴ -2 -1≡3 -2 -1≡33 p p 6k+5 6k+5 p p p p 2-1≡0(mod7)或 3 -2 -1≡3 -2 -1≡5-4-1≡0(mod7)即 7|3 -2 -1∴ 42p|3 -2 -1. 例 4. 已知 m,n 为正整数,且 m 为奇数,(m,2n-1)=1.证明:m|

?k
k ?1

m

n

.

证明:∵ 1,2,…,m 构成 modm 的完系,(m,2)=1∴ 2,4,…,2m 也构成 modm 的完系∴

? (2k )
k ?1

m

n

? ? k n (modm)
k ?1

m

? (2k ) n ? ? k n (modm) 即 (2 n ? 1)? k n ? 0(modm) ∵(m,2n-1)=1,∴m | ? k n 得证.
k ?1 k ?1 k ?1 k ?1

m

m

m

m

例 5. 求与数列

?a

n

? 2n ? 3n ? 6n ? 1, n ? 1? 中所有项都互质的所有正整数.

解:显然(1,an)=1.设 m>1 是与{an}中所有项都互质的正整数,p 为 m 的一个质因数,若 p>3,则由费马小 定理得: 2
p ?1

? 1? mod p ? , 3p?1 ? 1? mod p ? , 6 p?1 ? 1? mod p ? ,记 2 p?1 ? mp ? 1 , 3 p?1 ? np ? 1
mp ? 1 np ? 1 tp ? 1 ? ? ?1= 2 3 6

p ?2 p ?2 p ?2 3 p?1 ? np ? 1 , 6 p?1 ? tp ? 1 ( m, n, t ? Z ),则 a p ? 2 ? 2 ? 3 ? 6 ? 1 ?

?

3mp ? 2np ? tp 3m ? 2n ? t ? p? ,∵ ap-2 为整数, ( p, 6) ? 1 ,∴ 由 6|3m+2n+t, p a p ? 2 这与(m,ap-2)=1 矛 6 6
盾!若 p=2 或 3,则 a2=48=24?3,p|a2 也矛盾!故与 ?an ? 中所有项都互质的正整数只有 1. 例 6. 求使得 7d≡1(mod2r)(整数 r≥3)的最小正整数 d0. 解:∵ r)=2r(1Φ(2

1 2r ? 2 )=2r-1 及 d0|Φ(2r)∴ 0=2k, 0≤k≤r-1.先证:对任意奇数 a,必有 a d 2
2n?2

? 1(mod2r ) :
r=n+1 由此可

归纳法,设 a=2t+1,当 r=3 时,a2=4t(t+1)+1≡1(mod23),设当 r=n 时, a 时, a
2n?1

? 1(mod2n ) ,则当

? 1 ? (a2

n ?2

? 1)(a2

n ?2

? 1) 可被 2n+1 整除,即有 a2 ? 1(mod2n?1 ) ,故结论成立.
r ?3

n?1

知 d0=2k 中的 k 满足 0≤k≤r-2.我们证明:对任意整数 r≥3,必有 设当 r=n 时,

7 2 ?1(mod2r):归纳法,当 r=3 时,显然成立,

72 ?1(mod2n)∵72

n ?3

n ?3

≡1(mod2n-1) ∴

72

n ?3

=1+s?2n-1,其中整数 2?s,∴
n?2 r ?3

72

n ?2

? (72 )2 ? 1 ? s(1 ?

n?3

7

2n?2

? (7

2n?3 2
j

) ? 1 ? s(1 ? s ? 2n?2 )2n ,2 ? 1+s?2n-2, 即 72 ? 1(mod2n+1)∴ 72 ? 1(mod2r), 由 此 推

2 得: 7 ?1(mod2r),0≤j≤r-3,故 d0=2r-2 为所求.

例 7 求所有的正整数对(p,n)满足:(ⅰ 是素数; (ⅱ )p )n≤2p; (ⅲ p-1|(p-1)n+1. )n 解:显然(p,1)和(2,2)是满足题意的正整数对,下设 n≥2,p≥3.∵ (p-1)n+1 为奇数∴ 为奇数且 n<2p,记 n n n q 为 n 的最小素因子, q|(p-1) +1 即(p-1) ≡-1(modq),且(q,p-1)=1,(n,q-1)=1,存在 u,v∈ 使得 un+v(q-1)=1, 则 Z nu v(q-1) u 由 Fermat 小定理得:p-1≡(p-1) (p-1) ≡(-1) (modq)∵ 为奇数∴ 必为奇数,p-1≡ q u
6

p 1 p?1 p?1 -1(modq),从而 p=q,∵ n<2p=2q 及 q 是 n 的最小素因子∴ n=p=q.∵ (p-1)p+1= p ? Cp p ? ? ? Cp p

∴ p-1|(p-1)p+1 ? p≤3∴ p p=3,满足题意的所有的正整数对为(p,1)、(2,2)、(3,3)其中 p 为任意质数(IMO40). 方法 2:对任意素数 p,数对(p,1)是解;当 p=2 时,仅有数对(2,1)、(2,2)是解;下设 p≥3,n≥2,若 (p,n) 是 解 , 则 n 是 奇 数 , 设 n 的 最 小 素 因 子 是 q , n=qdm(q?m) , 则 (p-1)q≡(p-1)(modq)∴( p ? 1) ∵ q|(p-1)n+1,∴( p ? 1)
qd m

qd

? (p-1)(modq)

? ( p ? 1)n ? ( p ? 1)m ? ?1(modq) ,∵(p-1)2m≡1(modq),∴q|(p-1)2m-1,

∵ (p-1)q-1≡1(modq), q|(p-1)q-1-1∵ 是 n 的最小素因子∴ ∴ q (2m,q-1)=2, p-1 对模 q 的阶为 r,则 r|2m,r|q-1, 设 2 m ∴ r=2∴ q|(p-1) -1=p(p-2),∵ (m,q-1)=1,若 q|p-2,则 q|(p-1) +1=[(p-2)+1]m+1= (p-2)m+…+m(p-2)+2 ? q|2 与 n 是奇数矛盾∴ q|p,必有 q=p,∵ dm=pdm<2p=2q∴ n=q n=q=p,又由(ⅲ pp-1|(p-1)p+1= )得 展开式仅有 4 项∴ n=p=3。故满足条件的所有的正整数对为(p,n)=(p,1)、(2,2)、(3,3)。 例 8. 已知 p 为奇素数.证明:

p ? 1 p-1 p -…+p2 2

?k
k ?1

p ?1

2 p ?1

?

p( p ? 1) (mod p 2 ) . 2

证明:∵ 为偶数∴ p-1

?k
k ?1

p ?1

2 p ?1

1 2 p? ? ? [k 2 p ?1 ? ( p ? k ) 2 p ?1 ] ,∵ 2p-1+(p-k)2p-1= p 2 p?1 ? C2 p?1 p 2 p?2 ? k ? ?? C2 p?12 k

p ?1 2

k ?1

1 2 p? k C2 p?1 p 2 p?2 ? k ? ? ? C2 p?12 p ? k 2 p?2 ,∴ 2p-1+(p-k)2p-1≡ C2 p?1 p ? k

1

2 p?2

≡p(2p-1)k2p-2(modp2),由 Fermat 定理知 kp-1≡

1(modp),∴ (2p-1)k2p-2≡2p-1≡-1(modp)即(2p-1)k2p-2=pm-1,∴ p(2p-1)k2p-2≡p2m-p≡-p(modp2),∴
p ?1 p ?1 2

?k
k ?1

p ?1

2 p ?1

? ? (? p) ?
k ?1

p ?1 2

?k
k ?1

2 p ?1

? ? (? p) ? ?
k ?1

p( p ? 1) p( p ? 1) p( p ? 1) ? p2 ? ? (mod p 2 ) 2 2 2

练习题 1. 求所有的素数对(x,y)满足 xy-yx=xy2-19. 解:∵ y=yx+xy2-19 及 Fermat 定理 xy≡x(mody),∴ y≡x≡-19(mody)∴ x x y|x+19,同理 x|y-19,xy|(x+19)(yy 2 19),即 xy|19(y-x-19)∴ xy|y-x-19.(ⅰ )当 x=2 时,2 =3y -19,由 y|x+19=21 得 y=3,7,检验知(2,3)和(2,7)都是 2 x 解.(ⅱ y=2 时,x =2 +4x-19,且 x|(-17)∴ )当 x=17 检验知(17,2)非解.(ⅲ x≥3 时,当 y≥3 时,由 xy|y-x-19 及 )当 y≤x+19 得:3x≤xy≤x+19-y≤x+16 即 3x≤x+16∴ x≤8,x=3,5,7.此时,由 y|x+19=22,24,26 得 y=11,3,13 不满足 y x 2 x|y-19,非解.∴ 满足 x -y =xy -19 的所有素数对(x,y)=(2,3)和(2,7). 2. 证明:不存在非负整数 k 和 m,使得 k!+48=48(k+1)m. 证明:k=0,m=0 显然不是解.下设 k,m 为正整数.10.若 k+1 为合数,则 k+1|k!, k+1|48∵ 48|k!∴ k≥6, 0 k=7,11,23,47 检验知都不是解.2 .若 k+1 为素数,由 Wilson 定理知 k!≡-1(modk+1),即 k+1|k!+1,∵ k!+48= 48(k+1)m∴ k+1|47,k=46.方程为 46!+48=48?47m 即

46! ? 1 =47m,取 mod4 得 1≡(-1)m(mod4)∴ 为偶数,令 m 48

m=2m1.则有 (47

m1

? 1)(47m1 ? 1) =

46! 46! m m ∵ 2| 23 , 47 1 ? 1 ? 2(mod23) ,∴ 2| 47 1 ? 1 , 23 48 48

7

∵ 47

m1

? (46 ? 1)m1

≡46m1+1(mod232),∴ 2| 23

47m1 ? 1 ? 232|46m1 ? 23|m1∴m=2m1≥46,

故有 46!+48<48?47m.综上所述,不存在非负整数 k 和 m,使得 k!+48=48(k+1)m. 3. 已知 p 是一个大于 5 的素数.求证:至少存在两个不同的正整数 q1,q2 满足:(ⅰ )1≤q1,q2≤p-1; (ⅱ ip-1≡ )q 2 1(modp )(i=1,2). 证明:引理:若 ab?1(modc),则必存在素数 q|a 且 qb≡1(modc).证明原题:由二项式定理可知(p-1)p-1, (p+1)p-1, (2p-1)p-1, (2p+1)p-1 这四个数在 modp2 下的余数均不为 1∴ 存在 q1|p-1 且 q1p-1≡1(modp2).(ⅰ q1≠2, )若 p-1 2 则令 q2=2,易知 q2|p+1,且 q2 ≡1(modp ), q1,q2 即为所求.(ⅱ q1=2,则由 2p-1, 2p+1 中必有一数被 3 整除, )若 p-1 2 可令 q2=3,则必有 q2|2p-1 或 2p+1,且 q2 ≡1(modp )得证. 4. 证明,对于每一个素数 p,总存在无穷多个正整数 n 使得 p|2n-n. 证明: p=2,则 n 取任意偶数,结论成立;若 p>2,则由 Fermat 定理得 2p-1≡1(modp),令 n=(mp-1)(p-1),m 若 为任意正整数,则 n≡1(modp),2n≡1(modp)∴ n-n≡0(modp),即有 p|2n-n.故结论成立. 2 5. 已知 k 为正整数,k≥2, p1,p2,…,pk 为奇素数,且(a,p1p2…pk)=1.证明 a ( p1 ? 1)( p2 ? 1)?( pk ? 1) -1 有不同 于 p1,p2,…,pk 的奇素数因数. 证明:∵ 1p2…pk)=1∴ 1)=1, 由 Fermat 定理得: a (a,p (a,p
p1 ?1

? 1(mod p1 ) ,又
( p1 ?1)( p2 ?1)?( pk ?1) 2

( p 2 ? 1)( p3 ? 1) ? ( p k ? 1) 为正整数,∴a 2
理得

( p1 ?1)( p2 ?1)?( pk ?1) 2

? 1(mod p1 ) 即 p1 | a

? 1 ,同
? 0或1(mod4)

p2 , p3 , ?, pk | a

( p1 ?1)( p2 ?1)?( pk ?1) 2

( p ? 1)( p 2 ? 1) ? ( p k ? 1) ? 1 ,∵ 1 为偶数∴a 2

( p1 ?1)( p2 ?1)?( pk ?1) 2

?1)( p2 ?1)?( pk ?1) 2

? 0或1(mod4) ,且 4? a
因数∴a
( p1 ?1)( p2 ?1)?( pk ?1)

( p1 ?1)( p2 ?1)?( pk ?1) 2

? 1 ,即 a

( p1 ?1)( p2 ?1)?( pk ?1) 2

? 1 有异于 p1,p2,…,pk 的奇素数
? 1] 有异于
p1,p2,…,pk 的奇

? 1 ? [a

( p1 ?1)( p2 ?1)?( pk ?1) 2

? 1][a

( p1 ?1)( p2 ?1)?( pk ?1) 2

素数因数. 6. 已知 p 为素数.证明,存在一个素数 q,使得对任意正整数 n,q?np-p.

p p ?1 p p ?1 ? p p ?1 ? ? ? p 2 ? p ? 1 ? p ? 1(mod p 2 ) ,∴ 证明:∵ 中至少有一个素因子 q 满 p ?1 p ?1
足 q?1(modp2).若存在正整数 n 使得 np≡p(modq),则有 n
p2

? p p ? 1(modq) (∵p|pp-1),由 Fermat 定

理得: nq-1≡1(modq)及 p2? q-1,(p2,q-1)|p(∵ 2,q-1)=1 或 p),∴ p≡1(modq)∵ p≡p(modq)∴ (p n n p≡1(modq) 2 p-1 2 p-1 ∴ 1+p+p +…+p ≡p(modq),∵ 是 1+p+p +…+p 的一个质因子∴ q p≡0(modq)与 p≡1(modq)矛盾! 2 2 2 2 2 7. 设正整数 a,b,c,d,m,n 满足:a+b+c+d=m , a +b +c +d =1989,且其中 a,b,c,d 的最大者为 n2.试求 m,n 的 值. 解:显然,a,b,c,d 不全为偶数(1 奇或 3 奇),从而 m 为奇数.∵ 2=a+b+c+d ? m

4(a 2 ? b 2 ? c 2 ? d 2 ) ? 2 1989

c 2 ? d 2 ) ? 2 1989 <90,∴ 2 只能取{12,32,52,72,92},∵ m (a+b+c+d)2>a2+b2+c2+d2=1989∴ 2> 1989 即 m2≥45∴ 2 m m
=49 或 81.若 m2=49 即 a+b+c+d=49.∵ a,b,c,d 的最大者为 d=n2∴ 4≥a2+b2+c2+d2=1989∴ 4n n≥5,∵ a+b+c= 2 2 2 2 2 2 49-n ∴ 5≤n≤6 即 n=5 或 6,d=25 或 36.a+b+c=24 或 13, a +b +c =1364 或 693,∵ (a+b+c) =24 =576>a2+
8

b2+c2 或(a+b+c)2=132=169>a2+b2+c2 ,∴ 此时方程无解.∴ 2=a+b+c+n2=81, a2+b2+c2+n4=1989,∵ 2≥81 m 4n ∴ n≥5∵ 1989-n4≥3 即 n4≤1992∴ 5≤n≤6 即 n=5 或 6. 当 n=5 时,a+b+c=56,a2+b2+c2 =1364,∵ 4|1364=a2+ b2+c2∴ a,b,c 均为偶数:a=2a1,b=2b1,c=2c1 且 a12+b12+c12 =341, a1+b1+c1=28∵ 12+b12+c12 =341≡1(mod4) a ∴ 1,b1,c1 必定两个偶数一个奇数: a1=2a2,b1=2b2,c1=2k-1 且 2(a2+b2+k)=29 矛盾!当 n=6 时,a+b+c=45,a2+ a 2 b +c2 =693,∵ 693≡1(mod4)∴ a=2a1,b=2b1,c=2k-1 且 a1+b1+k=23,a12+b12+k(k-1) =173,∵ k(k-1) 为 偶 数 2 ∴ 1,b1 一 奇 一 偶 : a1=2a2,b1=2r-1 且 2a2+2r+k=24,4a2 +4r(r-1)+k(k-1) =172∴ a 2|k,4|k(k-1)∴ 4|k, 又 ∵ 173-k(k-1) = a1
2

? b1 ?
2

(a1 ? b1 ) 2 (23 ? k ) 2 ? ,即有 k2-16k+61≤0∴ 7≤k≤9,∵ 4|k∴ k=8,a2+r=8,a22+ 2 2

r(r-1)=29,消去 a2 得 2r2-17r+35=0,解得 r=5,(a,b,c,d)=(12,18,15,36)∴ 2=81,n2=36,(m,n)=(9,6). m x y z w 8. 求方程 2 ?3 -5 ?7 =1 的所有非负整数解(x,y,z,w). 解:(1)若 y=0,则 2x-5z?7w=1,当 z≠0 时, 2x≡1(mod5)∵ 4≡1(mod5)∴ 2 4|x,从而 3|2x-1=5z?7w,这不可能∴ z=0, x w w x w 2 -7 =1,当 x=1,2,3 时,(x,w)=(1,0),(3,1);当 x≥4 时, 7 =2 -1≡-1(mod16),但当 w 为偶数时 7 ≡ 1(mod16),当 w 为奇数时 7w≡7(mod16),矛盾.∴ 这时解为(1,0,0,0),(3,0,0,1);(2)若 y>0.① x=1 时,2?3y当 z w z w z y 4 5 ?7 =1, 则 5 ?7 ≡-1(mod3), 即 (-1) ≡-1(mod3)∴ 为 奇 数 ∴ z 2?3 ≡1(mod5)∵ ≡1(mod5),∴ 3 y≡1(mod4) 即 y 6 y=4m+1.当 w≠0 时, 2?3 ≡1(mod7)∵ ≡1(mod7)∴ 3 y≡4(mod6),y=6n+4=4m+1,即 6n=4m-3 矛盾∴ 必有 w=0, y z z 6 3 z z 2?3 -5 =1,当 y=1 时,z=1;当 y≥2 时,5 ≡-1(mod9)∵ ≡1(mod9)∴ 5 z≡3(mod6),5 +1|5 +1,7|5 +1=2?3y 矛盾! ∴ 这时解为(1,1,1,0),② x≥2 时,∵ z?7w≡-1(mod4),5z?7w≡-1(mod3)即(-1)w≡-1(mod4),(-1)z≡-1(mod3)∴ 都 当 5 w,z x y z w y z w y 是奇数,2 ?3 =5 ?7 +1≡35+1≡4(mod8),∴ x=2,y=2k,方程为 4?3 -5 ?7 =1∴ 4?3 ≡1(mod5),y≡2(mod4), y z w 4?3 ≡1(mod7),y≡2(mod6)∴ y≡2(mod12),设 y=12m+2(m≥0),则 5 ?7 =4?312m+2-1=(2?36m+1-1)(2?36m+1+1)
6 m ?1 ? ?1 ? 5z ?2 ? 3 ∵ 6m+1+1≡0(mod7),(2?36m+1-1,2?36m+1+1)=1∴ 2?3 5|2?36m+1-1,∴? ,若 m≥1,则 5z≡ ?2 ? 3 6 m ?1 ? 1 ? 7 w ?

?2 ? 3 ? 1 ? 5 z ? -1(mod9),由① 的证明知不可能.若 m=0,则 y=2, ? 得 z=w=1,得解(2,2,1,1).故原方程的所有解 ?2 ? 3 ? 1 ? 7 w ?
为:(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)∵ 4≡1(mod5)∴ 2 4|y, 对 方 程 两 边 mod4 得 z x 4r t x t r 2 ≡2(mod4)∴ z=1.设 y=4r,得 5 +1=2 +2?5 即 5 -2?5 =16 -1,两边 mod3 得:(-1)x+(-1)t≡0(mod3)∴ 一奇一 x,t t x t r x t 偶∵ ≡1 或 5(mod8)∴ 5 =2?5 +16 -1,两边 mod8 得: 5 ≡2?5 -1≡1(mod8)∴ 为偶数,t 为奇数.(1)若 t=1,则 5 对 x 5x=16r+9,设 x=2m,则(5m-3)(5m+3)=16r.∵ m-3,5m+3)=(5m-3,6)=2∴ m-3=2,5m+3=24r-1,∴ (5 5 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∵ r-1=(15+1)r=15r+…+ 16
1 Cr2 ?152 + Cr ? 15 ∴ 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).

9


高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题).doc

高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)_学科竞赛_高中教育

高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题).doc

高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题) - 同余的概念与应

高中数学竞赛专题讲座专题训练.doc

高中数学竞赛专题讲座专题训练 - 竞赛试卷 同余的概念与应用 概念与性质 1. 定义: 若整数 a,b 被整数 m(m≥1)除的余数相同,则称 a 同余于 b 模 m,或 ...

高中数学竞赛专题讲座---同余理论及其应用(一).doc

高中数学竞赛专题讲座---同余理论及其应用(一) - 同余理论及其应用 基础知识

高中数学竞赛专题讲座---竞赛中的数论问题.doc

高中数学竞赛专题讲座---竞赛中的数论问题_学科竞赛_高中教育_教育专区。高中...还可以运用抽屉原理,为同余增设一些条件。整除性与大小顺序 k 结合,就可有更多...

高中数学竞赛讲座同余.doc

高中数学竞赛讲座同余_数学_高中教育_教育专区。高中数学竞赛讲座同余【知识点】

高中数学竞赛专题讲座---学会从特殊角度入手解决有关数....doc

高中数学竞赛专题讲座---学会从特殊角度入手解决有关...学会从特殊角度入手解决有关数论的赛题一. 例题选...(4)缩小取值的可能范围:通过讨论整除、互素、同余...

人教版高中数学竞赛讲座:同余式与不定方程.doc

人教版高中数学竞赛讲座:同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程 同余不定方程是数论中古老而富有魅力的内容.考虑...

高中数学竞赛讲义(含答案)_图文.pdf

高中数学竞赛讲义(含答案)_数学_高中教育_教育专区...同余 §28 高斯函数 §29 覆盖 §29 涂色问题 §...例题讲解 一、从简单情况考虑 华罗庚先生曾经指出:...

17初中数学竞赛专题培训(25):同余式.doc

17初中数学竞赛专题培训(25):同余式 - 初中数学竞赛专题培训 数论有它自己的代数,称为同余理论.最先引进同余的概念 与记号的是数学王子高斯. 先看一个游戏:有 ...

高中数学竞赛常用知识汇集.pdf

1这m种情形, 所以, 整数集可以按对模m同余的关系...C2 = 0. 组合部分 1 排列与组合 1. 1 加法...高中数学竞赛专题知识 暂无评价 2页 1下载券 喜欢...

全国高中数学联赛专题讲座.doc

全国高中数学联赛专题讲座 - 第一部分 高中数学联赛考试大纲 一、考试范围 (一)一试 全国高中数学联赛的一试竞赛大纲,完全按照全日制中学《数学教学大纲》中所规定...

高中竞赛专题:同余式与不定方程.doc

高中竞赛专题:同余式与不定方程 数学竞赛数学竞赛隐藏>> 竞赛讲座 03 --同余式与不定方程 同余式与不定方程同余不定方程是数论中古老而富有魅力的内容.考虑...

赣县中学高中数学竞赛数论第6六讲同余(上).doc

赣县中学高中数学竞赛数论第6六讲同余(上)_学科竞赛...竞赛---数论 二、要点分析: 三、例题讲解: n n...高中数学竞赛专题讲座--... 5页 1下载券 赣县...

高中数学竞赛知识点.doc

高中数学竞赛知识点_学科竞赛_高中教育_教育专区。...中国剩余定理给出了以下的一元线性同余方程组: 有...那么 n 个抽屉至多放进 mn 个物体, 与题设不符...

竞赛专题--同余.doc

竞赛专题--同余_学科竞赛_高中教育_教育专区。第5讲 同余 【知识点】 1.设

高中数学竞赛讲义整数问题.doc

高中数学竞赛讲义整数问题_数学_高中教育_教育专区。...竞赛试卷 6.同余:设 m≠0,若 m|(a-b),即 a...二、方法与例题 1.奇偶分析法。 例1 4|n。 有...

高中数学竞赛专题讲座---竞赛中的数论问题.doc

高中数学竞赛专题讲座---竞赛中的数论问题_学科竞赛_高中教育_教育专区。竞赛中...还可以运用抽屉原理,为同余增设一些条件。整除性与大小顺序结合,就 ?k ? 可有...

高中数学竞赛辅导的几点体会.pdf

一种是平时布置练习, 集中进行讲评, 且大部分内 容...同余式; 与 B 1B 2 …B 9. 由抽屉原理, 知...高中数学竞赛辅导讲座-数... 8页 5下载券 高中...

同余练习.doc

同余练习_学科竞赛_小学教育_教育专区。第8讲 同 ...把题意用数学表达式表示:2836÷χ=??□□ 4582÷...第二部分:补充练习一、什么是“同余”? 整数 a、...