下载文档原格式
初等数论练习题一一、填空题1、τ(2420)=27；ϕ(2420)=_880_2、设a ，n 是大于1的整数，若a n -1是质数，则a=_2.3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1，0，1，2，3，4}.4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。
5、不定方程18x-23y=100的通解是x=900+23t ，y=700+18t t ∈Z 。
.6、分母是正整数m 的既约真分数的个数为_ϕ(m )_。
78、⎪⎭⎫ ⎝⎛10365 =-1。
9、若p 是素数，则同余方程x p - 1≡1(mod p )的解数为二、计算题1、解同余方程：3x 2+11x -20≡0 (mod 105)。
解：因105 = 3⋅5⋅7，同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3)，同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0，3 (mod 5)，同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2，6 (mod 7)，故原同余方程有4解。
作同余方程组：x ≡b 1 (mod 3)，x ≡b 2 (mod 5)，x ≡b 3 (mod 7)，其中b 1 = 1，b 2 = 0，3，b 3 = 2，6，由子定理得原同余方程的解为x ≡13，55，58，100 (mod 105)。
2、判断同余方程x 2≡42(mod 107)是否有解？11074217271071107713231071107311072107710731072107732107422110721721107213)(=∴-=-=-==-=-=-==⨯⨯≡-•--•-）（）（）（）（），（）（）（）（），（）（））（）（（）（解： 故同余方程x 2≡42(mod 107)有解。
3、求（127156+34）28除以111的最小非负余数。
解：易知1271≡50（mod 111）。
2020全国高中数学联赛《初等数论》专题真题汇编1、记集合},4,3,2,1,|7777{},6,5,4,3,2,1,0{4433221=∈+++==i T a a a a a M T i 将M 中的元素按从大到小的顺序排列，则第2005个数是（ ）A ．43273767575+++ B ．43272767575+++ C ．43274707171+++ D ．43273707171+++ 【答案】C2、数码1232006,,,,a a a a L 中有奇数个9的2007位十进制数12320062a a a a L 的个数为（ ）A ．200620061(108)2+B ．200620061(108)2-C ．20062006108+ D ．20062006108- 【答案】B3、方程组0,0,0x y z xyz z xy yz xz y ++=⎧⎪+=⎨⎪+++=⎩的有理数解(,,)x y z 的个数为 （ ）。
（A ） 1 （B ） 2 （C ） 3 （D ） 4【答案】B4、设p 是给定的奇质数，正整数k 使得k 2－pk 也是一个正整数，则k=【答案】14(p +1)2 【解析】设k 2－pk=n ，则(k －p 2)2－n 2=p 24，⇒(2k －p +2n )(2k －p －2n )=p 2，⇒k=14(p +1)2．5、如果自然数a 的各位数字之和等于7，那么称a 为“吉祥数”.将所有“吉祥数”从小到大排成一列,,,,321Λa a a 若,2005=n a 则=n a 5 .∵2005是第1+7+28+28+1＝65个“吉祥数”，即.200565=a 从而.3255,65==n n又,210)5(,84)4(61069====C P C P 而∑==51.330)(k k P∴从大到小最后六个五位“吉祥数”依次是：70000，61000,60100,60010,60001,52000.∴第325个“吉祥数”是52000，即.520005=n a6、方程20062420042005(1)(1)2006x x x x x +++++=L 的实数解的个数为 .【答案】17、方程2010=++z y x 满足z y x ≤≤的正整数解（x ,y ,z ）的个数是 . 【答案】336675从而满足z y x ≤≤的正整数解的个数为33667533567110031=++.8、已知=n a C ())95,,2,1(2162003200Λ=⎪⎪⎭⎫⎝⎛⋅⋅-n nnn ，则数列}{n a 中整数项的个数为 ．【答案】159、已知他们中的任意两人至多通电话一次，他们中的任意n －2个人之间通电话的次数相等，都是3 k 次，其中k 是自然数，求n 的所有可能值． 【解析】显然n ≥5. 记n 个人为A 1，A 2， A N ，设A 1通话的次数为m 1, A i 与 A j 之间通话的数为y ij , l ≤n j i ≤, .则m i +m j – y i . j =∑=ns s m 121-k 3= c . （*）其中c 是常数 ，l ≤n j i ≤, . 根据（*）知，=-j i m m )()(s j s i m m m m +-+=sj s i y y ..-≤1 , l ≤n j i ≤, .⇒1≤-j i m m , l ≤n j i ≤,设 m i =max{m s ,1.n s ≤≤} ,m j = min{m s,1≤s ≤n.} , 则 m i +m j ≤1.若 m i +m j =1 ,则对于任意 s ,,j i ≠ 1≤s ≤n ,都有(m i +m s -y I ,s )- (m j +m s -y I ,s )=1-(y I ,s – y j ,s )=0 , 即 y I ,s – y j ,s = 1 故 y I ,s =1 , y j ,s = 0 . s ,,j i ≠ 1≤s ≤n ,因此 m i ≥ n -2 , m j ≥1 . 于是 ，m i +m j ≥n -3≥2 . 出现矛盾 ，故 m i +m j =0 ，即 m s (1≤s ≤n)恒为常数 。
《初等数论》习题集及答案《初等数论》习题集第1章第 1 节1. 证明定理1。
2. 证明：若m - p ∣mn + pq ，则m - p ∣mq + np 。
3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。
4. 设p 是n 的最小素约数，n = pn 1，n 1 > 1，证明：若p >3n ，则n 1是素数。
5. 证明：存在无穷多个自然数n ，使得n 不能表示为a 2 + p （a > 0是整数，p 为素数）的形式。
第 2 节1. 证明：12∣n 4 + 2n 3 + 11n 2 + 10n ，n ∈Z 。
2. 设3∣a 2 + b 2，证明：3∣a 且3∣b 。
3. 设n ，k 是正整数，证明：n k 与n k + 4的个位数字相同。
4. 证明：对于任何整数n ，m ，等式n 2 + (n + 1)2 = m 2 + 2不可能成立。
5. 设a 是自然数，问a 4 - 3a 2 + 9是素数还是合数？6. 证明：对于任意给定的n 个整数，必可以从中找出若干个作和，使得这个和能被n 整除。
第 3 节1. 证明定理1中的结论(ⅰ)—(ⅳ)。
2. 证明定理2的推论1, 推论2和推论3。
3. 证明定理4的推论1和推论3。
4. 设x ，y ∈Z ，17∣2x + 3y ，证明：17∣9x + 5y 。
5. 设a ，b ，c ∈N ，c 无平方因子，a 2∣b 2c ，证明：a ∣b 。
6. 设n 是正整数，求1223212C ,,C ,C -n n n n 的最大公约数。
第 4 节1. 证明定理1。
2. 证明定理3的推论。
3. 设a ，b 是正整数，证明：(a + b )[a , b ] = a [b , a + b ]。
4. 求正整数a ，b ，使得a + b = 120，(a , b ) = 24，[a , b ] = 144。
5. 设a ，b ，c 是正整数，证明：),)(,)(,(),,(],][,][,[],,[22a c c b b a c b a a c c b b a c b a =。
初等数论试题及答案高一一、选择题（每题3分，共30分）1. 以下哪个数是质数？A. 2B. 4C. 6D. 8答案：A2. 一个数的因数包括它自己吗？A. 是B. 否答案：A3. 一个数的倍数包括它自己吗？A. 是B. 否答案：A4. 两个连续整数的乘积一定是合数吗？A. 是B. 否答案：B5. 一个数的最小倍数是多少？A. 它自己B. 2C. 1D. 0答案：A6. 一个数的最大因数是多少？A. 它自己B. 2C. 1D. 0答案：A7. 以下哪个数是完全数？A. 6B. 28C. 496D. 8128答案：A8. 一个数的质因数分解中，质因数的个数至少有几个？A. 1B. 2C. 3D. 0答案：A9. 以下哪个数是素数？A. 1B. 2C. 9D. 10答案：B10. 一个数的因数个数是奇数还是偶数？A. 奇数B. 偶数答案：B二、填空题（每题4分，共20分）1. 一个数的最小质因数是______。
答案：22. 一个数的最小非零因数是______。
答案：13. 一个数的最大因数是______。
答案：它自己4. 一个数的最小倍数是______。
答案：它自己5. 一个数的倍数个数是______。
答案：无限三、解答题（每题10分，共50分）1. 证明：对于任意的正整数n，2n总是偶数。
证明：假设n为任意正整数，那么2n = 2 * n。
因为2是偶数，所以2n也是偶数。
2. 证明：对于任意的正整数n，n^2 - 1是奇数。
证明：假设n为任意正整数，那么n^2 - 1 = (n - 1)(n + 1)。
因为n - 1和n + 1是连续的整数，所以它们中必有一个偶数和一个奇数。
因此，它们的乘积是奇数。
3. 找出100以内的所有质数。
答案：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 974. 证明：如果p是质数，那么p^2 - 1是合数。
备战2021年高中数学联赛之历年真题汇编（1981-2020）专题29初等数论历年联赛真题汇编1．【2020高中数学联赛B卷（第02试）】设a,b为不超过12的正整数,满足:存在常数C,使得a n+b n+9≡C( mod13)对任意正整数n成立.求所有满足条件的有序数对(a,b).【答案】(1,1),(4,4),(10,10),(12,12)【解析】解法1:由条件知,对任意正整数n,有a n+b n+9≡a n+3+b n+12(mod13). ①注意到13为素数,a,b均与13互素,由费马小定理知a2≡b2≡1(mod13).因此在①中取n=12,化简得1+b9≡a3+1(mod13),故b9≡a3(mod13).代入①,得a n+a3b n≡a n+3+b n+12≡a n+3+b n(mod13),即(a n−b n)(1−a3)≡0(mod13). ②分两种情况讨论.(ⅰ)若a3≡1(mod13),则b3≡a3b3≡b12≡1(mod13),又a,b∈{1,2,⋯,12},经检验可知a,b∈{1,3,9}.此时a n+b n+9≡a n+b n(mod13).由条件知a+b≡a3+b3≡2(mod13),从而只能是a=b=1.经检验,当(a,b)=(1,1)时,对任意正整数n, a n+b n+9模13余2为常数,满足条件.(ⅱ)若a3≡1(mod13),则由②知,对任意正整数n,有a n≡b n(mod13).特别地, a≡b(mod13),故a=b.所以a3≡b9=a9(mod13),即a3(a3−1)(a3+1)≡0(mod13),故a3≡−1(mod13).通过检验a≡±1,±2,⋯,±6(mod13),可知a=4,10,12.经检验,当(a,b)=(4,4),(10,10), (12,12)时,对任意正整数n,有a n+b n+9=a n+a n+9=a n(1+(a3)3)≡0(mod13),满足条件.综上,所求的有序数对(a,b)为(1,1),(4,4),(10,10),(12,12).解法2:由条件知,对任意正整数n,有(a n+b n+9)(a n+2+b n+11)≡(a n+1+b n+10)2(mod13),化简得a n b n+11+a n+2b n+9≡2a n+1+b n+10(mod13),即a n b n+9(a−b)2≡0(mod13).由于13为素数, a,b∈{1,2,⋯,12},故13|(a−b)2,进而a=b.因此,当n变化时, a n+b n+9=a n(1+a9)模13的余数为常数.当1+a9≡(mod13)时,由上式知, a n模13的余数为常数,特别地,有a2≡a(mod13),故a=1.当1+a9≡0(mod13)时,由费马小定理得a2≡1(mod13),故a3≡a3⋅(−a9)≡−a12≡−1(mod13).通过检验a≡±1,±2,⋯,±6(mod13),可知a=4,10,12.综上,所求的有序数对(a,b)为(1,1),(4,4),(10,10),(12,12).2．【2019高中数学联赛A卷（第02试）】设m为整数，|m|⩾2.整数数列a1,a2,⋯满足:a1,a2不全为零，且对任意正整数n，均有a n+2=a n+1−ma n.证明:若存在整数r、s(r>s≥2)使得a r=a s=a1，则r−s⩾m.【答案】证明见解析【解析】不妨设a1,a2互素(否则，若(a1,a2)=d>1，则a1d 与a2d互素，并且用a1d,a2d,a3d,…代替a1,a2,a3,⋯条件与结论均不改变).由数列递推关系知a2≡a3≡a4≡⋯( mod |m|)①以下证明:对任意整数n≥3，有a n≡a2−(a1+(n−3)a2)m( mod m2)②事实上，当n=3时②显然成立.假设n=k时②成立(其中k为某个大于2的整数)，注意到①，有ma k−1≡ma2( mod m2)，结合归纳假设知a k+1=a k−ma k−1≡a2−(a1+(k−3)a2)m−ma2≡a2−(a1+(k−2)a2)( mod m2)，即n=k+1时②也成立.因此②对任意整数n≥3均成立.注意，当a1=a2时，②对n=2也成立.设整数r、s(r>s≥2)，满足a r=a s=a1.若a1=a2，由②对n≥2均成立，可知a2−(a1+(r−3)a2)m≡a r=a3=a2−(a1+(s−3)a2)m( mod m2)，即a1+(r−3)a2≡a1+(s−3)a2( mod |m|)，即(r−s)a2≡0( mod |m|)③若a1≠a2，则a r=a s=a1≠a2，故r>s≥3.此时由于②对n≥3均成立，故类似可知③仍成立.我们证明a2，m互素事实上，假如a2与m存在一个公共素因子p，则由①得p为a2,a3,a4,⋯的公因子，而a1,a2互素，故p∤a1，这与a r=a s=a1矛盾.因此，由③得r−s≡0( mod |m|).又r>s，所以r−s⩾|m|.3．【2019高中数学联赛B卷（第02试）】求满足以下条件的所有正整数n:(1)n至少有4个正因数；(2)若d1<d2<⋯<d k是n的所有正因数，d2−d1,d3−d2,⋯，d k−d k−1构成等比数列.【答案】答案见解析【解析】由条件可知k≥4，且d3−d2d2−d1=d k−d k−1d k−1−d k−2.易知d1=1,d k=n,d k−1=nd2,d k−2=nd3，代入上式得d3−d2d2−1=n−nd2nd2−nd3，化简得(d3−d2)2=(d2−1)2d3.由此可知d3是完全平方数.由于d2=p是n的最小素因子，d3是平方数，故只能d3=p2.从而序列d2−d1,d3−d2,⋯,d k−d k−1 , p−1,p2−p,p3−p2，⋯,p k−1−p k−2，即d1,d2,d3,⋯,d k为1,p,p2,⋯,p k−1，而此时相应的n为p k−1.综上可知，满足条件的n为所有形如p a的数，其中p是素数，整数a≥3.4．【2018高中数学联赛B卷（第02试）】给定整数a≥2.证明:对任意正整数n，存在正整数k，使得连续n个数a k+1,a k+2,⋯,a k+n均是合数.【答案】证明见解析【解析】设i1<i2<⋯<i r是1，2，…，n中与a互素的全体整数，则对1≤i≤n，i∉{i1,i2,⋯,i r}，无论正整数k如何取值，a k+i均与a不互素且大于a，故a k+i为合数.对任意j=1，2，…，r，因a+i j>1，故a+i j有素因子p j.我们有(p j,a)=1(否则，因p j是素数，故p j|a，但p j|a+i j，从而p j|i j，故a,i j不互素，与i j的取法矛盾).因此，由费马小定理知，a p j−1≡1( mod p j).现取k=(p1−1)(p2−1)⋯(p r−1)+1.对任意j=1，2，…，r，注意到k≡1( mod p j−1)，故有a k+i j≡a+i j≡0( mod p j).又a k+i j>a+i j⩾p j，故a k+i j为合数.综上所述，当k=(p1−1)(p2−1)⋯(p r−1)+1时，a k+1,a k+2,⋯，a k+n均是合数.5．【2017高中数学联赛A卷（第02试）】设m、n均是大于1的整数，m≥n.a1,a2,⋯,a n是n个不超过m的互不相同的正整数，且a1,a2,⋯,a n互质.证明:对任意实数x，均存在一个i(1≤i≤n)，使得‖a i x‖⩾2m(m+1)‖x‖，这里‖y ‖表示实数y到与它最近的整数的距离.【答案】证明见解析【解析】4首先证明以下两个结论结论1存在整数c 1,c 2,⋯,c n ，满足c 1a 1+c 2a 2+⋯+c n a n =1， 并且|c i |⩽m,1⩽i ⩽n .由于(a 1,a 2,⋯,a n )=1，由裴蜀定理，存在整数c 1,c 2,⋯,c n ， 满足c 1a 1+c 2a 2+⋯+c n a n =1①下面证明，通过调整，存在一组c 1,c 2,⋯,c n 满足①，且绝对值均不超过m . 记S 1(c 1,c 2,⋯,c n )=∑c i c i >m ⩾0，S 2(c 1,c 2,⋯,c n )=∑|c j |ϵj <¬m⩾0.如果S 1>0，那么存在c i >m >1，于是c i a i >1，又因为a 1,a 2,⋯,a n 均为正数，故由①可知存在c j <0.令c i ′=c i −a j ,c j ′=c j +a i ,c k ′=c k (1⩽k ⩽n,k ≠i,j)， 则c 1′a 1+c 2′a 2+⋯+c n ′a n =1②并且0⩽m −a j ⩽c i ′<c i ,c j <c j ′<a i ⩽m .因为c i ′<c i ，且c j ′<m ，所以S 1(c 1′,c 2′,⋯,c n ′)<S 1(c 1,c 2,⋯,c n ). 又c j ′>c j 及c i ′>0，故S 2(c 1′,c 2′,⋯,c n ′)⩽S 2(c 1,c 2,⋯,c n ).如果S 2>0，那么存在c j <−m ，因此有一个c i >0.令c i ′=c i −a j ,c j ′=c j +a i ,c k ′=c k (1⩽k ⩽n,k ≠i,j)，那么②成立，并且−m <c i ′<c i ,c j <c j ′<0.与上面类似地可知S 1(c 1′,c 2′,⋯,c n ′)⩽S 1(c 1,c 2,⋯,c n )， 且S 2(c 1′,c 2′,⋯,c n ′)<S 2(c 1,c 2,⋯,c n ).因为S 1与S 2均是非负整数，故通过有限次上述的调整，可得到一组c 1,c 2,⋯,c n ，使得①成立，并且S 1=S 2=0.结论1获证.结论2(1)对任意实数a 、b ，均有‖a +b‖⩽‖a‖+‖b‖. (2)任意整数u 和实数y 有‖uy‖⩽|u|⋅‖y‖.由于对任意整数u 和实数x ，有‖x +u‖=‖x‖，故不妨设a ，b ∈[−12,12]，此时‖a‖=|a|,‖b‖=|b|.若ab ≤0，不妨设a ≤0≤b ，则a +b ∈[−12,12]，从而‖a +b‖=|a +b|⩽|a|+|b|=‖a‖+‖b‖.若ab >0，即a 、b 同号.当|a|+|b|⩽12时，有a +b ∈[−12,12]，此时‖a +b‖=|a +b|=|a|+|b|=‖a‖+‖b‖. 当|a|+|b|>12时，注意总有‖a +b‖⩽12，故‖a +b‖⩽12<|a|+|b|=‖a‖+‖b‖.故(1)得证.由(1)及‖−y‖=‖y‖即知(2)成立.回到原问题，由结论1，存在整数c 1,c 2,⋯,c n ，使得c 1a 1+c 2a 2+⋯+c n a n =1， 并且|c i |⩽m,1⩽i ⩽n . 于是∑c i n i=1a i x =x .利用结论2得‖x‖=‖∑c i n i=1a i x ‖⩽∑|c i |n i=1⋅‖a i x ‖⩽m ∑‖a i x ‖n i=1.因此max 1⩽i⩽n ‖a i x ‖⩾1mn‖x‖ ③若n ⩽12(m +1)，由③可知max 1⩽i⩽n ‖a i x ‖⩾‖x‖mn⩾2‖x‖m(m+1).若n >12(m +1)，则在a 1,a 2,⋯,a n 中存在两个相邻正整数. 不妨设a 1,a 2相邻，则‖x‖=‖a 2x −a 1x ‖⩽‖a 2x ‖+‖a 1x ‖. 故‖a 2x ‖与‖a 1x ‖中有一个⩾‖x‖2⩾2‖x‖m(m+1).综上所述，总存在一个i (1≤i ≤n )，满足‖a i x ‖⩾2m(m+1)‖x‖.6．【2015高中数学联赛（第02试）】求具有下述性质的所有正整数k ：对任意正整数n ，2(k−1)n+1|(kn )!n!不成立.【答案】答案见解析【解析】以v (n )表示n !中2的幂次，以S (n )表示n 的二进制表示中1的个数. 有结论v(n)=n −S(n).原题等价于v(n)+k(n −1)⩾v(kn)恒成立，等价于S(kn)⩾S(n)恒成立. 显然S(k)⩾1.当S (k )=1，即k 为2的方幂时，有S(kn)⩾S(n)，符合题意. 下面用构造法证明：使S (k )≥2的k 均不符合题意. 若S (k )≥2，则k 的二进制表示中至少有两个1.用如下方式构造序列n i ，使得存在l ∈N ，使S (kn l )<s (n l )，则这样的k 不符合条件. 以下讨论均在二进制下.先取n 1=1,n 2=2a +1，使得2a k 中的最后一个1与k 中倒数第二个1对齐(如k =1001时，a =3). 当n t 取定时，考虑此时的kn t ：取n t+1=n t +2b ，使得2b k 中的最后一个1与kn t 中倒数第二个1对齐(如k =1001时，{n i }为1，9，25，…).这样构造出了一个数列{n i }，并且易知该数列有无穷多项.考虑其中一项n j .由构造方式有S(n j )=j . 设n j =∑2a i ji=1 (a 1>a 2>⋯>a j =0), 由构造的方式，知kn j 的最后a 1+1位只有一个1. 设2m ⩽k <2m+1，则2a 1+m ⩽kn j <2a 1+m+2，这样，kn j 的二进制表示中至多有a 1+m +1位，至多有m +1个1. 取j >m +1，有故使S (kn j )≥2的k 均不满足题设. 综上，所求的k 为一切2的方幂.7．【2014高中数学联赛（第02试）】设整数x 1,x 2,⋯,x 2014模2014互不同余，整数y 1,y 2,⋯,y 2014模2014也互不同余.证明：可将y 1,y 2,⋯,y 2014重新排列为z 1,z 2,⋯,z 2014，使得x 1+z 1,x 2+z 2,⋯,x 2014+z 2014模4028互不同余.【答案】证明见解析【解析】记k =1007.不妨设x i ≡y i ≡i( mod 2k) (1⩽i ⩽2k)，对每个整数i ，1≤i ≤k ，若x i +y i ≡x i+k +y i+k ( mod 4k)，则令z i =y i ,z i+k =y i+k ，否则，令z i =y i+k ,z i+k =y i ，如果是前一种情形，则x i +z i =x i +y i ≡x i+k +y i+k =x i+k +z i+k ( mod 4k)， 如果是后一种情形，则也有x i +z i =x i +y i+k ≡x i+k +y i =x i+k +z i+k ( mod 4k) 若不然，我们有x i +y i ≡x i+k +y i+k ( mod 4k)，x i +y i+k ≡x i+k +y i ( mod 4k)， 两式相加得2x i ≡2x i+k ( mod 4k)，于是x i ≡x i+k ( mod 2k).但x 1,x 2,⋯,x 2014模2014(2014=2k )互不同余，特别地x i ≡x i+k ( mod 2k)，矛盾. 由上述构造方法知z 1,z 2,⋯,z 2k 是y 1,y 2,⋯,y 2k 的排列.记w i =x i +z i ,i =1,2,⋯,2k .下面验证ω1,ω2,⋯,ω2k 模4k 互不同余，这只需证明，对任意整数i,j,1⩽i <j ⩽k ,w i ,w j ,w i+k ,w j+k 模4k 两两不同余.注意，前面的构造方式已保证w i ≡w i+k ( mod 4k),w j ≡w j+k ( mod 4k)①情形一：z i =y i 且z j =y j ，则由前面的构造方式可知w i ≡w i+k ≡2i( mod 2k)，w j ≡w j+k ≡2j( mod 2k)， 由于2i ≡2j( mod 2k)，故易知w i 与W j 及w i+k 模2k 不同余，w i+k 与W j 及w j+k 模2k 不同余，从而模4k 更不同余，再结合式①，可见结论得证.情形二：z i =y i+k ，且z j =y j+k ，则由前面的构造方式可知： w i ≡w i+k ≡2i +k( mod 2k)，w j ≡w j+k ≡2j +k( mod 2k).同样有w i 与w j 及w j+k 模2k 不同余，w i+k 与w j 及w j+k 模2k 不同余，与情形一相同地可知结论得证.情形三：z i=y i，且z j=y j+k（z i=y i+k，且z j=y j的情形与此相同)，则由前面的构造方式可知w i≡w i+k≡2i( mod 2k)，w j≡w j+k≡2j+k( mod 2k).由于k是奇数，故2i≡2j+k( mod 2)，更有2i≡2j+k( mod 2k).因此仍然有w i与w j及w j+k模2k不同余，w i+k与w j及w j+k模2k不同余.从而结论得证.因此本题得证.8．【2013高中数学联赛（第02试）】设n，k为大于1的整数，n<2k.证明：存在2k个不被n整除的整数，若将它们任意分成两组，则总有一组有若干个数的和被n整除.【答案】证明见解析【解析】先考虑n为2的幂的情形设n=2r,r⩾1，则r<k.取3个2r−1及2k－3个1，显然这些数均不被n整除.将这2k个数任意分成两组，则总有一组中含2个2r−1，它们的和为2r，被n整除.现在设n不是2的幂，取2k个数为−1,−1,−2,−22,⋯,−2k−2,1,2,22,⋯,2k−1，因为n不是2的幂，故上述2k个数均不被n整除.若可将这些数分成两组，使得每一组中任意若干个数的和均不能被n整除.不妨设1在第一组，由于(−1)+1=0被n整除，故两个－1必须在第二组；因(−1)+(−1)+2=0被n整除，故2在第一组，进而推出－2在第二组.现归纳假设1,2,⋯,2l均在第一组，而－1，－1，－2，…，－2l均在第二组，这里1⩽l<k−2，由于(−1)+(−1)+(−2)+⋯+(−2t)+2t+1=0被n整除，故2l+1在第一组，从而−2l+1在第二组.故由数学归纳法可知，1,2,22,⋯,2k−2在第一组，－1，－1，－2，－22，…，－2k－2在第二组.最后，由于(−1)+(−1)+(−2)+⋯+(−2k−2)+2k−1=0被n整除，故2k−1在第一组.因此1,2,22,⋯,2k−1均在第一组，由正整数的二进制表示可知，每一个不超过2k−1的正整数均可表示为1,2,22,⋯,2k−1中若干个数的和，特别地，因为n⩽2k−1，故第一组中有若干个数的和为n，当然被n整除，矛盾.因此，将前述2k个整数任意分成两组，则总有一组中有若干个数之和被n整除.9．【2009高中数学联赛（第02试）】设k，l是给定的两个正整数.证明：有无穷多个正整数m≥k，使得C m k与l互素.【答案】证明见解析【解析】证法一对任意正整数t，令m=k+t⋅l⋅(k!)，我们证明(C m k,l)=1.设p是l的任一素因子，只要证明：p|C m k.若p|k!，则由k!C m k=∏(m −k +i)k i=1≡∏[(i +tl (k!))]ki=1≡∏k i=1i ≡k!( mod p)，即p 不整除上式，故p|C m k . 若p|k !，设a ≥1使p α|k!， 但p α+1|k!，则p α+1|l(k!).故由k!C m k =∏(m −k +i)ki=1≡∏[(i +tl (k!))]ki=1≡∏k i=1i ≡k!( mod p α+1)，及p α|k!且p α+1|k!知p α|k!C m k 且p α+1|k!C m k ， 从而p|C m k .证法二对任意正整数t ，令m =k +t ⋅l ⋅(k!)2，我们证明(C m k ,l )=1. 设p 是l 的任一素因子，只要证明：p|C m k .若p|k!，则由k!C m k =∏(m −k +i)ki=1≡∏[i +tl(k!)2]ki=1≡∏k i=1i ≡k!( mod p)，即p 不整除上式，故p|C m k ，若p|k !，设α⩾1使p α|k!，但p α+1|k!，则p α+1|(k!)2.故由k!C m k =∏(m −k +i)k−1i=1≡∏[i +tl(k!)2]ki=1≡∏k i=1i ≡k!( mod p α+1)及p α|k!且p α+1|k!知p α|k!C m k 且p α+1|k!C m k ，从而p|C m k .10．【2007高中数学联赛（第02试）】设集合P ={1，2，3，4，5}.对任意k ∈P 和正整数m ，记f (m,k )=∑[m√k+1i+1]5i=1，其中[a ]表示不大于a 的最大整数.求证：对任意正整数n ，存在k ∈P 和正整数m ，使得f(m,k)=n . 【答案】证明见解析【解析】定义集合A ={m √k +1|m ∈N ∗,k ∈P}，其中N *为正整数集. 由于当任意k ，i ∈P 且k ≠i √k+1是无理数，所以对任意的k 1,k 2∈P 和正整数m 1,m 2，有m 1√k 1+1=m 2√k 2+1， 当且仅当m 1=m 2,k 1=k 2，这表明A 中无重复元素.注意到A 是一个无穷集，现将A 中的元素按从小到大的顺序排成一个无穷数列.对于任意的正整数n ，设此数列中第n 项为m √k +1.下面确定n 与m ，k 间的关系. 若m i √i +1⩽m √k +1，则m i ⩽√k+1√i+1，由m i是正整数知，对i=1，2，3，4，5，满足这个条件的m i的个数为√k+1√i+1]，从而n=∑√k+1√i+1]5i=1=f(m,k),因此对任意n∈N∗，存在m∈N∗,k∈P，使得f(m,k)=n.11．【2004高中数学联赛（第02试）】对于整数n≥4，求出最小的整数f(n)，使得对于任意正整数m，集合{m，m+1，m+2，…，m+n－1}的任何一个f(n)元子集中，均有至少3个两两互素的元素.【答案】证明见解析【解析】当n⩾4时，对集合M={m,m+1,m+2,⋯,m+n−1}，若2|m，则m+1，m+2，m+3两两互素.若2不能整除m，则m，m+1，m+2两两互素.所以M的所有n元子集中，均有至少3个两两互素的元素，即f(n)存在且f(n)≤0.设T n={t|t≤n+1且2|t或3|t}可知T n是{2，3，…n+1}的子集，但T n中任3个元素均不能两两互素，所以f(n)⩾|T n|+1，由容斥原理知|T n|=[n+12]+[n+13]−[n+16]，从而必有f(n)⩾[n+12]+[n+13]−[n+16]+1①所以f(4)⩾4,f(5)⩾5,f(6)⩾5，f(7)⩾6,f(8)⩾7,f(9)⩾8，我们将证明f(6)=5，设x1,x2,x3,x4,x5是{m，m+1，m+2，…，m+5}中的5个数，若这5个数中有3个奇数，则它们两两互素，若这5个数中有两个奇数，则必有3个偶数，不妨设x1,x2,x3为偶数，x4,x5为奇数.当1≤i<j≤3时，|x i−x j|∈{2,4}，所以x1,x2,x3中至多1个被3整除，至多1个被5整除，从而至少有1个既不被3整除也不被5整除.不妨设其为x3，有x3,x4,x5两两互素.说明这个数中有3个两两互素，即f(6)=5.又因为{m,m+1,m+2,⋯,m+n}={m,m+1,m+2,⋯,m+n−1}∪{m+n}，可知f(n+1)⩽f(n)+1，因为f(6)=5，所以f(4)=4,f(5)=5,f(7)=6,f(8)=7,f(9)=8.所以当4⩽n⩽9时f(n)=[n+12]+[n+13]+[n+16]+1②接下来用归纳法证明对所有n都有式②成立：假设n≤k(k≤9)时，式②成立.当n=k+1时，由于{m,m+1,m+2,⋯,m+k}={m,m+1,m+2,⋯,m+k−6}∪{m+k−5,m+k−4,m+k−3，m+k−2,m+k−1,m+k}.且当n=6，n=k－5时，式②成立.所以f(k+1)⩽f(k−5)+f(6)−1=[k+22]+[k+23]−[k+26]+1③由式①与③知，对n=k+1，式②成立.所以对任意的n≥4，有f(n)=[n+12]+[n+13]−[n+16]+1.12．【1995高中数学联赛（第02试）】求一切实数p，使得三次方程5x3−5(p+1)x2+(71p−1)x+1=66p的三个根均为自然数.【答案】76【解析】由观察易知x=1为原三次方程的一个自然数根，由综合除法，原三次方程可降次为二次方程5x2−5px+66p−1=0①原三次方程的三个根均为自然数等价于二次方程①的两个根均为自然数.设u，v(u≤v)为方程①的两个根，则由韦达定理得{u+v=p②uv=15(66p−1)③，把式②代入式③得5uv=66(u+v)−1④可知u，v都不能被2，3，11所整除.又由式④得v=66u−15u−66⑤而u，v均为自然数，由式⑤可知v>665，即u⩾14.又2|u，3|u均不成立，所以u⩾17.由v≥u及式⑤可得66u−15u−66⩾u，即5u2−132u+1⩽0.于是u⩽66+√662−55<1325，所以17⩽u⩽26.再由2|u，3|u均不成立知，u只能取17，19，23，25.当u=17时，由式⑤得v=112119=59，当u=19时，由式⑤得v=125329，并非自然数，应舍去当u=23时，由式⑤得v=151749，并非自然数，应舍去.当u=25时，由式⑤得v=1649，并非自然数，应舍去.59所以仅当p=u+v=76时，方程①的两根均为自然数，原方程的三根均为自然数.13．【1994高中数学联赛（第02试）】将与105互素的所有正整数从小到大排成数列，试求出这个数列的第100 0项.【答案】2186【解析】设S={1,2,⋯,105}，A1={x|x∈S且3|x}，A2={x|x∈S且5|xA3={x|x∈S且7|x}.则与105互素且不大于105的自然数为：|A1∩A2∩A3|=|S|−(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)−|A1∩A2∩A3|,所以|S|=105,|A1|=35,|A2|=21,|A3|=15，|A1∩A2|=7,|A1∩A4|=5,|A1∩A2|=3，|A1∩A2∩A3|=1，|A1∩A2∩A3|=105−(3×5+3×7+5×7)+(3+5+7)−1=105−71+15−1=48设与105互素的正整数按从小到大的顺序排成的数列为a1,a2,a3,⋯,a n,⋯，则a1=1,a2=2,a3=4,⋯,a48=104，令P={a1,a2,a3,⋯,a48}，一方面，对于n≥1，令a n=105k+r(k⩾0,0⩽r⩽104,k,r∈Z)，因为(a n,105)=1，所以(r,105)=1，故r∈P；另一方面，对于任意的非负整数k及r∈P，因为(r,105)=1，所以(105k+r,105)=1，从而必有n使得a n=105k+r.这表明数列{a n}由且仅由形如105k+r(k≥0，k∈Z，r∈P)的数按从小到大的顺序排列而成.因为数列是递增的，且对每个固定的非负整数k，当r取遍P的值时，共得48个数，而1000=48×20+40，所以a1000=105×220+a40.因为a48=104,a47=103,a46=101,a45=97,a44=94，a43=92,a42=89,a41=88,a40=86.所以a1000=105×20+86=2186.14．【1991高中数学联赛（第02试）】设a n为下述自然数N的个数：N的各位数字之和为n且每位数字只能取1，3或4，求证：a2n是完全平方数，这里n=1，2，…【答案】证明见解析【解析】设N=x1x2⋯x k，其中x1,x2,⋯,x k∈{1,3,4}且x1+x2+⋯+x k=n.假定n>4.删去x1时，则当x1依次取1，3，4时，x2+x3+⋯+x k分别等于n－1，n－3，n－4.故当n>4时a n=a n−1+a n−3+a n−4①先用归纳法证明下式成立a2n+1=a2n+a2n−1②因故当n=1时，式②成立.设n=k时，式②成立，即a2k+2=a2k+a2k−1，则据式①，有a2k+3=a2k+2+a2k+a2k−1=a2(k+1)+a2(k+1)−1.可见式②对k+1成立，于是式②对一切n∈N成立.2③再用归纳法证明下式成立a2n a2n+2=a2n+1因a2=1,a3=2,a4=4，故当n=1时，式③成立.2，设n=k时，式③成立，即a2k a2k+2=a2k+1则据式①，②，有2a2k+2a2k+4=a2k+2(a2k+1+a2k+1+a2k)=a2k+2a2k+3+a2k+2a2k+1+a2k+12.=a2k+2a2k+3+a2k+1a2k+3=a2k+3可见式③对k+1成立.故式③对一切n∈N成立.最后再用归纳法证明本题结论，显然n=1时结论正确，设a2n是完全平方数，则由式③知a2n+2是完全平方数，因此结论对任意自然数n成立.15．【1989高中数学联赛（第02试）】有n×n(n≤4)的一张空白方格表，在它的每一个方格内任意地填入+1与－1两数中的一个，现将表内n个两两既不同行(横)又不同列(竖)的方格中的数的乘积称为一个基本项.试证：按上述方式所填成的每一个方格表，它的全部基本项之和总能被4整除(即总能表成4k的形式，其中k∈Z).【答案】证明见解析【解析】首先题目中所谓的基本项共有n!个，且每个基本项的取值要么是1，要么是－1.设表中第i行，第j列的数为a ij(a ij=1或－1)，则每个a ij都出现在(n－1)!个基本项内..考虑全部(n!个)基本项的乘积G1⋅G2⋅⋯⋅C n!=∏a ij(n−1)!1⩽i,j≤n(n−1)!=1.由于n≥4，所以(n－1)!是偶数，故aij即G1⋅G2⋅⋯⋅G n!=1.说明在G1,G2,⋯,G n个基本项中－1有n!个数，设为2k个，于是G1,G2,⋯,G n中的1的个数为n!－2k，这样G1+G2+⋯+G n!=(n!−2k)+2k(−1)=n!−4k.显然是4的倍数，命题得证.16．【1985高中数学联赛（第02试）】在直角坐标系xOy中，点A(x1,y1)和点B(x2,y2)的坐标均为正整数.OA与x轴正方向的夹角大于45°，OB与x轴正方向的夹角小于45°，B在x轴上的射影为B'，A在y轴上的射影为A'，△OB'B的面积比△OA'A的面积大33.5.由x1,y1,x2,y2组成的四位数x1x2y2y1=x1⋅103+x2⋅102+y2⋅10+ y1试求出所有这样的四位数，并写出求解过程.【答案】答案见解析【解析】很明显，题设的主要条件是关于面积的一些等量关系.于是由S△BOB′=S△AOA′+33.5得x2y2=x1y1+67，因为x1y1>0，所以x2y2>67.因为x2,y2为一位正整数，所以x2y2=72和81.但因为∠BOB′<45°，即点B在直线y=x的下方所以x2>y2，故x2y2≠81.于是x2y2=72，所以x2=9,y2=8，从而x1y1=5.又因为∠AOB′>45°，所以x1<y1，由x1,y1均为一位正整数，推得x1=1,y1=5.所以x1x2y2y1=1985.17．【1984高中数学联赛（第02试）】设a n是12+22+⋯+n2的个位数字，n=1，2，3，…….试证0.a1a2⋯a n⋯是有理数.【答案】证明见解析【解析】本题实际上只要证出0.a1a2⋯a n⋯是循环小数即可.下面将介绍几个证法证法一因为k2,(k+10)2,(k+20)2,⋯,(k+90)2的个位数字都相同，而10个相同整数之和的个位数字是0，所以k2+(k+10)2+(k+20)2+⋯+(k+90)2的个位数字是0.从而a n+100=(12+22+⋯+n2+(n+1)2+⋯+(n+100)2)的个位数字为：(a n+(n+1)2+(n+2)2+⋯+(n+100)2)的个位数字={a n+[(n+1)2+(n+11)2+⋯+(n+91)2]+[(n+2)2+(n+12)2+⋯+(n+92)2]+⋯+[(n+10)2+(n+20)2+⋯+(n+100)2]}的个位数字=a n.所以0.a1a2⋯a n⋯是循环小数.证法二因为(k+10)2=k2+20k+100,所以(k+10)2与k2的个位数字相同.又因为数列{a n}的前10项依次为1，5，4，0，5，1，0，4，5，5.所以从a11至a20就是把a10=5分别加到a1~a10各项所得数的个位数字.由于a20=0，所以a21=a1=1，…，a30=a10=5,a31=a21+5的个位数字，……a40=a30+5的个位数字.依此类推，有a n+20=a n.即0.a1a2⋯a n⋯是循环节长为20的循环小数.优质模拟题强化训练1．设k 、l 、c 均为正整数，证明：存在正整数a 、b 满足b −a =c ⋅(a,b)，且τ(a)τ(a (a,b))⋅l =τ(b)τ(b a,b )⋅k ，其中(a ，b )表示a 、b 的最大公因数，τ(m)表示正整数m 的所有不同正因子的个数.【答案】见解析【解析】 如果m 的标准分解式为m =p 1α1p 2α2⋯p n n αn ，那么τ(m)=(α1+1)(α2+1)⋯(αn +1). 取定两个不同的素数p 、q 使得(pq ，c )=1.由于(p ，q )=1，利用裴蜀定理，存在正整数u 0,v 0，使得p k u 0−q l v 0=c .由于(pq ，c )=1，那么p ∤v 0且q ∤u 0.由中国剩余定理，下列同余方程组：{u 0+tq l ≡1( mod p)v 0+tp k ≡1( mod q)u 0+tq l ≡1( mod c)有正整数解t =t 0.令u =u 0+t 0q l ,v =v 0+t 0p k ，那么p k u −q l v =c ，而且(u ，pqc )=1.因此(v,pqc)=1,(u,v)=1.现在取d =p k 2−1q l 2−1,n =q l v ，则n +c =q l v +c =p k u .从而(n,n +c)=1.令a =nd ，b =(n +c )d ，那么(a ，b )=d ，因此b −a =cd =c ⋅(a,b).而且：τ(a)τ(a a,b )⋅l =τ(nd)τ(n)⋅l =τ(p k 2−1q l 2+l−1v)τ(q l v)⋅l =k 2(l 2+l)l l+1=k 2l 2. τ(b)τ(b a,b )⋅k =τ((n+c)d)τ(n+c)⋅k =τ(p k 2+k−1q l 2−1u)τ(p k u)⋅k =(k 2+k)l 2kk+1=k 2l 2. 所以τ(a)τ(a (a,b))⋅l =τ(b)τ(b (a,b))⋅k .2．求所有的正整数n ，使得方程1x 12+1x 22+⋯+1x n 2=n+1x n+12有正整数解. 【答案】{n ∈N +|n ⩾3}.【解析】当n =1时，方程变为1x 12=2x 22，得x2x 1=√2，显然无正整数解. 当n =2时，方程变为1x 12+1x 22=3x 32，得(x 2x 3)2+(x 1x 3)2=3(x 1x 2)2. 先证引理：a 2+b 2=3c 2无正整数解假设有一组正整数解a ､b ､c ，不妨设a ､b ､c 的最大公因数为1.由a ､b 为正整数，知a 2≡0或1(mod 3)，b 2≡0或1(mod 3).又3c2≡0( mod 3)，故a2≡0( mod 3)且b2≡0( mod 3)，即a≡0( mod 3)且b≡0( mod 3)，从而c≡0( mod 3).这与“a､b､c的最大公因数为1”矛盾.引理得证由a2+b2=3c2无正整数解，可知此时原方程无正整数解.当n=3时，方程变为1x12+1x22+1x32=4x42，由32+42=52，得32 (3×4×5)2+42(3×4×5)2=52(3×4×5)2，即1202+1152=1122，所以1202⋅122+1152⋅122=1(122)2，可得1202(1202+1152)+1152⋅122=1(122)2，即14002+13002+11802=11442，故14002+13002+11802=42882.这说明原方程有正整数解：x1=400,x2=300,x3=180,x4=288.当n≥4时，1x12+1x22+⋯+1x n2=n+1x n+12有正整数解：x1=400,x2=300,x3=180,x4=x5=⋯=x n=x n+1=288.综上，当n=1或n=2时，原方程无正整数解；当n≥3时，原方程有正整数解.即所求的n为{n∈N+|n⩾3}.3．求证：不存在无穷多项的素数数列p1,p2,⋯,p n,⋯，使得p k+1=5p k+4,k=1,2,⋯.【答案】见解析【解析】用反证法.假设存在满足题设的无穷多项的素数数列p1,p2,⋯,p n,⋯，则由p k+1=5p k+4得p k+1+1=5(p k+1)，于是数列{p k+1}是以5为公比的等比数列，所以p k+1=5k−1(p1+1)，故p k=5k−1(p1+1)−1,k=1,2,⋯.易知数列{p n}是严格递增的，不妨设p1>5(否则用p2作为首项)，则有(5，p1)=1，于是由费马小定理得5p1−1≡1( mod p1)，所以p p1=5p1−1(p1+1)−1=5p1−1p1+5p1−1−1=0( mod p1)，这与p p1是素数矛盾所以，满足题设的素数数列不存在.4．设m，n是正整数，满足mn|m2+n2+1.证明：m2+n2+1=3mn.【答案】证明见解析．【解析】由题：m，n是正整数，满足mn|m2+n2+1，设m2+n2+1=tmn,t∈N∗，mn|m2+n2+1，必有n|m2+1,m|n2+1，所以m2+1n ,n2+1m均为正整数，当m=n时，2m2+1=tm2,t∈N∗，1=(t−2)m2,t∈N∗，显然只能m=1,t=3，当m≠n时，不妨设m<n，则m 2+1n<m<n，考虑方程x2+y2+1=txy,t∈N∗，(m,n)是方程的一组解，m2+n2+1=tmn,t∈N∗，则m2+(m2+1n )2+1=m2+(tmn−n2n)2+1=m2+(tm−n)2+1=m2+n2+t2m2−2tmn+1 =t2m2−tmn=tm(tm−n)=tm(tmn−n2n)=tm⋅m2+1n即m2+(m2+1n )2+1=tm⋅m2+1n，即(m,m2+1n)也是方程x2+y2+1=txy,t∈N∗的一组解，同理可得：(n,n 2+1m)，(n2+1m,n),(m2+1n,m)均是该方程的解，照此递换，必有(1,2)是方程的解，所以t=3综上所述：t=3，即m2+n2+1=3mn.5．求证：对任意的n∈N∗，32n+2−8n−9能被64整除.【答案】证明见解析【解析】（1）当n=1时，式子32n+2−8n−9=34−8−9=64能被64整除，命题成立．（2）假设当n=k时，32k+2−8k−9能够被64整除．当n=k+1时，32k+4−8(k+1)−9=9[32k+2−8k−9]+64k+64=9[32k+2−8k−9]+64(k+1)，因为32k+2−8k−9能够被64整除，∴9[32k+2−8k−9]+64(k+1)能够被64整除．即当n=k+1时，命题也成立．由（1）（2）可知，32n+2−8n−9(n∈N∗)能被64整除．6．求最小的正整数n，使得当正整数点k≥n时，在前k个正整数构成的集合M={1,2,⋯,k}中，对任意x∈M总存在另一个数y∈M且y≠x，满足x+y为平方数．【答案】7【解析】易知当n≤6时，在M={1,2,3,4,5,6}中，数2与其他任何数之和皆不是平方数；以下证明，n的最小值为7．如果正整数x、y(x≠y)满足：x+y=平方数，就称{x,y}是一个“平方对”，显然在M={1,2,⋯,7}中，{1,3}，{2,7}，{3,6}，{4,5}为平方对．在M={1,2,⋯,7,8}中增加了平方对{1,8}；在M={1,2,⋯,7,8,9}中平加了平方对{7,9}．以下采用归纳法，称满足题中条件的k为具有性质P；简记为k∈P．据以上知，当7≤k≤32时，均有k∈P．设已证得，当7≤k≤m2(m≥3)时，皆有k∈P，今考虑7≤k≤(m+1)2情况，利用归纳假设，只需证，当k =m2+r，其中1≤r≤2m+1时，均有k∈P．首先，在r=2m+1，即k=(m+1)2时，(k,2m+3)构成平方对，这是由于k+(2m+3)=(m+1)2+(2m+3)=(m+2)2，而由m2−(2m+3)=(m−1)2−4≥0，知2m+3≤m2，即2m+3≠k．在1≤r≤2m时，(k,2m+1−r)构成平方对，这是由于k+(2m+1−r)=(m2+r)+(2m+1−r)=(m+1)2，而1≤2m+1−r≤2m<m2，所以2m+1−r≠k．因此对于满足7≤k≤(m+1)2的每个k，皆有k∈P，从而对所有满足7≤k≤m2(m≥3)的正整数k，皆有k∈P，即对一切正整数k≥7，均有k∈P．所以n的最小值为7．7．设k∈Z+，定义：A1=1，A n+1=nA n+2(n+1)2k(n=1,2⋯).证明：当n≥1时，A n为整数，且A n为奇数当且n+2仅当n≡1或2(mod4).【答案】见解析【解析】注意到(n+2)A n+1−nA n=2(n+1)2k①(n+1)A n−(n−1)A n−1=2n2k②(n +1)×①+n ×②得(n +1)(n +2)A n+1−(n +1)nA n−1=2(n +1)2k+1+2n 2k+1. 反复运用上式，再叠加得A n =2S(n)n(n+1).其中，S(n)=1′+2′+⋯+n′(t =2k +1).由2S(n)=∑[(n −i)t +i t ]n i=0=∑[(n +1−i)t +i t ]n i=1⇒n(n +1)|2S(n)因此，A n (n ≥1)为整数.1.若n ≡0或2(mod 4)，由S(n)有奇数个奇数项知S(n)为奇数. 于是，A n 为奇数.2.若n ≡0(mod 4)，则(n 2)t ≡0(mod n)故S(n)=∑[(n −i)t +i t ]n 2i=0−(n 2)t ≡0(mod n) 于是，A n 为偶数.3.若n ≡3(mod 4)，则(n+12)t ≡0(mod n +1) 故S(n)=∑[(n +1−i)t +i t ]n+12i=1−(n+12)t ≡0(mod n).于是，A n 为偶数.因此，当n ≥1时，A n 为整数，且A n 为奇数当且仅当n ≡1或2(mod 4). 8．已知a 、b 、c 、d 、e 、e 为整数，方程ax 5−2bx 4+3cx 3−5dx 2+7ex −2024=0①有正整数解．证明：存在无穷多个正整数k 使得61|(11k 5−7ek 4+5dk 3−3ck 2+2bk −a)．【答案】见解析【解析】设方程①的正整数解为x =m ．首先说明：(m,61)=1．否则，61|m ⇒61|(am 5−2bm 4+3cm 3−5dm 2+7em)⇒61|2024．矛盾． 由am 5−2bm 4+3cm 3−5dm 2+7em −2024=0⇒am 5−2bm 4+3cm 3−5dm 2+7em −11=2013=3×11×61⇒am 5−2bm 4+3cm 3−5dm 2+7em −11≡0(mod 61)．取整数n(1≤n≤60)，满足mn≡1(mod61)．故0≡−(am5−2bm4+3cm3−5dm2+7em−11)n5≡11n5−7en4+5dn3−3cn2+2bn−a≡0(mod61)．取k=61t+n(t=1,2,⋯)．则11k5−7ek4+5dk3−3ck2+2bk−a≡11n5−7en4+5dn3−3cn2+2bn−a≡0(mod61)．因此，存在无穷多个正整数k，使得61|(11k5−7ek4+5dk3−3ck2+2bk−a)．9．已知a n=∑n−1i=010i(n=1,2,⋅⋅⋅)，求证：存在无穷多个正整数n，使a1,a2,⋅⋅⋅,a n除以n的余数互不相同。
初等数论1、（2010一试8）方程2010=++z y x 满足z y x ≤≤的正整数解(,,)x y z 的个数是. 【答案】336675易知 100420096100331⨯=+⨯+k ，所以110033*********-⨯-⨯=k200410052006123200910052006-⨯=-⨯+-⨯=，即3356713343351003=-⨯=k .从而满足z y x ≤≤的正整数解的个数为33667533567110031=++.2、（2011一试8）已知=n a C ())95,,2,1(2162003200 =⎪⎪⎭⎫⎝⎛⋅⋅-n nnn ，则数列}{n a 中整数项的个数为． 【答案】15 【解析】=n a C65400320020023n nn--⋅⋅．要使)951(≤≤n a n 为整数，必有65400,3200nn --均为整数，从而4|6+n ． 当=n 2,8,14,20,26,32,38,44,50,56,62,68,74,80时，3200n -和65400n-均为非负整数，所以n a 为整数，共有14个．当86=n 时，=86a C 5388620023-⋅⋅，在C !114!86!20086200⋅=中，!200中因数2的个数为1972200220022002200220022002200765432=⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡， 同理可计算得!86中因数2的个数为82，!114中因数2的个数为110，所以C 86200中因数2的个数为511082197=--，故86a 是整数．当92=n 时，=92a C 10369220023-⋅⋅，在C !108!92!20092200⋅=中，同样可求得!92中因数2的个数为88,!108中因数2的个数为105,故C 86200中因数2的个数为410588197=--，故92a 不是整数． 因此，整数项的个数为15114=+．3、（2015一试8）对四位数(19,0,,9)abcd a b c d ≤≤≤≤,若,,a b b c c d ><>,则称abcd 为P 类数,若,,a b b c c d <><,则称a b c d 为Q 类数,用()N P 与()N Q 分别表示P 类数与Q 类数的个数,则()()N P N Q -的值为【答案】28511..dcba B dcba B A abcd A B ∈∈故反之，每个唯一对应于中的元素这建立了与之间的一一对应，因此有 010()()||||||||||||.N P N Q A B A A B A -=-=+-=00||:0,0,19b,A abc A b ∈⋅⋅⋅下面计算对任一四位数可取，，，对其中每个99b a b c <≤<≤由及知，a 和c 分别有9-b 种取法，从而992200191019|=(9)26|85.b k b k ==⨯⨯-===∑∑A ()()285.N P N Q -=因此，4、（2016一试8）设4321,,,a a a a 是1，2，…，100中的4个互不相同的数，满足2433221242322232211)())((a a a a a a a a a a a a ++=++++则这样的有序数组),,,(4321a a a a 的个数为 . 【答案】40【解析】由柯西不等式知，2433221242322232211)())((a a a a a a a a a a a a ++≥++++，等号成立的充分必要条件是433221a a a a a a ==，即4321,,,a a a a 成等比数列.于是问题等价于计算满足{1,2,3,},,,{4321⊆a a a a …,100}的等比数列4321,,,a a a a 的个数.设等比数列的公比1≠q ，且q 为有理数.记mnq =，其中n m ,为互素的正整数，且n m ≠. 先考虑m n >的情况.此时331314)(m n a m n a a ==，注意到33,nm 互素，故31m a l =为正整数. 相应地，4321,,,a a a a 分别等于l n l mn nl m l m 3223,,,，它们均为正整数.这表明，对任意给定的1>=mnq ，满足条件并以q 为公比的等比数列4321,,,a a a a 的个数，即为满足不等式1003≤l n 的正整数l 的个数，即]100[3n.由于10053>，故仅需考虑34,4,23,3,2=q 这些情况，相应的等比数列的个数为20113312]64100[]64100[]27100[]27100[]8100[=++++=++++. 当m n <时，由对称性可知，亦有20个满足条件的等比数列4321,,,a a a a . 综上可知，共有40个满足条件的有序数组),,,(4321a a a a .5、（2017一试4）若一个三位数中任意两个相邻数码的差均不超过1，则称其为“平稳数”.平稳数的个数是. 【答案】756、（2009二试3）设k ， l 是给定的两个正整数．证明：有无穷多个正整数m k ≥，使得C k m 与l 互素． 【解析】证法一：对任意正整数t ，令(!)m k t l k =+⋅⋅．我们证明()C 1k m l =，． 设p 是l 的任一素因子，只要证明：p/|C k m ．若p /|k !，则由1!C ()k k mi k m k i ==-+∏1[((!)]k i i tl k =≡+∏1ki i =≡∏()1!mod k p α+≡．及|!p k α，且pα+1/|k !，知|!C k m p k α且1α+p /|!C k m k ．从而p/|C km ．证法二：对任意正整数t ，令2(!)m k t l k =+⋅⋅，我们证明()C 1k m l =，． 设p 是l 的任一素因子，只要证明：p/|C k m ． 若p /|k !，则由 1!C ()==-+∏kkmi k m k i 21[((!)]ki i tl k =≡+∏1ki i =≡∏()!mod k p ≡．即p 不整除上式，故p/|C k m ．若|!p k ，设1α≥使|!p k α，但1/|!p k α+．12|(!)p k α+．故由11!C ()k kmi k m k i -==-+∏21[((!)]ki i tl k =≡+∏1ki i =≡∏()1!mod k p α+≡,及|!p k α，且pα+1/|k !，知|!C k m p k α且1α+p /|!C k m k ．从而p/|C km ．7、（2009二试4）在非负数构成的39⨯数表111213141516171819212223242526272829313233343536373839x x x x x x x x x P x x x x x x x x x x x x x x x x x x ⎛⎫⎪= ⎪ ⎪⎝⎭中每行的数互不相同，前6列中每列的三数之和为1，1728390x x x ===，27x ，37x ，18x ，38x ，19x ，29x 均大于．如果P 的前三列构成的数表111213212223313233x x x S x x x x x x ⎛⎫ ⎪= ⎪ ⎪⎝⎭满足下面的性质()O ：对于数表P 中的任意一列123k k k x x x ⎛⎫ ⎪⎪ ⎪⎝⎭（1k =，2，…，9）均存在某个{}123i ∈，，使⑶{}123min ik i i i i x u x x x =≤，，．求证：（ⅰ）最小值{}123min i i i i u x x x =，，，1i =，2，3一定自数表S 的不同列． （ⅱ）存在数表P 中唯一的一列***123k k k x x x ⎛⎫⎪⎪ ⎪ ⎪⎝⎭，*1k ≠，2，3使得33⨯数表***111212122231323k k k x x x S x x x x x x ⎛⎫ ⎪'= ⎪ ⎪ ⎪⎝⎭仍然具有性质()O ．【解析】（ⅰ）假设最小值{}123min i i i i u x x x =，，，1i =，2，3不是取自数表S 的不同列．则存在一列不含任何i u ．不妨设2i i u x ≠，1i =，2，3．由于数表P 中同一行中的任何两个元素都不等，于是2i i u x <，1i =，2，3．另一方面，由于数表S 具有性质()O ，在⑶中取2k =，则存在某个{}0123i ∈，，使得002i i x u ≤．矛盾．（ⅱ）由抽届原理知，{}1112min x x ，，{}2122min x x ，，{}3132min x x ，中至少有两个值取在同一列．不妨设{}212222min x x x =，，{}313232min x x x =，．由前面的结论知数表S 的第一列一定含有某个i u ，所以只能是111x u =．同样，第二列中也必含某个i u ，1i =，2．不妨设222x u =．于是333u x =，即i u 是数表S 中的对角线上数字． 111213212223313233x x x S x x x x x x ⎛⎫ ⎪= ⎪⎪⎝⎭下面证明33⨯数表***111212122231323k k k x x x S x x x x x x ⎛⎫ ⎪'= ⎪ ⎪ ⎪⎝⎭具有性质()O ．从上面的选法可知{}{}*1212:min min i i i i i ik u x x x x x '==，，，，(13)i =，．这说明 {}*111211min k x x x u >，≥，{}*313233min k x x x u >，≥．又由S 满足性质()O ．在⑶中取*k k =，推得*22k x u ≤，于是{}**2212222min k k u x x x x '==，，．下证对任意的k M ∈，存在某个1i =，2，3使得i ik u x '≥．假若不然，则{}12min ik i i x x x >，，1i =，3且*22k k x x >．这与*2k x 的最大性矛盾．因此，数表S '满足性质()O ． 下证唯一性．设有k M ∈使得数表111212122231323k k k x x x S x x x x x x ⎛⎫⎪= ⎪ ⎪⎝⎭具有性质()O ，不失一般性，我们假定{}111121311min u x x x x ==，，⑷{}221222322min u x x x x ==，，{}331323333min u x x x x ==，， 3231x x <．由于323x x<，2221x x <及（ⅰ），有{}11112111min k u x x x x ==，，．又由（ⅰ）知：或者()a {}3313233m i n k k u x x x x ==，，，或者{}2212222()min k k b u x x x x ==，，． 如果()a 成立，由数表S 具有性质()O ，则{}11112111min k u x x x x ==，，，⑸{}22122222min k u x x x x ==，，， {}3313233min k k u x x x x ==，，．由数表S 满足性质()O ，则对于3M ∈至少存在一个{}123i ∈，，使得*i ik u x ≥．由*k I ∈及⑷和⑹式知，*1111k x x u >=，*3323k x x u >=．于是只能有*222k k x u x =≤．类似地，由S '满足性质()O 及k M ∈可推得*222k k x u x '=≤．从而*k k =．8、（2010一试11）证明：方程02523=-+x x 恰有一个实数根r ，且存在唯一的严格递增正整数数列}{n a ，使得+++=32152a a a r r r.若存在两个不同的正整数数列 <<<<n a a a 21和 <<<<n b b b 21满足52321321=+++=+++ b b b a a a r r r r r r ， 去掉上面等式两边相同的项，有 +++=+++321321t t t s s s r r r r r r，这里 <<<<<<321321,t t t s s s ，所有的i s 与j t 都是不同的. 不妨设11t s <，则 ++=++<21211t t s s s r r r r r，112111111121211=--<--=++≤++<--rr r r r s t s t ，矛盾.故满足题设的数列是唯一的.9、（2010二试2）设k 是给定的正整数，12r k =+．记(1)()()f r f r r r ==⎡⎤⎢⎥，()()l f r =(1)(()),2l f f r l -≥．证明：存在正整数m ，使得()()m f r 为一个整数．这里，x ⎡⎤⎢⎥表示不小于实数x 的最小整数，例如：112⎡⎤=⎢⎥⎢⎥，11=⎡⎤⎢⎥．【解析】记2()v n 表示正整数n 所含的2的幂次．则当2()1m v k =+时，()()m f r 为整数． 下面我们对2()v k v =用数学归纳法．当0v =时，k 为奇数，1k +为偶数，此时()111()1222f r k k k k ⎛⎫⎡⎤⎛⎫=++=++ ⎪ ⎪⎢⎥⎝⎭⎢⎥⎝⎭为整数． 假设命题对1(1)v v -≥成立．对于1v ≥，设k 的二进制表示具有形式1212222v v v v v k αα++++=+⋅+⋅+，这里，0i α=或者1，1,2,i v v =++．于是 ()111()1222f r k k k k ⎛⎫⎡⎤⎛⎫=++=++ ⎪ ⎪⎢⎥⎝⎭⎢⎥⎝⎭2122k k k =+++ 11211212(1)2()222v v v v v v v ααα-++++=+++⋅++⋅+++12k '=+， ① 这里1121122(1)2()22v v v v v v v k ααα-++++'=++⋅++⋅+++.显然k '中所含的2的幂次为1v -．故由归纳假设知，12r k ''=+经过f 的v 次迭代得到整数，由①知，(1)()v f r +是一个整数，这就完成了归纳证明．10、（2010二试4）一种密码锁的密码设置是在正n 边形12n A A A 的每个顶点处赋值0和1两个数中的一个，同时在每个顶点处涂染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同．问：该种密码锁共有多少种不同的密码设置？设标有a 的边有2i 条，02n i ⎡⎤≤≤⎢⎥⎣⎦，标有b 的边有2j 条，202n i j -⎡⎤≤≤⎢⎥⎣⎦．选取2i 条边标记a 的有2in C 种方法，在余下的边中取出2j 条边标记b 的有22jn i C -种方法，其余的边标记c ．由乘法原理，此时共有2in C 22j n i C -种标记方法．对i ，j 求和，密码锁的所有不同的密码设置方法数为 222222004n n i i j nn i i j C C -⎡⎤⎡⎤⎢⎥⎢⎥⎣⎦⎣⎦-==⎛⎫ ⎪ ⎪ ⎪⎝⎭∑∑． ① 这里我们约定001C =．当n 为奇数时，20n i ->，此时22221202n i jn i n ij C-⎡⎤⎢⎥⎣⎦---==∑． ②代入①式中，得()()2222222221222000044222n n i n n i j i n i i n i n n i n n i j i i C C C C -⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦----====⎛⎫ ⎪== ⎪⎪⎝⎭∑∑∑∑ 022(1)(21)(21)nnkn kk n kk n n nn k k C C --===+-=++-∑∑31n =+．222222004n n i i j n n i i j C C -⎡⎤⎡⎤⎢⎥⎢⎥⎣⎦⎣⎦-==⎛⎫ ⎪= ⎪ ⎪⎝⎭∑∑()122210412n i n i n i C ⎡⎤-⎢⎥⎣⎦--=⎛⎫ ⎪⨯+ ⎪ ⎪⎝⎭∑()2221024233n i n i n n i C ⎡⎤⎢⎥⎣⎦--==+=+∑． 综上所述，这种密码锁的所有不同的密码设置方法数是：当n 为奇数时有31n +种；当n 为偶数时有33n+种．11、（2011二试2）证明：对任意整数4≥n ，存在一个n 次多项式0111)(a x a x a x x f n n n ++++=--具有如下性质：（1）110,,,-n a a a 均为正整数；（2）对任意正整数m ，及任意)2(≥k k 个互不相同的正整数k r r r ,,,21 ，均有)()()()(21k r f r f r f m f ≠．【解析】令 2)()2)(1()(++++=n x x x x f ， ①将①的右边展开即知)(x f 是一个首项系数为1的正整数系数的n 次多项式． 下面证明)(x f 满足性质（2）．对任意整数t ，由于4≥n ，故连续的n 个整数n t t t +++,,2,1 中必有一个为4的倍数，从而由①知)4(mo d 2)(≡t f ．因此，对任意)2(≥k k 个正整数k r r r ,,,21 ，有 )4(m od 02)()()(21≡≡k k r f r f r f ． 但对任意正整数m ，有)4(m od 2)(≡m f ，故)4)(m od ()()()(21k r f r f r f m f ≡/， 从而)()()()(21k r f r f r f m f ≠． 所以)(x f 符合题设要求．12、（2011二试3）设)4(,,,21≥n a a a n 是给定的正实数，n a a a <<< 21．对任意正实数r ，满足)1(n k j i r a a a a j k ij ≤<<≤=--的三元数组),,(k j i 的个数记为)(r f n ．证明：4)(2n r f n <．因此，当n 为偶数时，设m n 2=，则有∑∑∑-=-=-=+==121212)()()()(m mj j m j j n j j n r g r g r g r f2)1(2)1()2()1(1212-+-=-+-≤∑∑-+==m m m m j m j m m j m j 4222n m m m =<-=．当n 为奇数时，设12+=m n ，则有∑∑∑+==-=+==mm j jmj j n j j n r gr g r g r f 21212)()()()(∑∑+==-++-≤mm j m j j m j 212)12()1(422n m <=．13、（2011二试4）设A 是一个93⨯的方格表，在每一个小方格内各填一个正整数．称A 中的一个)91,31(≤≤≤≤⨯n m n m 方格表为“好矩形”，若它的所有数的和为10的倍数．称A 中的一个11⨯的小方格为“坏格”，若它不包含于任何一个“好矩形”．求A 中“坏格”个数的最大值． 【解析】首先证明A 中“坏格”不多于25个．用反证法．假设结论不成立，则方格表A 中至多有1个小方格不是“坏格”．由表格的对称性，不妨假设此时第1行都是“坏格”．设方格表A 第i 列从上到下填的数依次为9,,2,1,,, =i c b a i i i ．记9,,2,1,0,)(,11=+==∑∑==k c b T a S ki i i k ki i k ，这里000==T S ．即第2行至第3行、第1+m 列至第n 列组成一个“好矩形”，从而至少有2个小方格不是“坏格”，矛盾． 类似地，也不存在90,,≤<≤n m n m ，使)10(m od n n m m T S T S +≡+．因此上述断言得证．故)10(mod 59210)(999≡++++≡+≡≡∑∑∑=== k k k k k k k T S T S ，所以 )10(mod 055)(99090≡+≡+≡+∑∑∑===k k k k k k k T S T S ，矛盾！故假设不成立，即“坏格”不可能多于25个．另一方面，构造如下一个93⨯的方格表，可验证每个不填10的小方格都是“坏格”，此时有25个“坏格”．综上所述，“坏格”个数的最大值是25．14、（2012二试2）试证明：集合{}22,2,,2,n A =满足（１）对每个a A ∈，及b N *∈，若21b a <-，则(1)b b +一定不是2a 的倍数；（２）对每个a A ∈（其中A 表示A 在Ｎ 中的补集），且1a ≠，必存在b N *∈，21b a <-，使(1)b b +是2a 的倍数．【解析】证明:对任意的a A ∈,设2,,ka k N *=∈则122,k a +=如果b 是任意一个小于21a -的正整数,则121b a +≤-则122k a m +=⋅下面给出(2)的三种证明方法: 证法一:令1,12,k b mx b y +=+=消去b 得12 1.k y mx +-=由于1(2,)1,k m +=这方程必有整数解;1002k x x ty y mt +⎧=+⎪⎨=+⎪⎩其中00,(,)t z x y ∈为方程的特解.把最小的正整数解记为(,),x y **则12k x *+<,故21,b mx a *=<-使(1)b b +是2a 的倍数．证法二:由于1(2,)1,k m +=由中国剩余定理知,同余方程组10(mod 2)1(mod )k x x m m +⎧=⎨=-⎩在区间1(0,2)k m +上有解,x b =即存在21,b a <-使(1)b b +是2a 的倍数． 证法三:由于(2,)1,m =总存在(,1),r r N r m *∈≤-使21(mod )r m =取,t N *∈使1,tr k >+则21(mod )tr m =存在1(21)(2)0,,tr k b q m q N +=--⋅>∈使021,b a <<- 此时1,21,k m b m ++因而(1)b b +是2a 的倍数．15.（2013二试4）（本题满分50分）设,n k 为大于1的整数，2k n <.证明：存在2k 个不被n 整除的整数，若将它们任意分成两组，则总有一组若干个数的和被n 整除. 【证明】先考虑n 为2的幂的情形.设2,1r n r =≥，则r k <.取3个12r -及23k -个1，显然这些数均不被n 整除.将这2k 个数任意分成两组，则总有一组中含2个12r -，它们的和为2r ，被n 整除. 现在设n 不是2的幂，取2k 个数为22211,1,2,2,,2,1,2,2,,2k k -------，因为n 不是2的幂，故上述2k 个数均不被n 整除.若可将这些数分成两组，使得每一组中任意若干个数的和均不能被n 整除.不妨设1在第一组，由于（-1）+1=0，被n 整除，故两个-1必须在第二组；因（-1）+（-1）+2=0，被n 整除，故2在第一组，进而推出-2在第二组. 现归纳假设1,2,,2l 均在第一组，而1,1,2,,2l ----均在第二组，这里12l k ≤<-，由于()()()()1112220l l +-+-+-++-+=，被n 整除，故12l +在第一组，从而12l +-在第二组.故由数学归纳法可知，221,2,2,,2k -在第一组，221,1,2,2,,2k ------在第二组.最后，由于()()()()21112220k k ---+-+-++-+=，16、（2014二试4）（本题满分50分）设整数122014,,,2014x x x 模互不同余，122014,,,y y y 整数模2014也互不同余.证明：可将122014,,,y y y 重新排列为122014,,,z z z ，使得112220142014,,,x z x z x z +++模4028互不同余.【证明】(mod2),12.,i i y i k i k i ≡≡≤≤记k=1007,不妨设x 对每个整数 1,+(mod4),,i i i k i k i i i k i k i k y x y k y y ++++≤≤≡+==若x 不则令z z ；否则，,.i i k i k i z y z y ++==令如果是前一种情形，则++=(mod4)i i i i i k i k i k i k z y x y x z k ++++=≡++x x 不 如果是后一种情形，则也有+++=(mod4)i i i i k i k i i k i k z y x y x z k +++=≡++x x 不++(mod4),+(mod4),i i i k i k i i k i k i y x y k y x y k +++≡+≡+若不然，我们有x x 22(mod4),(mod2)i i k i i k x x k x x k ++≡≡两式相加可得于是，但 122014,,,2014=2)(mod2),i i k x x x k x k +≡模（互不同余，特别地，x 不矛盾.122122,,,y ,,,k k z z z y y 由上述构造方法知是的排列.记1122,1,2,,2.w ,,,4.i i k x z i k w w k =+=w 下面模互不同余≤≤这只需证明，对任意整数i,j,1i<j k,w ,,,4i j i k j k w w w k ++*模两两不同余.()注意，前面的构造方式已保证(mod4),(mod4).()i i k j j k w k w k ++≡≡**w 不w 不,.i i j j z y z y ==情形一：且则由前面的构造方式可知 2(mod2),2(mod2).i i k j j k w i k w j k ++≡≡≡≡w w 22(mod2),2i j j k i j k w w k +≡由于不故易知与w 及模 j 24i k j k w w w k k ++不同余，与及模不同余，从而模更***不同余，再结合（）可见（）得证.,(,i i j j k i i k j i z y z y z y z y ++====情形三：且且的情形与此相同）.则由前面的构造方式可知2(mod2),2(mod2).i i k j j k w i k w j k k ++≡≡≡≡+w w22(mod2),22(mod2),k i j k i j k k ≡+≡+由于是奇数，故不更有不+22i j j k i k j j k w w k w w k ++因此仍然有w 与及模不同余，w 与及模不同余.*从而（）得证.因此本题得证.17、（2015二试4）(本题满分50分)求具有下述性质的所有正整数k :对任意正整数(1)1,2k n n -+不整除()!!kn n .22(()!)(!),1kn v kn n v n -≥-进而由（）知，本题等价于 ≥求所有正整数k,使得s(kn)s(n)对任意正整数n 成立.(0,1,2,).a a =⋅⋅⋅我们证明，所有符号条件的k 为2(2)()a S n S n n =一方面，由于对任意正整数成立，故2.a k =符合条件 22,0,1.a k k q a q =⋅≥另一方面，若不是的方幂，设是大于的奇数)().)=2)(),a n S kn S n S kn S qn S qn <=下面构造一个正整数，使得（因为（（,)().m q m S m S q<因此问题等价于我们选取的一个倍数使得（2)1,,21(mod ).(u q u q =≡由（，熟知存在正整数使得事实上，).)u q ϕ由欧拉定理知，可以取（12122+2++2,0, 2.t t q t αααααα⋅⋅⋅=<<⋅⋅⋅<≥设奇数的二进制表示为1122+2++22,t t tu m S αααα-+=⋅⋅⋅+取则（m)=t,且 (21)0(mod ).t tu q α-≡m=q+2我们有(`1)21211212(122)t t tu u u t um q q q αα---=+⋅=+⋅++⋅⋅⋅+102112.t ut lu l q α-+=-=+⋅∑212102,u u u u q q --<<由于故正整数的二进制表示中的最高次幂小于，由此2121(01),22t tu u lu ju i j i j t q qαα++--≤<≤-⋅⋅易知，对任意整数，数与 的二进制表示中没有相同的项.210,20,1,,1)1tu lu t l t q αα+->⋅=⋅⋅⋅-又因为故（的二进制表示中均不包含，故212)1()(),u m S S t t S m q q-=+⋅>=由（）可知（.m 因此上述选取的满足要求(0,1,2,).a a =⋅⋅⋅综合上述的两个方面可知，所求的k 为218、（2016二试3）（本题满分50分）给定空间中10个点，其中任意四点不在一个平面上，将某些点之间的线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值. 【解析】以这10个点为顶点，所连线段为边，得到一个10界简单图G ，我们证明G 的边数不超过15.边，否则就形成三角形，所以，121,,,n v v v +⋅⋅⋅之间恰有n 条边.对每个j (210)n j +≤≤，j v 至多与21,,n v v +⋅⋅⋅中的一个顶点相邻（否则设j v 与,(21)s t v v s t n ≤<≤+）相邻，则1,,,s j t v v v v 就对应了一个空间四边形的四个顶点，这与题设条件矛盾，从而21,,n v v +⋅⋅⋅与210,,n v v +⋅⋅⋅之间的边数至多10(1)9n n -+=-条.在210,,n v v +⋅⋅⋅这9n -个顶点之间，由于没有三角形，由托兰定理，至多2(9)[]4n -条边，因此G 的边数22(9)(9)25(9)[]9[]9[]15444n n k n n --≤+-+=+≤+=如图给出的图共有15条边，且满足要求，综上所述，所求边数的最大值为15.19、（2017二试3）（本题满分50分）将33×33方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等，若相邻两个小方格的颜色不同，则称它们的公共边为“分隔边”.试求分隔边条数的最小值.解：记分隔边的条数为L ，首先，将方格纸按如图分成三个区域，分别染成三种颜色，粗线上均为分隔边，此时共有56个分隔边，即L=56.1233123312356.,.,.A (A ),B ().,,.,().1,A .A ,)0,,).((ii i i j j j i j i j i j L A A B B n n B c c c c n c c c c B c n A δδ≥⎧⎪=⎨⎪⎩下面证明将方格纸的行从上至下依次记为A ，，列从左至右依次记为B ，，行中方格出现的颜色数记为列中方格出现的颜色个数记为三种颜色分别记为对于一种颜色设是含有色方格的行数与列数之和记若行含有色方格（否则.类似地定义（于是3333311133331112)())(A ,),))(A ,),))().133=3633363,n()38,n()391,i i i j i j i i j i j i j j j i j j j j j j n B c B c c B c n c c c a b c a b ab c a b c j δδδδ======+=+=+=⋅≥=+≥≥>≥=∑∑∑∑∑∑（（（（由于染色的方格有个，设含有色方格的行有个，列有个，则色的方格一定在这行和列的交叉方格中，因此从而故，33333311131112,3.1()()1()1(()1)(()1)(()())66(2)(()66.31.c 33c i i i j j i i i i i i i j j A n A n A B n B L n A n B n A n B n c ====--≥-+-=-=-∑∑∑∑（）由于在行中有种颜色的方格，因此至少有条分隔边，同理在列中，至少有条分隔边。
全国高中数学历届(2009-2019)联赛初等数论试题汇编1．【2017年全国联赛】若一个三位数中任意两个相邻数码之差均不超过1,则称其为“平稳数”.那么,平稳数的个数为____________。
【答案】75【解析】考虑平稳数,若,则,有2个平稳数。
若,则个平稳数。
若,则,有个平稳数。
若，则，有个平稳数。
综上，平稳数的个数为。
故答案为：752．【2015年全国联赛】对四位数，若，则称类数；若，则称类数.用分别表示类数与类数的个数.则的值为______.【答案】285【解析】记类数、类数的全体分别为，再记个位数为零的类数全体为，个位数不为零的类数全体为. 对任一四位数，将其对应到四位数.注意到，.则.反之，每个唯一对应于中的元素.因此，建立了之间的一一对应.故.下面计算.对任意四位数可取0，1，…，9，对其中每个，由，知分别有种取法.故.因此，.故答案为：2853．【2010年全国联赛】方程满足的正整数解（）的个数是________.【答案】336675【解析】首先，易知方程的正整数解的个数为.其次，把方程满足的正整数解分为三类：（1）均相等的正整数解的个数显然为1；（2）中有且仅有两个相等的正整数解的个数，易知为1003；（3）设两两均不相等的正整数解的个数为.注意到.解得.故满足的正整数解的个数为.4．【2019年全国联赛】设m为整数，|m|≥2.整数数列满足：不全为零，且对任意正整数n，均有.证明：若存在整数r，s（r>s≥2）使得，则.【答案】【解析】若，记.则对任意正整数n，d|a n，考虑数列，可得同样结论。
故不妨设，由可知，即对任意大于2的正整数n，.若a 1，不满足，则不存在r>s≥2使得，故不妨设，由互质性.设，则b n为整数数列，.可知，若存在整数使得，则.而，故，由知，故r-s≥|m|.5．【2018年全国联赛】设n，k，m是正整数，满足k≥2，且.设A是的n元子集。
第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++是m 得倍数．证明：12,,n a a a 都是m 的倍数。
∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n nq a q a q a ∴+++1122n n q p m q p m q p m =+++1122()n n p q q p q p m =+++即1122n n q a q a q a +++是m 的整数2．证明 3|(1)(21)n n n ++ 证明(1)(21)(1)(21)n n n n n n n ++=+++-(1)(2)(1)(1)n n n n n n =+++-+ 又(1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证：,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b 00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b bb b ---则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t <()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有 1102222b b q q t a bs a b a b t ++-≤=-=-=-<∴≤ 若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b r q r -=，┄, d '|21(,)n n n n r r q r a b --=+=,即d '是(,)a b 的因数。
（完整版）初等数论练习题二（含答案）《初等数论》期末练习一一、单项选择题1、如果a b ，b a ，则( ).A b a =B b a -=C b a ≤D b a ±=2、如果n 3，n 5，则15（）n .A 整除B 不整除C 等于D 不一定3、在整数中正素数的个数（）.A 有1个B 有限多C 无限多D 不一定4、如果)(mod m b a ≡,c 是任意整数,则A )(mod m bc ac ≡B b a =C ac T )(mod m bcD b a ≠5、如果( ),则不定方程c by ax =+有解.A c b a ),(B ),(b a cC c aD a b a ),(6、整数5874192能被( )整除.A 3B 3与9C 9D 3或97、如果n 2，n 15，则30（）n .A 整除B 不整除C 等于D 不一定8、大于10且小于30的素数有（）.A 4个B 5个C 6个D 7个9、模5的最小非负完全剩余系是( ).A -2,-1,0,1,2B -5,-4,-3,-2,-1C 1,2,3,4,5D 0,1,2,3,410、整数637693能被( )整除.A 3B 5C 7D 9二、填空题1、素数写成两个平方数和的方法是（）.2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ).3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为(). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ).5、b a ,的公倍数是它们最小公倍数的( ).6、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r π≤0.7、设p 是素数,则不定方程22y x p +=有（）.8、如果同余式)(mod 0m b ax ≡+有解,则解的个数( ).9、在176与545之间有( )是13的倍数.10、如果0φab ,则),](,[b a b a =( ).11、如果1),(=b a ,那么),(b a ab +=( ).三、计算题1、求[136,221,391]=?2、求解不定方程144219=+y x .3、解同余式)45(mod 01512≡+x .4、求??563429,其中563是素数. （8分） 5、求[24871,3468]=?6、求解不定方程18176=-y x .7、解同余式)321(mod 75111≡x .8、求17的平方剩余与平方非剩余.四、证明题1、证明对于任意整数n ,数62332n n n ++是整数. 2、证明相邻两个整数的立方之差不能被5整除.3、证明形如14-n 的整数不能写成两个平方数的和.4、如果整数a 的个位数是5,则该数是5的倍数.5、证明相邻两个偶数的乘积是8的倍数.初等数论期末练习一答案一、单项选择题1、D.2、A3、C4、A5、A6、B7、A8、C9、D 10、C二、填空题1、素数写成两个平方数和的方法是（唯一的）.2、同余式)(mod 0m b ax ≡+有解的充分必要条件是(b m a ),().3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ][ba ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( 与p 互素 ).5、b a ,的公倍数是它们最小公倍数的( 倍数 ).6、如果b a ,是两个正整数,则存在( 唯一 )整数r q ,,使r bq a +=,b r π≤0.7、设p 是素数,则不定方程22y x p +=有（唯一解）.8、如果同余式)(mod 0m b ax ≡+有解,则解的个数( ),(m a ).9、在176与545之间有( 28 )是13的倍数.10、如果0φab ,则),](,[b a b a =( ab ).11、如果1),(=b a ,那么),(b a ab +=( 1 ).三、计算题1、求[136,221,391]=?（8分）解 [136,221,391]=[[136,221],391] =[391,17221136?] =[1768,391] = 173911768? =104?391=40664.2、求解不定方程144219=+y x .（8分）解：因为（9，21）=3，1443，所以有解；化简得4873=+y x ；考虑173=+y x ，有1,2=-=y x ，所以原方程的特解为48,96=-=y x ，因此，所求的解是Z t t y t x ∈-=+-=,348,796。
2009-2017全国高中数学联赛分类汇编第02讲：初等数论1、（2010一试8）方程2010=++z y x 满足z y x ≤≤的正整数解(,,)x y z 的个数是. 【答案】336675易知 100420096100331⨯=+⨯+k ，所以110033*********-⨯-⨯=k200410052006123200910052006-⨯=-⨯+-⨯=，即3356713343351003=-⨯=k .从而满足z y x ≤≤的正整数解的个数为33667533567110031=++.2、（2011一试8）已知=n a C ())95,,2,1(2162003200 =⎪⎪⎭⎫⎝⎛⋅⋅-n nnn ，则数列}{n a 中整数项的个数为． 【答案】15 【解析】=n a C65400320020023n nn--⋅⋅．要使)951(≤≤n a n 为整数，必有65400,3200nn --均为整数，从而4|6+n ． 当=n 2,8,14,20,26,32,38,44,50,56,62,68,74,80时，3200n -和65400n-均为非负整数，所以n a 为整数，共有14个．当86=n 时，=86a C 5388620023-⋅⋅，在C !114!86!20086200⋅=中，!200中因数2的个数为1972200220022002200220022002200765432=⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡， 同理可计算得!86中因数2的个数为82，!114中因数2的个数为110，所以C 86200中因数2的个数为511082197=--，故86a 是整数．当92=n 时，=92a C 10369220023-⋅⋅，在C !108!92!20092200⋅=中，同样可求得!92中因数2的个数为88,!108中因数2的个数为105,故C 86200中因数2的个数为410588197=--，故92a 不是整数． 因此，整数项的个数为15114=+．3、（2015一试8）对四位数(19,0,,9)abcd a b c d ≤≤≤≤,若,,a b b c c d ><>,则称abcd 为P 类数,若,,a b b c c d <><,则称a b c d 为Q 类数,用()N P 与()N Q 分别表示P 类数与Q 类数的个数,则()()N P N Q -的值为【答案】28511..dcba B dcba B A abcd A B ∈∈故反之，每个唯一对应于中的元素这建立了与之间的一一对应，因此有 010()()||||||||||||.N P N Q A B A A B A -=-=+-=00||:0,0,19b,A abc A b ∈⋅⋅⋅下面计算对任一四位数可取，，，对其中每个99b a b c <≤<≤由及知，a 和c 分别有9-b 种取法，从而992200191019|=(9)26|85.b k b k ==⨯⨯-===∑∑A ()()285.N P N Q -=因此，4、（2016一试8）设4321,,,a a a a 是1，2，…，100中的4个互不相同的数，满足2433221242322232211)())((a a a a a a a a a a a a ++=++++则这样的有序数组),,,(4321a a a a 的个数为 . 【答案】40【解析】由柯西不等式知，2433221242322232211)())((a a a a a a a a a a a a ++≥++++，等号成立的充分必要条件是433221a a a a a a ==，即4321,,,a a a a 成等比数列.于是问题等价于计算满足{1,2,3,},,,{4321⊆a a a a …,100}的等比数列4321,,,a a a a 的个数.设等比数列的公比1≠q ，且q 为有理数.记mnq =，其中n m ,为互素的正整数，且n m ≠. 先考虑m n >的情况.此时331314)(m n a m n a a ==，注意到33,nm 互素，故31m a l =为正整数. 相应地，4321,,,a a a a 分别等于l n l mn nl m l m 3223,,,，它们均为正整数.这表明，对任意给定的1>=mnq ，满足条件并以q 为公比的等比数列4321,,,a a a a 的个数，即为满足不等式1003≤l n 的正整数l 的个数，即]100[3n.由于10053>，故仅需考虑34,4,23,3,2=q 这些情况，相应的等比数列的个数为20113312]64100[]64100[]27100[]27100[]8100[=++++=++++. 当m n <时，由对称性可知，亦有20个满足条件的等比数列4321,,,a a a a . 综上可知，共有40个满足条件的有序数组),,,(4321a a a a .5、（2017一试4）若一个三位数中任意两个相邻数码的差均不超过1，则称其为“平稳数”.平稳数的个数是. 【答案】756、（2009二试3）设k ， l 是给定的两个正整数．证明：有无穷多个正整数m k ≥，使得C k m 与l 互素． 【解析】证法一：对任意正整数t ，令(!)m k t l k =+⋅⋅．我们证明()C 1k m l =，． 设p 是l 的任一素因子，只要证明：p/|C k m ．若p /|k !，则由1!C ()k k mi k m k i ==-+∏1[((!)]k i i tl k =≡+∏1ki i =≡∏()1!mod k p α+≡．及|!p k α，且pα+1/|k !，知|!C k m p k α且1α+p /|!C k m k ．从而p/|C km ．证法二：对任意正整数t ，令2(!)m k t l k =+⋅⋅，我们证明()C 1k m l =，． 设p 是l 的任一素因子，只要证明：p/|C k m ． 若p /|k !，则由 1!C ()==-+∏kkmi k m k i 21[((!)]ki i tl k =≡+∏1ki i =≡∏()!mod k p ≡．即p 不整除上式，故p/|C k m ．若|!p k ，设1α≥使|!p k α，但1/|!p k α+．12|(!)p k α+．故由11!C ()k kmi k m k i -==-+∏21[((!)]ki i tl k =≡+∏1ki i =≡∏()1!mod k p α+≡,及|!p k α，且pα+1/|k !，知|!C k m p k α且1α+p /|!C k m k ．从而p/|C km ．7、（2009二试4）在非负数构成的39⨯数表111213141516171819212223242526272829313233343536373839x x x x x x x x x P x x x x x x x x x x x x x x x x x x ⎛⎫⎪= ⎪ ⎪⎝⎭中每行的数互不相同，前6列中每列的三数之和为1，1728390x x x ===，27x ，37x ，18x ，38x ，19x ，29x 均大于．如果P 的前三列构成的数表111213212223313233x x x S x x x x x x ⎛⎫ ⎪= ⎪ ⎪⎝⎭满足下面的性质()O ：对于数表P 中的任意一列123k k k x x x ⎛⎫ ⎪⎪ ⎪⎝⎭（1k =，2，…，9）均存在某个{}123i ∈，，使⑶{}123min ik i i i i x u x x x =≤，，．求证：（ⅰ）最小值{}123min i i i i u x x x =，，，1i =，2，3一定自数表S 的不同列． （ⅱ）存在数表P 中唯一的一列***123k k k x x x ⎛⎫⎪⎪ ⎪ ⎪⎝⎭，*1k ≠，2，3使得33⨯数表***111212122231323k k k x x x S x x x x x x ⎛⎫ ⎪'= ⎪ ⎪ ⎪⎝⎭仍然具有性质()O ．【解析】（ⅰ）假设最小值{}123min i i i i u x x x =，，，1i =，2，3不是取自数表S 的不同列．则存在一列不含任何i u ．不妨设2i i u x ≠，1i =，2，3．由于数表P 中同一行中的任何两个元素都不等，于是2i i u x <，1i =，2，3．另一方面，由于数表S 具有性质()O ，在⑶中取2k =，则存在某个{}0123i ∈，，使得002i i x u ≤．矛盾．（ⅱ）由抽届原理知，{}1112min x x ，，{}2122min x x ，，{}3132min x x ，中至少有两个值取在同一列．不妨设{}212222min x x x =，，{}313232min x x x =，．由前面的结论知数表S 的第一列一定含有某个i u ，所以只能是111x u =．同样，第二列中也必含某个i u ，1i =，2．不妨设222x u =．于是333u x =，即i u 是数表S 中的对角线上数字． 111213212223313233x x x S x x x x x x ⎛⎫ ⎪= ⎪⎪⎝⎭下面证明33⨯数表***111212122231323k k k x x x S x x x x x x ⎛⎫ ⎪'= ⎪ ⎪ ⎪⎝⎭具有性质()O ．从上面的选法可知{}{}*1212:min min i i i i i ik u x x x x x '==，，，，(13)i =，．这说明 {}*111211min k x x x u >，≥，{}*313233min k x x x u >，≥．又由S 满足性质()O ．在⑶中取*k k =，推得*22k x u ≤，于是{}**2212222min k k u x x x x '==，，．下证对任意的k M ∈，存在某个1i =，2，3使得i ik u x '≥．假若不然，则{}12min ik i i x x x >，，1i =，3且*22k k x x >．这与*2k x 的最大性矛盾．因此，数表S '满足性质()O ． 下证唯一性．设有k M ∈使得数表 111212122231323k k k x x x S x x x x x x ⎛⎫ ⎪= ⎪⎪⎝⎭具有性质()O ，不失一般性，我们假定{}111121311min u x x x x ==，，⑷{}221222322min u x x x x ==，，{}331323333min u x x x x ==，， 3231x x <．由于323x x<，2221x x <及（ⅰ），有 {}11112111min k u x x x x ==，，．又由（ⅰ）知：或者()a {}3313233m i n k k u x x x x ==，，，或者 {}2212222()min k k b u x x x x ==，，． 如果()a 成立，由数表 S具有性质()O ，则{}11112111min k u x x x x ==，，， ⑸ {}22122222min k u x x x x ==，，， {}3313233min k ku x x x x ==，，． 由数表 S 满足性质()O ，则对于3M ∈至少存在一个{}123i ∈，，使得 *i ik u x ≥．由*k I ∈及⑷和⑹式知， *1111k x x u >=， *3323k x x u >=．于是只能有 *222k k x u x =≤．类似地，由S '满足性质()O 及k M ∈可推得*222k k x u x '=≤．从而*k k =．8、（2010一试11）证明：方程02523=-+x x 恰有一个实数根r ，且存在唯一的严格递增正整数数列}{n a ，使得+++=32152a a a r r r.若存在两个不同的正整数数列 <<<<n a a a 21和 <<<<n b b b 21满足52321321=+++=+++ b b b a a a r r r r r r ， 去掉上面等式两边相同的项，有 +++=+++321321t t t s s s r r r r r r，这里 <<<<<<321321,t t t s s s ，所有的i s 与j t 都是不同的. 不妨设11t s <，则 ++=++<21211t t s s s r r r r r，112111111121211=--<--=++≤++<--rr r r r s t s t ，矛盾.故满足题设的数列是唯一的.9、（2010二试2）设k 是给定的正整数，12r k =+．记(1)()()f r f r r r ==⎡⎤⎢⎥，()()l f r =(1)(()),2l f f r l -≥．证明：存在正整数m ，使得()()m f r 为一个整数．这里，x ⎡⎤⎢⎥表示不小于实数x 的最小整数，例如：112⎡⎤=⎢⎥⎢⎥，11=⎡⎤⎢⎥．【解析】记2()v n 表示正整数n 所含的2的幂次．则当2()1m v k =+时，()()m f r 为整数． 下面我们对2()v k v =用数学归纳法．当0v =时，k 为奇数，1k +为偶数，此时()111()1222f r k k k k ⎛⎫⎡⎤⎛⎫=++=++ ⎪ ⎪⎢⎥⎝⎭⎢⎥⎝⎭为整数． 假设命题对1(1)v v -≥成立．对于1v ≥，设k 的二进制表示具有形式1212222v v v v v k αα++++=+⋅+⋅+ ， 这里，0i α=或者1，1,2,i v v =++ ． 于是 ()111()1222f r k k k k ⎛⎫⎡⎤⎛⎫=++=++ ⎪ ⎪⎢⎥⎝⎭⎢⎥⎝⎭2122k k k =+++ 11211212(1)2()222v v v v v v v ααα-++++=+++⋅++⋅+++ 12k '=+， ① 这里1121122(1)2()22v v v v v v v k ααα-++++'=++⋅++⋅+++ . 显然k '中所含的2的幂次为1v -．故由归纳假设知，12r k ''=+经过f 的v 次迭代得到整数，由①知，(1)()v f r +是一个整数，这就完成了归纳证明．10、（2010二试4）一种密码锁的密码设置是在正n 边形12n A A A 的每个顶点处赋值0和1两个数中的一个，同时在每个顶点处涂染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同．问：该种密码锁共有多少种不同的密码设置？设标有a 的边有2i 条，02n i ⎡⎤≤≤⎢⎥⎣⎦，标有b 的边有2j 条，202n i j -⎡⎤≤≤⎢⎥⎣⎦．选取2i 条边标记a 的有2in C 种方法，在余下的边中取出2j 条边标记b 的有22jn i C -种方法，其余的边标记c ．由乘法原理，此时共有2in C 22j n i C -种标记方法．对i ，j 求和，密码锁的所有不同的密码设置方法数为 222222004n n i i j nn i i j C C -⎡⎤⎡⎤⎢⎥⎢⎥⎣⎦⎣⎦-==⎛⎫ ⎪ ⎪ ⎪⎝⎭∑∑． ① 这里我们约定001C =．当n 为奇数时，20n i ->，此时22221202n i jn i n ij C-⎡⎤⎢⎥⎣⎦---==∑． ②代入①式中，得()()2222222221222000044222n n i n n i j i n i i n i n n i n n i j i i C C C C -⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦----====⎛⎫ ⎪== ⎪⎪⎝⎭∑∑∑∑ 022(1)(21)(21)nnkn kk n kk n n nn k k C C --===+-=++-∑∑31n =+．222222004n n i i j n n i i j C C -⎡⎤⎡⎤⎢⎥⎢⎥⎣⎦⎣⎦-==⎛⎫ ⎪= ⎪ ⎪⎝⎭∑∑()122210412n i n i n i C ⎡⎤-⎢⎥⎣⎦--=⎛⎫ ⎪⨯+ ⎪ ⎪⎝⎭∑()2221024233n i n i n n i C ⎡⎤⎢⎥⎣⎦--==+=+∑． 综上所述，这种密码锁的所有不同的密码设置方法数是：当n 为奇数时有31n +种；当n 为偶数时有33n+种．11、（2011二试2）证明：对任意整数4≥n ，存在一个n 次多项式0111)(a x a x a x x f n n n ++++=--具有如下性质：（1）110,,,-n a a a 均为正整数；（2）对任意正整数m ，及任意)2(≥k k 个互不相同的正整数k r r r ,,,21 ，均有)()()()(21k r f r f r f m f ≠．【解析】令 2)()2)(1()(++++=n x x x x f ， ①将①的右边展开即知)(x f 是一个首项系数为1的正整数系数的n 次多项式． 下面证明)(x f 满足性质（2）．对任意整数t ，由于4≥n ，故连续的n 个整数n t t t +++,,2,1 中必有一个为4的倍数，从而由①知)4(mo d 2)(≡t f ．因此，对任意)2(≥k k 个正整数k r r r ,,,21 ，有 )4(m od 02)()()(21≡≡k k r f r f r f ． 但对任意正整数m ，有)4(m od 2)(≡m f ，故)4)(m od ()()()(21k r f r f r f m f ≡/， 从而)()()()(21k r f r f r f m f ≠． 所以)(x f 符合题设要求．12、（2011二试3）设)4(,,,21≥n a a a n 是给定的正实数，n a a a <<< 21．对任意正实数r ，满足)1(n k j i r a a a a j k ij ≤<<≤=--的三元数组),,(k j i 的个数记为)(r f n ．证明：4)(2n r f n <．因此，当n 为偶数时，设m n 2=，则有∑∑∑-=-=-=+==121212)()()()(m mj j m j j n j j n r g r g r g r f2)1(2)1()2()1(1212-+-=-+-≤∑∑-+==m m m m j m j m m j m j 4222n m m m =<-=．当n 为奇数时，设12+=m n ，则有∑∑∑+==-=+==mm j jmj j n j j n r gr g r g r f 21212)()()()(∑∑+==-++-≤mm j m j j m j 212)12()1(422n m <=．13、（2011二试4）设A 是一个93⨯的方格表，在每一个小方格内各填一个正整数．称A 中的一个)91,31(≤≤≤≤⨯n m n m 方格表为“好矩形”，若它的所有数的和为10的倍数．称A 中的一个11⨯的小方格为“坏格”，若它不包含于任何一个“好矩形”．求A 中“坏格”个数的最大值． 【解析】首先证明A 中“坏格”不多于25个．用反证法．假设结论不成立，则方格表A 中至多有1个小方格不是“坏格”．由表格的对称性，不妨假设此时第1行都是“坏格”．设方格表A 第i 列从上到下填的数依次为9,,2,1,,, =i c b a i i i ．记9,,2,1,0,)(,11=+==∑∑==k c b T a S ki i i k ki i k ，这里000==T S ．即第2行至第3行、第1+m 列至第n 列组成一个“好矩形”，从而至少有2个小方格不是“坏格”，矛盾． 类似地，也不存在90,,≤<≤n m n m ，使)10(m od n n m m T S T S +≡+．因此上述断言得证．故)10(mod 59210)(999≡++++≡+≡≡∑∑∑=== k k k k k k k T S T S ，所以 )10(mod 055)(99090≡+≡+≡+∑∑∑===k k k k k k k T S T S ，矛盾！故假设不成立，即“坏格”不可能多于25个．另一方面，构造如下一个93⨯的方格表，可验证每个不填10的小方格都是“坏格”，此时有25个“坏格”．综上所述，“坏格”个数的最大值是25．14、（2012二试2）试证明：集合{}22,2,,2,n A = 满足（１）对每个a A ∈，及b N *∈，若21b a <-，则(1)b b +一定不是2a 的倍数；（２）对每个a A ∈（其中A 表示A 在Ｎ 中的补集），且1a ≠，必存在b N *∈，21b a <-，使(1)b b +是2a 的倍数．【解析】证明:对任意的a A ∈,设2,,ka k N *=∈则122,k a +=如果b 是任意一个小于21a -的正整数,则121b a +≤-则122k a m +=⋅下面给出(2)的三种证明方法: 证法一:令1,12,k b mx b y +=+=消去b 得12 1.k y mx +-=由于1(2,)1,k m +=这方程必有整数解;1002k x x ty y mt +⎧=+⎪⎨=+⎪⎩其中00,(,)t z x y ∈为方程的特解.把最小的正整数解记为(,),x y **则12k x *+<,故21,b mx a *=<-使(1)b b +是2a 的倍数．证法二:由于1(2,)1,k m +=由中国剩余定理知,同余方程组10(mod 2)1(mod )k x x m m +⎧=⎨=-⎩在区间1(0,2)k m +上有解,x b =即存在21,b a <-使(1)b b +是2a 的倍数． 证法三:由于(2,)1,m =总存在(,1),r r N r m *∈≤-使21(mod )r m =取,t N *∈使1,tr k >+则21(mod )tr m =存在1(21)(2)0,,tr k b q m q N +=--⋅>∈使021,b a <<- 此时1,21,k m b m ++因而(1)b b +是2a 的倍数．15.（2013二试4）（本题满分50分）设,n k 为大于1的整数，2k n <.证明：存在2k 个不被n 整除的整数，若将它们任意分成两组，则总有一组若干个数的和被n 整除. 【证明】先考虑n 为2的幂的情形.设2,1r n r =≥，则r k <.取3个12r -及23k -个1，显然这些数均不被n 整除.将这2k 个数任意分成两组，则总有一组中含2个12r -，它们的和为2r ，被n 整除.现在设n 不是2的幂，取2k 个数为22211,1,2,2,,2,1,2,2,,2k k ------- ， 因为n 不是2的幂，故上述2k 个数均不被n 整除.若可将这些数分成两组，使得每一组中任意若干个数的和均不能被n 整除.不妨设1在第一组，由于（-1）+1=0，被n 整除，故两个-1必须在第二组；因（-1）+（-1）+2=0，被n 整除，故2在第一组，进而推出-2在第二组.现归纳假设1,2,,2l 均在第一组，而1,1,2,,2l ---- 均在第二组，这里12l k ≤<-，由于()()()()1112220l l +-+-+-++-+= ，被n 整除，故12l +在第一组，从而12l +-在第二组.故由数学归纳法可知，221,2,2,,2k - 在第一组，221,1,2,2,,2k ------ 在第二组.最后，由于()()()()21112220k k ---+-+-++-+= ，16、（2014二试4）（本题满分50分）设整数122014,,,2014x x x 模互不同余，122014,,,y y y 整数模2014也互不同余.证明：可将122014,,,y y y 重新排列为122014,,,z z z ，使得112220142014,,,x z x z x z +++ 模4028互不同余.【证明】(mod2),12.,i i y i k i k i ≡≡≤≤记k=1007,不妨设x 对每个整数 1,+(mod4),,i i i k i k i i i k i k i k y x y k y y ++++≤≤≡+==若x 不则令z z ；否则，,.i i k i k i z y z y ++==令如果是前一种情形，则++=(mod4)i i i i i k i k i k i k z y x y x z k ++++=≡++x x 不 如果是后一种情形，则也有+++=(mod4)i i i i k i k i i k i k z y x y x z k +++=≡++x x 不++(mod4),+(mod4),i i i k i k i i k i k i y x y k y x y k +++≡+≡+若不然，我们有x x 22(mod4),(mod2)i i k i i k x x k x x k ++≡≡两式相加可得于是，但122014,,,2014=2)(mod2),i i k x x x k x k +≡ 模（互不同余，特别地，x 不矛盾. 122122,,,y ,,,k k z z z y y 由上述构造方法知是的排列.记 1122,1,2,,2.w ,,,4.i i k x z i k w w k =+= w 下面模互不同余≤≤这只需证明，对任意整数i,j,1i<j k,w ,,,4i j i k j k w w w k ++*模两两不同余.()注意，前面的构造方式已保证(mod4),(mod4).()i i k j j k w k w k ++≡≡**w 不w 不,.i i j j z y z y ==情形一：且则由前面的构造方式可知 2(mod2),2(mod2).i i k j j k w i k w j k ++≡≡≡≡w w 22(mod2),2i j j k i j k w w k +≡由于不故易知与w 及模 j 24i k j k w w w k k ++不同余，与及模不同余，从而模更***不同余，再结合（）可见（）得证.,(,i i j j k i i k j i z y z y z y z y ++====情形三：且且的情形与此相同）.则由前面的构造方式可知2(mod2),2(mod2).i i k j j k w i k w j k k ++≡≡≡≡+w w22(mod2),22(mod2),k i j k i j k k ≡+≡+由于是奇数，故不更有不+22i j j k i k j j k w w k w w k ++因此仍然有w 与及模不同余，w 与及模不同余.*从而（）得证.因此本题得证.17、（2015二试4）(本题满分50分)求具有下述性质的所有正整数k :对任意正整数(1)1,2k n n -+不整除()!!kn n .22(()!)(!),1kn v kn n v n -≥-进而由（）知，本题等价于 ≥求所有正整数k,使得s(kn)s(n)对任意正整数n 成立.(0,1,2,).a a =⋅⋅⋅我们证明，所有符号条件的k 为2(2)()a S n S n n =一方面，由于对任意正整数成立，故2.a k =符合条件 22,0,1.a k k q a q =⋅≥另一方面，若不是的方幂，设是大于的奇数)().)=2)(),a n S kn S n S kn S qn S qn <=下面构造一个正整数，使得（因为（（,)().m q m S m S q<因此问题等价于我们选取的一个倍数使得（2)1,,21(mod ).(u q u q =≡由（，熟知存在正整数使得事实上，).)u q ϕ由欧拉定理知，可以取（12122+2++2,0, 2.t t q t αααααα⋅⋅⋅=<<⋅⋅⋅<≥设奇数的二进制表示为1122+2++22,t t tu m S αααα-+=⋅⋅⋅+取则（m)=t,且 (21)0(mod ).t tu q α-≡m=q+2我们有(`1)21211212(122)t t tu u u t um q q q αα---=+⋅=+⋅++⋅⋅⋅+102112.t ut lu l q α-+=-=+⋅∑212102,u u u u q q --<<由于故正整数的二进制表示中的最高次幂小于，由此2121(01),22t tu u lu ju i j i j t q qαα++--≤<≤-⋅⋅易知，对任意整数，数与 的二进制表示中没有相同的项.210,20,1,,1)1tu lu t l t q αα+->⋅=⋅⋅⋅-又因为故（的二进制表示中均不包含，故212)1()(),u m S S t t S m q q-=+⋅>=由（）可知（.m 因此上述选取的满足要求(0,1,2,).a a =⋅⋅⋅综合上述的两个方面可知，所求的k 为218、（2016二试3）（本题满分50分）给定空间中10个点，其中任意四点不在一个平面上，将某些点之间的线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值. 【解析】以这10个点为顶点，所连线段为边，得到一个10界简单图G ，我们证明G 的边数不超过15.边，否则就形成三角形，所以，121,,,n v v v +⋅⋅⋅之间恰有n 条边.对每个j (210)n j +≤≤，j v 至多与21,,n v v +⋅⋅⋅中的一个顶点相邻（否则设j v 与,(21)s t v v s t n ≤<≤+）相邻，则1,,,s j t v v v v 就对应了一个空间四边形的四个顶点，这与题设条件矛盾，从而21,,n v v +⋅⋅⋅与210,,n v v +⋅⋅⋅之间的边数至多10(1)9n n -+=-条.在210,,n v v +⋅⋅⋅这9n -个顶点之间，由于没有三角形，由托兰定理，至多2(9)[]4n -条边，因此G 的边数22(9)(9)25(9)[]9[]9[]15444n n k n n --≤+-+=+≤+=如图给出的图共有15条边，且满足要求，综上所述，所求边数的最大值为15.19、（2017二试3）（本题满分50分）将33×33方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等，若相邻两个小方格的颜色不同，则称它们的公共边为“分隔边”.试求分隔边条数的最小值.解：记分隔边的条数为L ，首先，将方格纸按如图分成三个区域，分别染成三种颜色，粗线上均为分隔边，此时共有56个分隔边，即L=56.1233123312356.,.,.A (A ),B ().,,.,().1,A .A ,)0,,).((ii i i j j j i j i j i j L A A B B n n B c c c c n c c c c B c n A δδ≥⎧⎪=⎨⎪⎩ 下面证明将方格纸的行从上至下依次记为A ，，列从左至右依次记为B ，，行中方格出现的颜色数记为列中方格出现的颜色个数记为三种颜色分别记为对于一种颜色设是含有色方格的行数与列数之和记若行含有色方格（否则.类似地定义（于是3333311133331112)())(A ,),))(A ,),))().133=3633363,n()38,n()391,i i i j i j i i j i j i j j j i j j j j j j n B c B c c B c n c c c a b c a b ab c a b c j δδδδ======+=+=+=⋅≥=+≥≥>≥=∑∑∑∑∑∑（（（（由于染色的方格有个，设含有色方格的行有个，列有个，则色的方格一定在这行和列的交叉方格中，因此从而故，33333311131112,3.1()()1()1(()1)(()1)(()())66(2)(()66.31.c 33c i i i j j i i i i i i i j j A n A n A B n B L n A n B n A n B n c ====--≥-+-=-=-∑∑∑∑（）由于在行中有种颜色的方格，因此至少有条分隔边，同理在列中，至少有条分隔边。
