loading目录
四川省成都市第七中学高一年级竞赛数学数论专题 4第一次考试题 四川省成都市第七中学高一年级竞赛数学数论专题 8.第二次考试题 四川省成都市第七中学高一年级竞赛数学数论专题 15.第三次考试题 高一竞赛数论专题1.整除
高一竞赛数论专题 4.第一次考试题
(满分180分)
1.(满分40分)设p是素数,a,b是整数,a?b(modp),证明：a?b(modp).
2.(满分40分)设p是奇素数,证明：p
23.(满分50分)设m?d0?d1?3?d2?3?pppp2?(p?k)!(k?1)!.(其中n!?n(n?1)k?1p?12?1,约定0!?1.)
?dn?3n为一个正整数的平方,且di?{0,1,2},i?0,1,2,,n.
证明：至少有一个di?1.
4.(满分50分)设p是大于1的奇数,若4(p?1)!?4??p(modp(p?2)).证明：p,p?2是孪生素数. (孪生素数是指相差为2的一对素数).
高一竞赛数论专题
4.第一次考试题解答
(满分180分)
1.(满分40分)设p是素数,a,b是整数,a?b(modp),证明：a?b(modp).
证明：因为p是素数,所以由Fermat小定理知道a?a(modp),b?b(modp). 于是a?b(modp).20分
p?Cp(pq)p.
pppppp20pp?12p?2从而a?b?pq,q?Z.ap?(b?pq)p?Cpb?C1pq?Cpb(pq)2?pb0pp?1所以(b?pq)p?Cpb?C1pq?bp?bp?1p2q?bp(modp2) pb所以a?b(modp).
2.(满分40分)设p是奇素数,证明：p
证明：因为(p?1)!?(p?1)(p?2)又(p?1)(p?2)于是(p?1)!?(?1)pp240分
?(p?k)!(k?1)!.(其中n!?n(n?1)k?1p?12?1,约定0!?1.)
(p?(k?1))(p?k)!
(?(k?1))?(?1)k?1(k?1)!(modp).
20分
(p?(k?1))?(?1)(?2)k?1(p?k)!(k?1)!(modp).由Wilson定理知(p?1)!??1(modp). 所以(p?k)!(k?1)!?(?1)(modp). 从而
k?(p?k)!(k?1)!??(?1)k?1k?1p?1p?1k?0(modp)(p?1是偶数).
所以p
?(p?k)!(k?1)!k?1p?140分
23.(满分50分)设m?d0?d1?3?d2?3??dn?3n为一个正整数的平方,且di?{0,1,2},i?0,1,2,,n.
证明：至少有一个di?1.
2证明：因为m?d0?d1?3?d2?3??dn?3n为一个正整数的平方,所以d0,d1,d2,,dn不全为0.
对于任意的x,x?0,1,?1(mod3),所以x?0,1(mod3). 所以m?d0?0,1(mod3).所以d0?0或1.
2若d0?0,则m?d1?3?d2?3?2?dn?3n.从而3|m.因为m?t2,t?N*.所以3|t2.从而3|t,于是32|m.
?dn?3n?32(d2?d3?3??dn?3n?2) .
2于是3|d1,所以d1?0.则m?d2?3?于是d2?d3?3??dn?3n?2是一个正整数的平方,按上面的推导方法可得d2?0.
如此下去,可以推导出d0?d1?d2?若d0?1,则结论成立. 所以d0?1. 至少有一个di?1.
?dn?0.(矛盾)
4.(满分50分)设p是大于1的奇数,若4(p?1)!?4??p(modp(p?2)).证明：p,p?2是孪生素数. (孪生素数是指相差为2的一对素数).
证明：引理 若(p?1)!??1(modp).则p是素数.
引理的证明：假设p不是素数,则p为合数,于是p?ab.其中1?a,b?p.于是a,b必是1,2,某个数.若a?b,则p|(p?1)!矛盾.若a?b,则m?a. 当a?2时,a?2a因为1,2,22,m?1中的
,a2?1一定含有a,2a,所以a2|(a2?1)!矛盾.
当a?2时,p?4.所以(p?1)!?3!??1(modp).矛盾. 所以假设错误, p是素数.
回到原题,因为4(p?1)!?4??p(modp(p?2)).所以p(p?2)|4(p?1)!?4?p.
10分
因为p是奇数,所以(p,p?2)?(p,2)?1.
于是p|4(p?1)!?4?p且(p?2)|4(p?1)!?4?p.
因为p|4(p?1)!?4?p,所以p|4[(p?1)!?1],p是奇数,(p,4)?1.p|(p?1)!?1. 即(p?1)!??1(modp). 由引理知道p是素数.
因为(p?2)|4(p?1)!?4?p,所以(p?2)|4(p?1)!?2,p是奇数,(p,2)?1.(p?2)|2(p?1)!?1. 即2(p?1)!??1(modp?2).
于是(?1)(?2)(p?1)!??1(modp?2).也就是(p?2?1)(p?2?2)(p?1)!??1(modp?2). 即((p?2)?1)!?(p?1)!?(p?1)p(p?1)!??1(modp?2). 由引理知道p?2是素数. 所以p,p?2是孪生素数.
50分 30分
高一竞赛数论专题 8.第二次考试题
(满分180分)
1.(满分40分)设k是非负整数,记号a||b表示b恰被a的k次方整除,即a|b,askkk?1b.
设m,s都是大于1的正整数,且2||m?1.证明：对所有的正整数n都有2n?s||m2?1成立.
2.(满分40分)证明：对每个素数p,有无穷多个正整数n,使得p|2?n.
nn
3.(满分50分)证明：对于任意的正整数k,(k!)
4.(满分50分)以S(n,p)表示(1?x)的展开式中不可被p整除的系数的个数. 证明：S(2018
2017n2j!为整数. ?j?0(j?k)!k?1,2017)可被2018整除.
高一竞赛数论专题 7.第二次考试题解答
1.(满分40分)设k是非负整数,记号a||b表示b恰被a的k次方整除,即a|b,askkk?1b.
设m,s都是大于1的正整数,且2||m?1.证明：对所有的正整数n都有2n?s||m2?1成立. 证明：方法1 因为2||m?1.所以2|m?1,2我们用数学归纳法证明.
2s22s2s?1s?1s?1当n?1时,m?1?(2q0?1)?1?2q0?2q0?2?q0(2q0?1). s?1因为q0是正奇数,所以2q0(2q0?1).所以2nsss?1m?1.于是m?2sq0?1,q0是正奇数.
s?1|m2?1,2s?2m2?1.即2s?1||m2?1.
所以当n?1时,结论成立.
假设当n?k时,结论成立,即2k?s||m2?1.也就是2k?s|m2?1,2k?1?s于是m2?2k?sqk?1,qk是正奇数. 当n?k?1时,m2k?1kkkm?1.
2k2?1?(m2)2?1?(2k?sqk?1)2?1?22k?2sqk?2k?1?sqk?2k?1?sqk(2k?1?sqk?1).
k?1kk?1?sqk?1).所以2k?1?s|m2因为qk是正奇数,所以2qk(2?1,2k?2?sm2?1.即2k?1?s||m2?1.
k?1k?1即当n?k?1时,结论成立.
于是对所有的正整数n都有2n?s||m2?1成立. 方法2：我们用数学归纳法证明. 当n?1时,m?1?(m?1)(m?1).
因为2||m?1,s?1,又2||2,所以2||m?1所以2所以当n?1时,结论成立.
ss?12n||m2?1.
假设当n?k时,结论成立,即2k?s||m2?1. 当n?k?1时,m2kk?1k?1?(m)?1?(m?1)(m?1).
kk?12k22k2k因为2k?s||m2?1,s?1,又2||2,所以2||m2?1,所以2k?1?s||m2即当n?k?1时,结论成立.
于是对所有的正整数n都有2n?s||m2?1成立.
方法3 一方面m2?1?(m?1)(m?1)(m2?1)sinn?1.
(m2?1)(m2?1).
,n?1).
n?2n?1由于2||m?1,则m为奇数.故2|m2?1(i?0,1,2,所以2|n?(mi?0n?12i?1).又2s|m?1.
n?1i?0in所以2n?s|(m?1)?(m2?1)?m2?1.
另一方面,m,s都是大于1的正整数,所以s?2,于是4|m?1.
m?1?m?1?2?(m?1)?(m2?1)?2?4q?2?2(2q?1).即2||m2?1(i?0,1,i2i2ii?1j,n?1).
j?0结合2||m?1,所以2n?s||m2?1.
方法4 m2?1?(m?1)(m?1)(m2?1)sknsn(m2?1).
?mk?1),所以2s|mk?1.
n?1因为2|m?1,对于任意的k?2,m?1?(m?1)(1?m?设m?1?2A,则2ks?1|A.
kk因为s?1,所以A是偶数.m?1?m?1?2?2A?2?2(A?1).A?1是奇数. 所以2||m?1.又2||m?1. 所以2
方法5 一方面,由于2||m?1,故m是奇数,则有2|m2?1(i?0,1,故2|(m?1)(m?1)n2siksn?s||(m?1)?(m?1)?m?1.
i?0n?12i2n,n?1).
(mi2n?1?1).又2s|m?1,所以2n?s|m2?1.
n另一方面,若存在i使得m2?1?k?2t,k是正奇数,t?2.
则m2?1?k?2t?2?2(k?2t?1?1),因为k?2iiit?1?1是奇数,所以2||(m2?1).
ii而2s|m?1,(m?1)|(m2?1),故2s|(m2?1)(s?1)与2||(m2?1)矛盾. 所以对i?0,1,2,s,n?1都有2||m2?1(i?0,1,ii,n?1).于是2n||(m?1)(m2?1)(m2?1).
n?1结合2||m?1.所以2n?s||m2?1(i?0,1,
,n?1).
2.(满分40分)证明：对每个素数p,有无穷多个正整数n,使得p|2?n. 证明：若p?2,取n为正偶数即可.
若p是奇素数,则(2,p)?1.于是由Fermat小定理知道2np?1n?1(modp).
n若取的正整数n满足n?s(p?1),则2?1(modp).为使得p|2?n.则正整数n还需满足n?1(modp). 即n?s(p?1)?1(modp).所以取n?(kp?1)(p?1)(k?1,2,则2?n?2n(kp?1)(p?1)).
?(kp?1)(p?1)?(2p?1)kp?1?(kp2?kp?p?1)?1kp?1?1?0(modp).
所以有无穷多个正整数n?(kp?1)(p?1)(k?1,2,所以命题得证.
法2：若p?2,取n为正偶数即可.
若p是奇素数,取n?(p?1)(p?1),k?0,1,2,k2)使得p|2n?n.
,
k2n?n?2(p?1)k(p?1)2?(p?1)k(p?1)2?(2p?1)(p?1)2k?1(p?1)?(p?1)k(p?1)2?1?1k(?1)2?0(modp).
3.(满分50分)证明：对于任意的正整数k,(k!)j!为整数. ?j?0(j?k)!证明：注意到n!的素因数分解式为n!?k?1?pp?n?(p,n)?n?,其中p是素数,?(p,n)???j?.j?1?p?
?所以只需证明(k!)2j!对任意的素数p的指数均为非负整数,即只要证明对于任意的素数的正整?(j?k)!j?0?k2?k?1??j?k??j??????. 数次幂P,有???????PP??P????j?0???k2?k?1??j?k??j???????1. 因为两边均为整数,所以只需证明????????P?j?0??P??P??k?1k2?k2?k?1?j?k?j?k?j?j??kk?1??j?k??j??????????即???????1????????????1 P?P?j?0?P?P?P?P??j?0Pj?0??P??P???k2?k?1?j?k?1?j?k?kk2注意到??,所以只需要证明???????????1.
Pj?0P?P?j?0?P?j?0?P?k?1然而,数0,1,k?1,k?1模P的余数之和显然不大于数k,k?1,,2k?1模P的余数之和,
?k2?k?1?j?k?1?j?k??k2??j?k?1?j?k?也即???????,再注意到???1.从而???????????1得证
j?0?P?j?0?P??P?j?0?P?j?0?P??P?对于任意的正整数k,(k!)2j!为整数. ?j?0(j?k)!k?1法2注意到n!的素因数分解式为n!?k?1?pp?n?(p,n)?n?,其中p是素数,?(p,n)???j?.j?1?p?
?所以只需证明(k!)2j!对任意的素数p的指数均为非负整数,即只要证明对于任意的素数p有?(j?k)!j?0?k2?k?1??j?k??j???pi?????pi???pi??.
??????j?0??
设k?t?p?s,t?N,0?s?p.
(r?1)pi?1j?rpiii?p?1??j?k??j??p?1??j?s??j????j?s??j??i??t???tp???i??i?????i??i????i???i?? ?ppppj?0??p?????j?0???????p????ii?tpi?tpi?s?1j?tpipi?s?1?j?0??j?s??j??p?1??j?s??j??i??i???i??+???i???i???tp?s. ??p??p??j?pi?s??p??p??i?s?1???j?k??j??s?1??j?k??j??s?1??j?s??j???j?s??j??i????t???sp???i??i?????i??i?????i??i????i???i?? ?ppppppj?0??p?????j?0??????j?0???????p?????j?s??sp???i?.
j?0?p?is?1s?1??j?k??j??2i?j?s?i于是???i???i???tp?st?sp???i?.
j?0??pj?0?p???p??k?1?j?s?p?s?1?j?s?s?1?j?s??2s?pi. ??pi????pi????i?j?0?j?0???j?pi?s?p?s?1i??j?k??j??2iii2ii2i所以???i???i???tp?st?sp?2s?p?(t?1)p?st?sp?2s?(t?1)p?2st?2s
j?0??p??p??k?1所以
??j?k??j??2i??i???i???(t?1)p?2st?2s?1. ?j?0??p??p??k?1?k2??t2(pi)2?2stpi?s2?2i?s2??tp?2st??i?. ?pi????ip?????p?所以
?k2?2i?s2?2is2s22ii2i?tp?2st??tp?2st??1?(t?1)p?2st?p??1?(t?1)p?2st?2s?1 ?pi??pi?iipp?????k2?k?1??j?k??j??所以?i?????i???i??.
?p?j?0??p??p??所以对于任意的正整数k,(k!)2j!为整数. ?(j?k)!j?0nk?14.(满分50分)以S(n,p)表示(1?x)的展开式中不可被p整除的系数的个数. 证明：S(20182017,2017)可被2018整除.
证明：设p为素数,而n?n0?n1?p?n2?p2?引理：S(n,p)?(n0?1)(n1?1)?nkpk?(nknk?1n1n0)p是n的p进制表达式.
(nk?1).
2017若引理已证明,因为2017是素数,2018因为2017|C2017(i?1,2,i?(1?2017)2017i??C2017?2017i. i?02017,2016),所以从第4项起,都可以被20174整除.
12223而前3项的和为1?C2017?2017?C2017?2017?1?2017?1008?2017.
20182017?1?20172?1008?20173?M?20174
20182017?(nknk?1n1n0)2017的n0?1,n1?0,n2?1,n3?1008.
S(20182017,2017)?(n0?1)(n1?1)(nm?1).
其中(n0?1)(n3?1)?(1?1)?(1008?1)?2018. 所以S(20182017,2017)可被2018整除.
n下面证明引理,(1?x)的展开式中x的系数为Cn,所以应该计算Cn?整除的个数.
iiin!(i?0,1,i!(n?i)!,n)中不可被pn?n0?n1?p?n2?p2?i?nkpk?(nknk?1iikCn(modp), kn1n0)p,i?i0?i1?p?i2?p2??ikpk?(ikik?1i1i0)p
i由Lucas定理知道Cn?Cn00Cn11i0i1所以CnCn01iik表示Cn可被p整除, Cn?0(modp)ki0i1CnCn10ikCn?1,2,k,p?1(modp)均表示不可被p整除.
注意到Ca?ba!(0?b?a?p)均不能被素数p整除.
b!(a?b)!于是Cn?n!(i?0,1,,n)中不可被p整除等价于i0?n0,i1?n1,i!(n?i)!(n0?1)(n1?1)(nk?1)个.
i,ik?nk.这个的i的个数为
所以S(n,p)?(n0?1)(n1?1)
(nk?1).所以引理得证.
法2 我们证明,若p是奇素数,S((p?1),p)可被p?1整除.
p(m?0,1,2,(1?x)(p?1)的展开式的每一项的系数为C(mp?1)pCm(p?1)pp,(p?1)p).
(p?1)p!?.考虑此式的分子分母中p的幂次. pm!((p?1)?m)!注意到p?3,f(p)?plnppp?1单调递减,所以(p?1)?p. ppp?(1?p)p??(1?p)p?m??m?pVp((1?p)!)???,V((1?p)?m)!)?,V(m!)????p??p?pi?. iippi?1?i?1?i?1????p(1?p)p(1?p)p?mm??i. 注意到iippp所以
01i?2i?2i?1i?1ppi?1i?1pp0i?2i?2Cp?C1p?C(1?p)pCp?Cpp?Cpp?(Cpp??Cpp)Cpp??Cppppp???pipipipi01i?2i?2i?1i?1ppi?1i?1pp0i?2i?2Cp?C1Cpp(1?p)pCp?Cpp?Cpp?(Cpp??Cpp)Cpp??Cpppp? ???iiiipppp注意到Cpp?kkp!pk的p的幂次为pk?1.
k!(p?k!i?1i?1pp01i?2i?2?(1?p)p?Cpp??Cpp(1?p)p?(1?p)p?Cp?Cpp?Cpp所以?.所以??. ????iiiiippppp????0若m模p的余数超过Cp?C1pp?iCip?2pi?2,
高一竞赛数论专题 15.第三次考试题
(满分180分)
1.设k为不等于1的整数,证明存在无穷多个正整数n,使得n?k不整除C2n.
2.是否存在正项数列{an}满足an?1?an?d(n),(其中d(n)表示n的正因数的个数)且至少连续两项为完全平方数.
n
3.设m,n为大于1的整数,用(a)n?a???n表示a(modn)的最小非负剩余.
n求maxmin
?a???a1,a2,,am0?k?n?(aj?1mj?k)n,其中最大遍及所有的m项整数数列.
高一竞赛数论专题 15.第三次考试题解答
(满分180分)
1.设k为不等于1的整数,证明存在无穷多个正整数n,使得n?k不整除C2n.
证明：当k?1时,k有素因子p,取n?p?k,其中正整数m足够大,使得n?0,这样的n有无穷多个. 我们证明对这些n有n?kn2nmnnpCC2,即2n. nmn???2n??n?(2n)!?.设素数p在C?中出现的幂次为则???2??pj???pj?.
(n!)2j?1?j?1???因为n?p?k,所以2n?2p?pmmm?1?2n??n?,所以j?m?1,?j??0,?j??0.
?p??p???2n??pm?k???n??m??2(pm?k)?于是?????j??2?j????????2?pj?? jpppj?1??????j?1??????m?m?j??2k???k??m???2k???k??m?j???2p??j??2p?2?j??????j??2?j??. j?1??p??p??j?1??p??p??mm???2k???k????2k???k?因为p|k,所以?所以 ???2?2?0.??j??????j??j?2??p??p???p??p?因为[2x]?[x]?[x?]?[x]?[x]?1?2[x]?1.
12???2k???k??mC2nn. 所以[2x]?2[x]?1.于是?????j??2?j???m?1?m.所以pj?2??p??p??m当k?0时,因为素数有无穷多个,故可取奇素数p?2|k|,令n?p?|k|,这样的正整数n有无穷多个. 我们证明对这些n有n?kn2nnnC2n,即pC2n.
???2n??n?(2n)!?.设奇素数p在C?中出现的幂次为则???2??pj???pj?.
(n!)2j?1?j?1???因为n?p?|k|,所以2n?2p?2|k|?3p?p.所以j?2,?2?2n??n??0,?0. ?j?j??p??p?所以????2n??n??2(p?|k|)??p?|k|???2|k|??|k|???2|k|??|k|??2??2?2??2?2??2??p????p???p??p???p??p? pp??????????????????因为p?2|k|,所以??2|k|??|k|??2|k|??|k|?npC于是所以?0,?0.???2?0.2n. ????????p??p??p??p?n于是我们证明了k为不等于1的整数,存在无穷多个正整数n,使得n?k不整除C2n.
2.是否存在正项数列{an}满足an?1?an?d(n),(其中d(n)表示n的正因数的个数)且至少连续两项为完全平方数.
解：不存在这样的正项数列{an}. 先证明d(n)?设n?p11p22??3n.
?sps(2?p1?p2??ps,pi都是素数,?i?N.于是d(n)?(1??1)(1??2)(1??s).
于是只需证明(1??1)(1??2)22?1?2(1??s)2?3n?3p1p29?14?2?3?sps?(p1)(p2)p343,s).
?sps.
下面分别证明(1)
9?14?2p1?(1??1)2,(2)p2?(1??2)2,(3)pi?i?(1??i)2(i?3,4,43先证明(1)
9?1p1?(1??1)2. 4因为
9?19?19p1??2.于是只需证明?2?1?(1??1)2. 444下面用数学归纳法证明.
当?1?0,?1?1,?2?2时显然成立. 假设当?1?k(k?2)时结论成立即当?1?k?1时,
29k?2?(1?k)2. 49?19k?19?2??2?2?(?2k)?2(1?k)2. 4442222注意到2(1?k)?(1?k?1)?2(1?k)?(k?2)?k?2?0, 所以
9?19k?19?2??2?2?(?2k)?2(1?k)2?(1?k?1)2?(1??1)2. 444所以当?1?k?1结论成立. 所以
9?19?1p1??2成立.我们不难发现当且仅当p1?2,?1?2时等号成立. 444?2p2?(1??2)2. 3再证明(2)
因为
4?24?24p2??3.于是只需证明?3?2?(1??2)2. 333下面用数学归纳法证明. 当?2?0,?2?1时显然成立. 假设当?2?k(k?1)时结论成立即当?2?k?1时,
24k?3?(1?k)2. 34?24k?14?3??3?3?(?3k)?3(1?k)2. 3332222注意到3(1?k)?(1?k?1)?3(1?k)?(k?2)?2k?2k?1?0. 所以
4?24k?14?3??3?3?(?2k)?3(1?k)2?(1?k?1)2?(1??2)2. 333所以当?2?k?1结论成立. 所以
4?24?2p2??3成立.我们不难发现当且仅当p2?3,?2?1时等号成立. 33?2最后证明(3)pii?(1??i)(i?3,4,,s).
?2因为i?3,所以pi?5.于是只需证明5i?(1??i). 下面用数学归纳法证明. 当?i?0时显然成立.
k2假设当?i?k(k?0)时结论成立即5?(1?k).
当?i?k?1时,5?i?5k?1?5(5k)?5(1?k)2?4(1?k)2?(2?2k)2?(2?k)2?(1?k?1)2?(1??i)2.
所以当?i?k?1结论成立.
所以5i?(1??i)成立.我们不难发现当且仅当?i?0时等号成立. 于是我们证明了d(n)?回到原题.
由an?1?an?d(n)知道an?a1?d(1)?d(2)?对于素数p有d(p)?2.又d(1)?1.
对于合数a有d(a)?2.于是an?1?1?2(n?2)?2n?2. 若存在连续两项为完全平方数设an?s,an?1?t(s,t?N).
22*?23n.
?d(n?1).
an?1?an?d(n)?1,即t2?s2?1,于是t?s?1.所以s?t?1.
所以3n?d(n)?an?1?an?t2?s2?t2?(t?1)2?2t?1?2an?1?1?22n?1. 即3n?22n?1.于是1?(22?3)n?22?3?1.矛盾. 所以不存在这样的正项数列{an}.
3.设m,n为大于1的整数,用(a)n?a???n表示a(modn)的最小非负剩余.
n求maxmin?a???a1,a2,,am0?k?n?(aj?1mj?k)n,其中最大遍及所有的m项整数数列.
,am)??(aj?k)n.
j?1m解：不妨设0?aj?n(1?j?m),令Sk(a1,a2,当k?0时,m项整数数列为{(aj)n}, 当k?1时,m项整数数列为{(aj?1)n},
当k?t时,m项整数数列为{(aj?t)n},
当k?m时,m项整数数列为{(aj?m)n}, 如果minSk(a1,a2,0?k?n,am)?S0(a1,a2,,am),
,am)(0?k?n).
则存在0?t?n使得St(a1,a2,,am)?Sk(a1,a2,令a?j?aj?t(1?j?m),于是(a?j)n?(aj?t)n,(a?j?1)n?(aj?t?1)n,(a?j?2)n?(aj?t?2)n,,
(a?j?m?t)n?(aj?m)n,(a?j?m?t?1)n?(aj)n,(a?j?m?t?2)n?(aj?1)n,(a?j?m)n?(aj?t?1)n. ?,a2?,于是我们有S0(a1?)?Sk(a1?,a2?,,am?)(0?k?n). ,am,
这表明对遍及所有的m项整数数列求
a1,a2,,am0?k?nmaxmin?(aj?k)n 可以限定在满足
j?1mminSk(a1,a2,,am)?S0(a1,a2,,am)的那些数列a1,a2,,am上求解.
?aj?k?n,若aj?n?k?aj?k?因为(aj?k)n?aj?k???n,所以(aj?k)n??a?k,若a?n?k.
j?n??j设aj?i的次数为?i.所以Sk??(aj?1mj?k)n??aj?mk?n(?n?1??n?2?j?1m??n?k).
,am)??aj.
j?1jm当且仅当?n?1??n?2???n?kmmk?(0?k?n)时minSk(a1,a2,1?k?nnn?1i?1n?1i?1n?1i?1n?1j?i,am)?S0(a1,a2,n?1n?1i?1j?ijn?1于是S0(a1,a2,,am)??aj??i?i??(n?i)?n?i=?(?1)?n?i????n?i????n?i
j?1j?1i?1因为?n?1??n?2???n?kmk?(0?k?n),所以S0(a1,a2,n?mj?,am)????n?i????.
j?1i?1j?1?n?n?1n?1考虑函数y?mm(n?1)m(n?1)x及矩形OABC,其中A(n?1,0),B(n?1,),C(0,). nnn?mj??((m,n)?1)?(m?1)(n?1). ???n?j?1?n?1由矩形的中心对称性知道2于是
?mj?1?((m?1)(n?1)?(m,n)?1). ???2j?1?n??mj?1,am)?????((m?1)(n?1)?(m,n)?1).
2j?1?n?n?1n?1所以S0(a1,a2,于是maxmina1,a2,,am0?k?n?(aj?k)n?j?1m1((m?1)(n?1)?(m,n)?1). 2选取?n?i??????n??则?n?1??n?2??mi??m(i?1)?,i?1,2,n??k,n.
??m?i??m?(i?1)???m?k?mk??n?k?????????n??n(0?k?n), ??nn??????i?1??,am)?S0(a1,a2,,am)??aj.
j?1m于是此时minSk(a1,a2,1?k?n于是数列a1,a2,?mi??m(i?1)?,i?1,2,,am有?n?i???????n??n?k,n个n?i.
且?n?1??n?2???m?i??m?(i?1)???m?k???n?k????????(0?k?n), ????n????n?i?1??n??mj?1,am)????n?i?????((m?1)(n?1)?(m,n)?1).
2j?1i?1j?1?n?n?1jn?1于是S0(a1,a2,所以maxmina1,a2,,am0?k?n?(aj?k)n?j?1m1((m?1)(n?1)?(m,n)?1). 2高一竞赛数论专题
1.整除
设a,b?Z,a?0.如果存在q?Z,使得b?aq,那么就说b可被a整除(或a整除b),记做a|b.且称b是a的倍数,a是b的约数(也可称为除数、因数).b不能被a整除就记做ab. 整除关系的基本性质 (1)a|b,b|c?a|c.
(2)a|b,a|c?对任意的x,y?Z,有a|bx?cy.
设a1,a2是两个不全为零的整数,如果d|a1且d|a2,那么d就称为a1和a2的公约数,我们把a1和a2的公约数中的最大的称为a1和a2的最大公约数,记做(a1,a2).若(a1,a2)?1,则称a1和a2是既约的,或是互素的.
设a1,a2是两个均不为零的整数,如果a1|l,且a2|l,那么l就称为a1和a2的公倍数,我们把a1和a2的公倍数中的最小的称为a1和a2的最小公倍数,记做[a1,a2].
1.设a1,a2是两个不全为零的整数,证明对任意整数q,都有(a1,a2)?(a1,a2?qa1).
2.设(a,b)?1,证明(1)若a|c,b|c则ab|c.
(2)若a|bc则a|c.
3.(Bezout定理)设a,b是不全为零的整数,证明(a,b)?1的充要条件是存在整数x,y使得ax?by?1.
4.证明对任意整数n,n?2n?n?2n能被120整除.
mn5.设m是一个大于2正整数,若存在正整数n使得2?1|2?1.求m的所有可能取值.
652
226.证明：正整数M是完全平方数的充要条件是对于任意正整数n,(M?1)?M,(M?2)?M,,
(M?n)2?M中至少有一项可以被n整除.
x4?1y4?1444?7.已知整数x,y满足x??1,y??1,且使得是整数,求证xy?1能被x?1整除. y?1x?1
3kk8.证明：对于任何自然数n和k,数f(n,k)?2n?4n?10都不能分解成若干个连续的自然数之积.
9.对于所有素数p和所有正整数n(n?p),证明：Cn???能被p整除.
10.(1)求所有的素数数列p1?p2?p?n??p??pn,使得?(1?k?1n1)是一个整数. pk*(2)是否存在n个大于1的不同正整数a1,a2,
,an,n?N,使得?(1?k?1n1)为整数?. ak2
mn(m,n)?1. 11.设m,n是正整数, 证明(2?1,2?1)?2
12.任给n?2,证明：存在n个互不相同的正整数,其中任意两个的和整除这n个数的积.
高一竞赛数论专题
1.整除解答
设a,b?Z,a?0.如果存在q?Z,使得b?aq,那么就说b可被a整除(或a整除b),记做a|b.且称b是a的倍数,a是b的约数(也可称为除数、因数).b不能被a整除就记做ab. 整除关系的基本性质 (1)a|b,b|c?a|c.
(2)a|b,a|c?对任意的x,y?Z,有a|bx?cy.
设a1,a2是两个不全为零的整数,如果d|a1且d|a2,那么d就称为a1和a2的公约数,我们把a1和a2的公约数中的最大的称为a1和a2的最大公约数,记做(a1,a2).若(a1,a2)?1,则称a1和a2是既约的,或是互素的.
设a1,a2是两个均不为零的整数,如果a1|l,且a2|l,那么l就称为a1和a2的公倍数,我们把a1和a2的公倍数中的最小的称为a1和a2的最小公倍数,记做[a1,a2].
1.设a1,a2是两个不全为零的整数,证明对任意整数q,都有(a1,a2)?(a1,a2?qa1).
证明：记(a1,a2)?d1,(a1,a2?qa1)?d2.
(a1,a2)?d1,即d1|a1,d1|a2.于是d1|a1,d1|a2?qa1.所以d1?d2.
(a1,a2?qa1)?d2,即d2|a1,d2|a2?qa1.于是d2|a1,d2|(a2?qa1)?qa1?a2.所以d2?d1.
所以d1?d2.命题得证.
2.设(a,b)?1,证明(1)若a|c,b|c则ab|c.
(2)若a|bc则a|c.
证明(a,b)?1,则1?ax?by.于是c?c?1?c(ax?by)?acx?bcy.
(1)a|c,b|c,则c?aq1,c?bq2.于是c?abq2x?baq1y?ab(q2x?q1y).所以ab|c. (2)a|bc,则a|acx?bcy.即a|c.
3.(Bezout定理)设a,b是不全为零的整数,证明(a,b)?1的充要条件是存在整数x,y使得ax?by?1.
证明：当a,b中有一个为零时,结论是显然的. 不妨设a,b都不为零,且|a|?|b|.
一方面若存在整数x,y使得ax?by?1.注意到(a,b)|a,(a,b)|b. 所以(a,b)|ax?by.即(a,b)|1.所以(a,b)?1.
另一方面设b?aq1?r1,0?r1?|a|,q1,r1为整数,若r1?0,则辗转相除到此为止；否则继续.
a?r1q2?r2,0?r2?r1,q2,r2为整数,若r2?0,则辗转相除到此为止；否则继续. r1?r2q3?r3,0?r3?r2,q3,r3为整数,若r3?0,则辗转相除到此为止；否则继续.
由于r1?r2?r3?且r1,r2,r3,均为自然数,所以经过有限步辗转相除可得rk?0.
即rk?3?rk?2qk?1?rk?1.rk?2?rk?1qk?rk(rk?0).
引理：设a,b是两个整数且a?0,b?aq?r,0?r?|a|,q,r为整数.则(a,b)?(a,r). 证明：因为(a,b)?(a,b?aq).又r?b?aq.所以(a,b)?(a,r). 回到原题：利用引理我们可得(a,b)?(a,r1)?(r1,r2)?所以(a,b)?(rk?1,0)?rk?1.
?(rk?2,rk?1)?(rk?1,rk).注意到rk?0.
由辗转相除的过程知道rk?1?rk?3?rk?2qk?1.
rk?2?rk?4?rk?3qk?2.
r3?r1?r2q3. r2?a?r1q2.
r1?b?aq1
所以r1?b?aq1,
r2?a?(b?aq1)q2?(1?q1q2)a?q2b,
r3?b?aq1?[(1?q1q2)a?q2b]q3?[(1?q1q2)q3?q1]a?(1?q2q3)b,
所以rk?1是a,b的线性组合即存在整数x,y使得rk?1?ax?by.即(a,b)?ax?by. 所以若(a,b)?1,则存在整数x,y使得ax?by?1.
4.证明对任意整数n,n?2n?n?2n能被120整除.
652542证明：n?2n?n?2n?n(n?2)?n(n?2)?n(n?2)(n?1)?n(n?2)(n?1)(n?1)(n?1)
652?n(n?2)(n?1)(n?1)(n2?4?5)?(n?2)n(n?1)(n?1)(n?2)2?5(n?1)n(n?1)(n?2).
5!|(n?2)n(n?1)(n?1)(n?2),4!|(n?1)n(n?1)(n?2),5!|5(n?1)n(n?1)(n?2),
所以n?2n?n?2n能被120整除.
mn5.设m是一个大于2正整数,若存在正整数n使得2?1|2?1.求m的所有可能取值.
652
mnnmm?1nm解: 因为2?1|2?1,所以2?1?2?1所以n?m(若不然,则n?m?1.于是2?1?2?1?2?1,
即m?2矛盾).
因为n?m,所以存在正整数q,r使得n?mq?r,0?r?m.
2n?1?2mq?r?1?2mq?r?2r?2r?1?2r(2mq?1)?2r?1?2r(2m?1)[(2m)q?1?mnmr因为2?1|2?1,所以2?1|2?1.从而2?1?2?1.
?2m?1]?2r?1.
rm注意到0?r?m.所以r?m?1.于是2m?1?1?2r?1?2m?1.即m?2矛盾.
所以不存在这样的m.
226.证明：正整数M是完全平方数的充要条件是对于任意正整数n,(M?1)?M,(M?2)?M,,
(M?n)2?M中至少有一项可以被n整除.
证明：(?)正整数M是完全平方数,则M?d.
2(M?i)2?M?(d2?i)2?d2?(d2?d?i)(d2?d?i).
d2?d?i对于i?1,2,2于是n|(M?i)?M.
,n是连续n个正整数,所以一定存在某个i使得n|d2?d?i.
22所以对于任意正整数n,(M?1)?M,(M?2)?M,,(M?n)2?M中至少有一项可以被n整除.
(?)假设正整数M不是完全平方数,则M中一定有一个素因数p,它的指数是奇数即存在正整数k使得p2k?1|M,p2kM.
22因为对于任意正整数n,(M?1)?M,(M?2)?M,,(M?n)2?M中至少有一项可以被n整除.
2k故取n?p,对于i?1,2,2k所以p,p2k一定存在某个i使得p2k|(M?i)2?M.注意到p2kM.
(M?i)2( 若不然, p2k|(M?i)2,又p2k|(M?i)2?M.于是p2kM矛盾).
2k22k?1|(M?i)2?M.注意到p2k?1|M.所以p2k?1|(M?i)2. 由于p|(M?i)?M,于是p2k?1|(M?i)2且p2k我们得到p(M?i)2.这与(M?i)2是完全平方数矛盾.
所以假设错误.所以正整数M是完全平方数.
x4?1y4?1444?7.已知整数x,y满足x??1,y??1,且使得是整数,求证xy?1能被x?1整除. y?1x?1
x4?1ay4?1c?,?.其中(a,b)?1,(c,d)?1,b?0,d?0. 证明：设
y?1bx?1d则
acad?bc??是整数.即bd|ad?bc. bdbd从而b|ad?bc,d|ad?bc.于是b|ad,d|bc.注意到(a,b)?1,(c,d)?1. 所以b|d,d|b.又b?0,d?0,所以b?d.
acx4?1y4?1(x?1)(x?1)(x2?1)(y?1)(y?1)(y2?1)????(x?1)(x2?1)(y?1)(y2?1). 因为??bdy?1x?1y?1x?1所以
ac?是整数,结合b?d. bd2所以b|ac.于是b|ac,又(a,b)?1,则b|c,又(b,c)?1.且b?0.所以b?1.
y4?1也就是?c.即x?1|y4?1.
x?144444444441049又xy?1?x(y?1)?x?1?x(y?1)[(y)?(y)?444所以x?1|xy?1.
?y4?1]?(x?1)(x?1)(x2?1).
3kk8.证明：对于任何自然数n和k,数f(n,k)?2n?4n?10都不能分解成若干个连续的自然数之积.
证明: 我们知道数f(n,k)能分解成n个连续的自然数之积,则一定能被n!整除.所以只需要证明数f(n,k) 不能被一个很小的自然数n整除即可.
f(n,k)?2n3k?4nk?10?(3n3k?3nk?9)?n3k?nk?1?3(n3k?nk?3)?(n3k?nk)?1 ?3(n3k?nk?3)?(nk?1)nk(nk?1)?1.
3|3(n3k?nk?3),3|(nk?1)nk(nk?1),31.
所以3f(n,k).
也就是数f(n,k)不能分解成3个或3个以上的连续的自然数之积. 下面再证明数f(n,k)不能分解成2个连续的自然数之积.
由上可知f(n,k)?3q?1.因此只需要证明3q?1?x(x?1)无自然数解. 当x?3m时,x(x?1)?3m(3m?1)?3[m(3m?1)],故无解.
2当x?3m?1时,x(x?1)?(3m?1)(3m?2)?3(3m?3m)?2,故无解.
当x?3m?2时,x(x?1)?(3m?2)(3m?3)?3(m?1)(3m?2)故无解. 所以数f(n,k)不能分解成2个连续的自然数之积.
3kk于是我们证明了对于任何自然数n和k,数f(n,k)?2n?4n?10都不能分解成若干个连续的自然数之积.
9.对于所有素数p和所有正整数n(n?p),证明：Cn???能被p整除.
p?n??p?证明：n,n?1,n?2,则?,n?p?1这连续p个数有且仅有一个被p整除,设这个数为N.则N?pq,q?Z.
,N?1,N?1,n?p?1除以p的余数不计次序为1,2,(n?p?1)?(p?1)!?pA.
,p?1.
?n?N??p?q.且n,n?1,p??(N?1)(N?1)于是n(n?1)?n?n(n?1)(N?1)N(N?1)Cnp????p!?p??(p?1)!?pA?pqA. ?q??1???(p?1)!?(p?1)!因为p与1,2,(n?p?1)?n(n?1)?q?q??(N?1)(N?1)(p?1)!(n?p?1)??1???n?qA,p?1互素,所以(p,(p?1)!)?1.于是(p?1)!|qAC.np????p?.
p(p?1)!???n?. ??p?所以p|Cn??
p10.(1)求所有的素数数列p1?p2??pn,使得?(1?k?1n1)是一个整数. pk*(2)是否存在n个大于1的不同正整数a1,a2,n,an,n?N,使得?(1?k?1n1)为整数?. 2ak(1?pk)?1)?k?1n. 解(1)?(1?pkk?1?pknk?1当n?3时,pn?pk?1,1?k?n?1.故(于是pn?1矛盾.所以n?2.当n?1时,1??(1?p),p)?1.所以pknk?1n?1n|1?pn.又pn|pn.所以pn|1.
1?N. p1(1?p1)(1?p2)1?p1?p211)(1?)??1??N. p1p2p1p2p1p2当n?2时,(1?p1p2|1?p1?p2,p2|1?p1?p2,p2|1?p1.又p2?p1?1.所以p2?1?p1.
于是p1|1?p1?1?p1,p1|2. 所以p1?2,p2?3.
综上,所求的数列只有一个p1?2,p2?3.
(2)不存在. 当1?a1?a2?n?an时,设an?m.
mmm11k2?1mk2k2(m!)22m1??(1?2)??(1?2)??2??2?????2.(m?1)!akkkm?1k?1k?2k?2k?2k?1k?2(k?1)(k?1)(m?1)!2n1所以?(1?2)?N.
akk?1n所以不存在n个大于1的不同正整数a1,a2,
,an,n?N,使得?(1?*k?11)为整数. ak2mn(m,n)?1. 11.设m,n是正整数, 证明(2?1,2?1)?2解：不妨设m?n.有带余除法得m?q1n?r1(q1?1,0?r1?n).
m我们有2?1?21n因为2?1|2q1nqn?r1?1?2q1n?r1?2r1?2r1?1?2r1(2q1n?1)?2r1?1.
?1,所以(2m?1,2n?1)?(2r1?1,2n?1).
注意到(m,n)?(n,r1).
mnnnn若r1?0,则(m,n)?(n,r1)?n.于是(2?1,2?1)?(21?1,2?1)?(0,2?1)?2?1.结论成立.
r若r1?0,则作辗转相除.,n?q2r1?r2(q2?1,0?r2?r1).
n我们有2?1?2q2r1?r2?1?2r2(2q2r1?1)?2r2?1.
因为21?1|2rq2r1?1,所以(2m?1,2n?1)?(2r1?1,2n?1)?(2r1?1,2r2?1).
若r2?0,则继续处理,直到rk?1?0为止.由辗转相除法知(m,n)?rk.
(2m?1,2n?1)?(2r1?1,2n?1)?(2r1?1,2r2?1)?至此,我们证得了结论.
?(2rk?1,2rk?1?1)?(2rk?1,0)?2rk?1?2(m,n)?1.
12.任给n?2,证明：存在n个互不相同的正整数,其中任意两个的和整除这n个数的积.
证明：我们任取n个互不相同的正整数a1,a2,,an,并选取一个正整数参数K,希望Ka1,Ka2,,Kan的积
Kna1a2取K?an被任意两项的和Kai?Kaj(i?j)整除,
1?i?j?n?(ai?aj).
,Kan互不相同, Kai?Kaj?(ai?aj)Ka1,Ka2,1?i?j?n?(ai?aj).
Kna1a2an?(1?i?j?n?(ai?aj))na1a2nan.
显然有Kai?Kaj|Ka1a2
an.