高中数学竞赛中数论问题的常用方法
数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法.
1.基本原理
为了使用方便,我们将数论中的一些概念和结论摘录如下:
我们用(a1,a2,...,an)表示整数a1,a2,…,an的最大公约数.用[a1,a2,…,an]表示a1,a2,…,an的 最小公倍数.对于实数x,用[x]表示不超过x的最大整数,用{x}=x-[x]表示x的小数部分.对于整数
m).对于正整数m,用?(m)表示a,b,若m|(a?b),m?1,则称a,b关于模m同余,记为a?b(mod{1,2,…,m}中与m互质的整数的个数,并称?(m)为欧拉函数.对于正整数m,若整数r1,r2,...,rm中任何两个数对模m均不同余,则称{r1,r2,...,rm}为模m的一个完全剩余系；若整数r1,r2,...,r?(m)中每一个数都与m互质,且其中任何两个数关于模m不同余,则称{r1,r2,...,r?(m)}为模m的简化剩余系.
定理1 设a,b的最大公约数为d,则存在整数x,y,使得d?xa?yb.
定理2(1)若ai?bi(modm),i?1,2,…,n,x1?x2(modm),则
(2)若a?b(modm),d?(a,b),d|m,则
?ax??bxii1inni2；
i?1i?1abm?(mod)； dddab(3)若a?b,d?(a,b),且(d,m)?1,则?(modm)；
dd(4)若a?b(modmi),i?1,2,...,n,M=[m1,m2,...,mn],则a?b(modM). 定理3(1)x?1?[x]?x?[x]?1； (2)[x?y]?[x]?[y]；
(3)设p为素数,则在n!质因数分解中,p的指数为
?p
k?1
n
k
.
定理4 (1)若{r1,r2,...,rm}是模m的完全剩余系,(a,m)?1,则{ar1?b,ar2?b,...,arm?b}也是模
m的完全剩余系；
(2)若{r1,r2,...,r?(m)}是模m的简化剩余系,(a,m)?1,则{ar1,ar2...,ar?(m)}是模m的简化剩余系. 定理5(1)若(m,n)?1,则?(mn)??(m)?(n).
?1?2(2)若n的标准分解式为n?p1?k为正整数,p1,p2,...pk为互不相p2...pkk,其中?1,?2,...?第 1 页 共 6 页
同的素数,则?(n)?n(1?111)(1?)...(1?). p1p2pk对于以上结论的证明,有兴趣的读者可查阅初等数论教材.
2 方法解读
对于数论试题,除直接运用数论的基本原理外,常用的基本方法还有因式(因数)分解法,配对法,分组法,估值法,同余方法,构造法,调整法,数学归纳法与反证法.下面分别予以说明
2.1基本原理的应用
例1 设正整数a,b,c的最大公约数为1,并且
ab?c (1),证明:(a?b)是一个完全平方数. a?b证:设(a,b)?d,a?a1d,b?b1d,其中(a1,b1)?1.由于(a,b,c)?1,故有(d,c)?1.由(1)得
a1b1d?a1c?b1c (2)
由(2)知,a1|b1c,又(a1,b1)?1,∴ a1|c.同理可证b1|c,从而有a1b1|c,设c?a1b1k,k为正整数,代入(2)得d?k(a1?b1) (3)
由(3)知k|d,又k|c,?k|(d,c)?1,?k?1. ∴d?a1?b1.∴a?b?d(a1?b1)?d2.故成立. 例2 设n为大于1的奇数,k1,k2,…,kn为给定的整数.对于{1,2,...,n}的排列P?(a1,a2,...,an), 记s(P)??ka,试证存在{1,2,...,n}的两个不同的排列B、C,使得n!|s(B)?s(C).
iii?1n证:假设对于任意两个不同的排列B、C,均有n!不整除s(B)?S(C).令X为{1,2,...,n}的所有排列构
成的集合,则{s(P)|P?X}为模n!的一个完全剩余系,从而有
P?Xn?s(P)??i?i?1n!(1?n!)n!(modn!) (1) 2n!(n?1)n 又??s(P)??(?kiai)=ki (2) ?2P?XP?Xi?1i?1(1?n!)n!n!(n?1)n而n为大于1的奇数,所以由(1),(2)得?ki?0(modn!). ?22i?1又(1?n!,n!)?1,所以2.2 因式(数)分解
数论中许多问题直接与因式(数)分解相关联,如合数问题,整除问题等常常是要证明某种分解式的存在.数的标准分解式本身就是一种特定形式的因数分解.在不定方程的求解与一些代数式的求值中,因式(数)分解能帮助我们确定某些变量的取值范围,寻找到解题的方法.
第 2 页 共 6 页
n!?0(modn!),矛盾.故,存在B、C?X,B?C,使得n!|s(B)?s(C). 2
例3 求三个素数,使得它们的积为和的5倍.
解:易知a,b,c中必有一个为5,不妨设c?5,则有ab?a?b?5,从而有(a?1)(b?1)?6.
因为a?1与b?1均为正整数,不妨设a?b,则有?求的三个素数为2,5,7.
2.3 配对
?a?1?1?a?1?2或?,从而知a?2,b?7.故所
?b?1?6?b?1?3 例4 设k为正奇数,证明:1?2?3?...?n整除1?2?...?n. 分析 因为1?2?3?...?n?kkkn(n?1).故需证n(n?1)|2(1k?2k?...?nk),注意到当k为奇数2时,xk?yk可因式分解,因此可将2(1k?2k?...?nk)中的2n个数两两配对.
证 ?2(1k?2k?...?nk)=[1k?(n?1)k]?[2k?(n?2)k]?...?[(n?1)k?1k]?2nk, 而当k为奇数时,a?b|ak?bk,从而知n|21k?2k?...?nk (1) 又?21k?2k?...?nk=[1k?nk]?[2k?(n?1)k]?...?[nk?1k],
∴(n?1)|2(1k?2k?...?nk) (2) 由(1)(2)知,n(n?1)|2(1k?2k?...?nk),故结论成立.
2.4 分组
????},G?{a1,a2,...,a100}?E,且G具有下列性质: 例5 (1990年高中联赛试题)设E?{1,2,...,200(1)对任何1?i?j?100,ai?aj?201；(2)
?ai?1100i?10080.
试证:G中的奇数的个数是4的倍数,且G中所有数的平方和是一定数.
证:对于1?i?100,令?i?2i?1,?i?201??i.Ei?{?i,?i},则G中恰含Ei中的一个元素.设G100}.由中有k个奇数?i1,?i2,…,?ik,有s个偶数?j1,?j2,...,?js,这里{i1,i2,...,ik,j1,j2,...,js}={1,2,...,题设知,10080=
??t?1kit???jrr?1kss?k???(201??it)???jr=?201?2??it+???it???jr? t?1r?1t?1t?1r?1?t?1?kskkk =201k?2
??t?1it+(2?4?6?...?200)=201k?2??t?1it?10100.
∴201k?2??t?1kit??20 (1)
第 3 页 共 6 页
由于?it为偶数,所以4|2100ks??t?1kkit,又4|20,所以4|201k,?4|k,即k是4的倍数.
skkks?ai?12i??????=?(201??it)???=?201?2?201??it+(?????j2r)
t?12itr?12jr2t?1r?12jr2t?1t?1t?12itr?1=201k?2?201k2??t?1tkit+(22?42?62?...?2002)
=201(201k?2??i)+4?t?1100100(100?1)(200?1) (2)
6将(1)代入(2)得2.5估值
?ai2?201?(?20)?4?i?1100?101?201=1349380.
6例6 令an表示前n个质数之和,即a1?2,a2?2?3?5,a3?2?3?5?10,…,证明:对任意的正整数n,区间[an,an?1]中包含有一个完全平方数.
分析:设质数从小到大依次为p1,p2,...,pk…,要结论成立,只要存在正整数m,使得an?m2?an?1,只要
an?m?an?1,只要an?1?an?1,只要an?1?an?1?2an,只要pn?1?1?2an,只要
(pn?1?1)2?4an?4(p1?p2?...?pk) (1)
证:直接验证易知[a1,,a2],[a2,a3],[a3,a4],[a4,a5]中都含有1个完全平方数.当n?5时,我们证明:(1)式成立.为此,令f(n?1)?(pn?1?1)2?4(p1?p2?...?pk),
则f(n?1)?f(n)?(pn?1?1)2?(pn?1)2?4pn=(pn?1?pn)(pn?1?pn?2)?4pn.
当n?2时,pn为奇数,故pn?1?pn?2,f(n?1)?f(n)?2(pn?1?pn?2?2pn)=2(pn?1?pn?2)?0, 故当n?2时,数列f(n)为递增数列.由于
f(5)?(p5?1)?4(p1?p2?p3?p4)=(11?1)?4(2?3?5?7)=32>0 所以当n?5时,f(n)?f(5)?0.故当n?5时(1)式成立.
例7 求出不定方程(n?1)!?n?1 (1)的全部正整数解.
解 当n?2时,易得k?1；当n?2时,(1)式左边为偶数,故右边也是偶数,所以n为奇数.当n?3kk时,由2!?3?1,得k?1.当n?5时,由4!?5?1,得k?2.
22k第 4 页 共 6 页
当n?5且为奇数时,
n?1n?1n?1?n?3,?2,故2?|(n?2)!,即(n?1)|(n?2)!,因此2222,所以(n?1)|n(?1)!(n?1)2|(nk?1).
另一方面,由二项式定理知nk?1?((n?1)?1)k?1=A(n?1)2+k(n?1).
其中A为整数,所以(n?1)2|k(n?1),故(n?1)|k,因此k?n?1,故有nk?1?nn?1?1?(n?1)!. 这说明当n?5时,方程(1)无解,故方程(1)的解为(n,k)?(2,1),(3,1),(5,2).
2.6同余 例8 证明993993?991991能被1984整除.
证 ?993993?(?991)993=(?991)2(?991)991=(495?1984?1)(?991)991?(?991)991(mod1984),
991∴993993?991?(?991)991?991991?0(mod1984).∴1984|993993?991991.
例9 用1,2,3,4,5,6,7组成的无重复数字的7位数,证明:这些7位数中没有一个是另一个的倍数. 证:若有两个7位数a,b,使得a?kb (1) 由于a,b均是由1,2,...,7所排成,故2?k?7由(1)得a?kb(mod9), ∴1?k?1(mod9),即k?1(mod9),这与2?k?9矛盾,故结论成立. 2.7构造
例10 若一个正整数的标准分解中,每个素约数的幂次都大于1,则称它为幂数,证明:存在无穷多个互不相同的正整数,它们及它们中任意多个不同数的和都不是幂数.
证:将全体素数从小到大依次记为p1,p2,...,pn,….
2222令a1?p1,a2?p1p2,当n?2时,an?an?1pn?1pn?p1p2...pn?1pn,下证:a1,a2,…,an,…合题意.
2|an,所以an不是幂数.又对于1?i1?i2???ik, 事实上,?pn|an,但pn? ai1?ai2???aik?ai1(1?ai2ai1???aikai12?pi2pi1(1?Api1), )=ai1(1?Api1)=p12p21?1其中A为正整数.因为(pi1,1?Api1)?1,所以pi1在(ai1?ai2???aik)的标准分解中的幂次为1,因而不是幂数.
}中质数的个数为a,n为正整数且1?n?a,求证必有2011个连续正整数, 例11 设{1,2,3,?,2011其中恰有n个质数.
第 5 页 共 6 页
证:令Ak?{k,k?1,k?2,?,k?2010},并令f(k)为Ak中质数的个数,则易知
!?2)?0. 对于k?1,2,?,(2012!?1),显然有|f(k?1)?f(k)|?1, f(1)?a,f(2012所以对于0?n?a,必存在一个k0,使得f(k0)?n,从而Ak0中的2011个连续整数满足要求.
2.8 数学归纳法
例12 设n是正整数,求证:512|32n?32n2?24n?1.
证:令f(n)?32n?32n2?24n?1.因为f(1)?0,所以512|f(1),假设512|f(n),那么对于n?1,因为f(n?1)?f(n)?8(32n?8n?1),所以要证512|f(n?1),只需证512|8(32n?8n?1),即只需证明
64|(32n?8n?1).为此,令g(n)?32n?8n?1.显然有64|g(1)?0,假设64|g(n),
由于g(n?1)?g(n)?8(9n?1)?64(9n?1?9n?2???1),因此64|g(n?1),由归纳法原理知对一切n,有64|32n?8n?1,从而有512|f(n?1),再由归纳法原理知,对于正整数n,有512|f(n).
2.9 反证法
例13 试证方程x3?2y3?4z3?0 (1)无正整数解.
3分析:若(x,y,z)为(1)的一组解,则x为偶数,令x?2x1,则4x1?y3?2z3?0,从而知y为偶数,33333再令y?2y1,代入得2x1?4y1?z3?0,故z为偶数,再令z?2z1,代入得x1?2y1?4z1?0,因此
(x1,y1,z1)也是方程(1)的解.这样由方程(1)的一组正整数解(x,y,z)必可得到另一组正整数解(x1,y1,z1),且x1?x.因此,若开始取得的正整数解使得x达到最小,则这种下降不可能进行.
证:反证法. 若方程(1)存在正整数解,设(x0,y0,z0)是使得x达到最小的正整数解,那么依分析的过程知必可得到方程(1)的一组正整数解(x1,y1,z1),且x1?x0,这与x0达到最小相矛盾,这个矛盾表明方程(1)无正整数解. 习题
1．设m?n?1,m,n为整数,证明2．设a,b为整数,证明:(n!)|bn?1(m,n)nCm是整数. ma(a?b)(a?2b)?(a?(n?1)b).
n?1个元素,使得两组数的23.设n是大于3的奇数,证明可将集合{1,2,3,?,n?1}的元素分成两组,每组和模n同余.
第 6 页 共 6 页
证:令Ak?{k,k?1,k?2,?,k?2010},并令f(k)为Ak中质数的个数,则易知
!?2)?0. 对于k?1,2,?,(2012!?1),显然有|f(k?1)?f(k)|?1, f(1)?a,f(2012所以对于0?n?a,必存在一个k0,使得f(k0)?n,从而Ak0中的2011个连续整数满足要求.
2.8 数学归纳法
例12 设n是正整数,求证:512|32n?32n2?24n?1.
证:令f(n)?32n?32n2?24n?1.因为f(1)?0,所以512|f(1),假设512|f(n),那么对于n?1,因为f(n?1)?f(n)?8(32n?8n?1),所以要证512|f(n?1),只需证512|8(32n?8n?1),即只需证明
64|(32n?8n?1).为此,令g(n)?32n?8n?1.显然有64|g(1)?0,假设64|g(n),
由于g(n?1)?g(n)?8(9n?1)?64(9n?1?9n?2???1),因此64|g(n?1),由归纳法原理知对一切n,有64|32n?8n?1,从而有512|f(n?1),再由归纳法原理知,对于正整数n,有512|f(n).
2.9 反证法
例13 试证方程x3?2y3?4z3?0 (1)无正整数解.
3分析:若(x,y,z)为(1)的一组解,则x为偶数,令x?2x1,则4x1?y3?2z3?0,从而知y为偶数,33333再令y?2y1,代入得2x1?4y1?z3?0,故z为偶数,再令z?2z1,代入得x1?2y1?4z1?0,因此
(x1,y1,z1)也是方程(1)的解.这样由方程(1)的一组正整数解(x,y,z)必可得到另一组正整数解(x1,y1,z1),且x1?x.因此,若开始取得的正整数解使得x达到最小,则这种下降不可能进行.
证:反证法. 若方程(1)存在正整数解,设(x0,y0,z0)是使得x达到最小的正整数解,那么依分析的过程知必可得到方程(1)的一组正整数解(x1,y1,z1),且x1?x0,这与x0达到最小相矛盾,这个矛盾表明方程(1)无正整数解. 习题
1．设m?n?1,m,n为整数,证明2．设a,b为整数,证明:(n!)|bn?1(m,n)nCm是整数. ma(a?b)(a?2b)?(a?(n?1)b).
n?1个元素,使得两组数的23.设n是大于3的奇数,证明可将集合{1,2,3,?,n?1}的元素分成两组,每组和模n同余.
第 6 页 共 6 页