数论问题的常用方法数论是研究数的性质的一门科学，它与中学数学教育有密切的联系。
数论问题解法灵活，题型丰富，它是中学数学竞赛试题的源泉之一。
下面介绍数论试题的常用方法.1.根本原理为了使用方便，我们将数论中的一些概念和结论摘录如下：我们用),...,,(21n a a a 表示n 个整数1a ,2a ,…,n a 的最大公约数。
用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的最小公倍数。
对于实数x ，用[x ]表示不超过x 的最大整数，用{x }=x -[x ]表示x 的小数局部。
对于整数b a ,,假设)(|b a m -，,1≥m 那么称b a ,关于模m 同余，记为)(mod m b a ≡。
对于正整数m ，用)(m ϕ表示{1，2，…，m }中与m 互质的整数的个数，并称)(m ϕ为欧拉函数。
对于正整数m ，假设整数m r r r ,...,,21中任何两个数对模m 均不同余，那么称{m r r r ,...,,21}为模m 的一个完全剩余系；假设整数)(21,...,,m r r r ϕ中每一个数都与m 互质，且其中任何两个数关于模m 不同余，那么称{)(21,...,,m r r r ϕ}为模m 的简化剩余系。
定理1设b a ,的最大公约数为d ，那么存在整数y x ,，使得yb xa d +=.定理2 〔1〕假设)(mod m b a i i ≡，1=i ，2，…，n ，)(mod 21m x x =，那么11nii i a x =∑≡21ni ii b x=∑；〔2〕假设)(mod m b a ≡，),(b a d =，m d |，那么)(mod dm d b d a ≡； 〔3〕假设)(mod m b a ≡，),(b a d =，且1),(=m d ，那么)(mod m dbd a ≡；〔4〕假设b a ≡〔i m mod 〕，n i ,...,2,1=，M=[n m m m ,...,,21]，那么b a ≡〔M mod 〕. 定理3 〔1〕1][][1+<≤<-x x x x ； 〔2〕][][][y x y x +≥+；〔3〕设p 为素数，那么在!n 质因数分解中，p 的指数为∑≥1k k pn.定理4 〔1〕假设{m r r r ,...,,21}是模m 的完全剩余系，1),(=m a ，那么{b ar b ar b ar m +++,...,,21}也是模m 的完全剩余系；〔2〕假设{)(21,...,,m r r r ϕ}是模m 的简化剩余系，1),(=m a ，那么{)(21...,,m ar ar ar ϕ}是模m 的简化剩余系.定理5〔1〕假设1),(=n m ，那么)()()(n m mn ϕϕϕ=.(2) 假设n 的标准分解式为k k p p p n ααα (2)121=，其中k ααα,...,21为正整数，kp p p ,...,21为互不一样的素数，那么)11)...(11)(11()(21kp p p n n ---=ϕ. 对于以上结论的证明，有兴趣的读者可查阅初等数论教材.2 方法解读对于数论试题，除直接运用数论的根本原理外，常用的根本方法还有因式〔因数〕分解法，配对法，分组法，估值法，同余方法，构造法，调整法，数学归纳法与反证法.下面分别予以说明2.1根本原理的应用例1 设正整数a ，b ，c 的最大公约数为1，并且c ba ab=-〔1〕 证明：)(b a -是一个完全平方数.证 设d b a =),(,d a a 1=,d b b 1=,其中1),(11=b a .由于1),,(=c b a ，故有1),(=c d .由〔1〕得c b c ad b a 1111-=〔2〕由〔2〕知，c b a 11|，又1),(11=b a ，∴c a |1.同理可证c b |1，从而有c b a |11，设k b a c 11=，k 为正整数，代入〔2〕得)(11b a k d -= 〔3〕由〔3〕知d k |，又c k |，∴1),(|=c d k ，∴1=k . ∴11b a d -=.∴211)(d b a d b a =-=-. 故)(b a -是一个完全平方数.例2 设n 为大于1的奇数，1k ，2k ，…，n k 为给定的n 个整数.对于{n ,...,2,1}的任一排列12(,,...,)n P a a a =，记1()ni i i s P k a ==∑，试证存在{n ,...,2,1}的两个不同的排列B 、C ，使得)()(!|C s B s n -.证 假设对于任意两个不同的排列B 、C ，均有!n 不整除)()(C S B s -.令X 为{n ,...,2,1}的所有排列构成的集合，那么{()|s P P X ∈}为模!n 的一个完全剩余系，从而有!1(1!)!()(mod !)2n P Xi n n s P i n ∈=+≡=∑∑ 〔1〕 又 1()()ni i P X P X i s P k a ∈∈==∑∑∑=∑=+ni i k n n 12)1(! 〔2〕 而n 为大于1的奇数，所以由〔1〕，〔2〕得)!(mod 02)1(!2!)!1(1n k n n n n ni i ≡+≡+∑=. 又1)!,!1(=+n n ，所以)!(mod 02!n n ≡，矛盾. 这个矛盾说明必存在B 、C X ∈，B ≠C ，使得)()(!|C s B s n -.2.2 因式〔数〕分解例2 求三个素数，使得它们的积为和的5倍.解 采用分析中的记号，易知a ，b ，c 中必有一个为5，不妨设5c =，那么有 5++=b a ab ， 从而有6)1)(1(=--b a .因为1-a 与1-b 均为正整数，不妨设b a <，那么有⎩⎨⎧=-=-6111b a 或 ⎩⎨⎧=-=-3121b a ， 从而知2=a ，7=b .故所求的三个素数为2，5，7.2.3配对例4 设k 为正奇数，证明：n ++++...321整除kkkn +++...21.分析 因为2)1(...321+=++++n n n .故需证)...21(2|)1(k k k n n n ++++，注意到当k 为奇数时，k k y x +可因式分解，因此可将)...21(2k k k n +++中的n 2个数两两配对. 证 )...21(2k k k n +++=k k k k k k k n n n n 2]1)1[(...])2(2[])1(1[++-++-++-+，而当k 为奇数时，k k b a b a ++|，从而知()k k k n n +++...212| 〔1〕又 ()k k k n +++...212=]1[...])1(2[]1[k k k k k k n n n +++-+++， ∴)...21(2|)1(k k k n n ++++ 〔2〕 由〔1〕〔2〕知，)...21(2|)1(k k k n n n ++++，故结论成立.2.4 分组例5 〔1990年高中联赛试题〕设}200,...,2,1{=E ，},...,,{10021a a a G =E ⊆，且G 具有以下性质：（1） 对任何1001≤<≤j i ，201≠+j i a a ； （2）100801001=∑=i ia.试证：G 中的奇数的个数是4的倍数，且G 中所有数的平方和是一定数.证 对于1001≤≤i ，令12-=i i α，i i αβ-=201.},{i i i E βα=，那么G 中恰含iE 中的一个元素.设G 中有k 个奇数1i α，2i α，…，k i α，有s 个偶数sj j j βββ,...,,21，这里},...,,,,...,,{2121s k j j j i i i =}100,...,2,1{.由题设知， 10080=∑∑∑∑====+-=+sr j kt i sr j kt i r t rt1111)201(βββα=∑∑==-kt i kt t 112201β+⎪⎭⎫⎝⎛+∑∑==k t sr j i r t 11ββ =-k 2012∑=kt i t1β+)200...642(++++=1010022011+-∑=kt i tk β.∴ 〔1〕由于t i β为偶数，所以∑=kt i t12|4β，又20|4，所以k 201|4，∴k |4，即k 是4的倍数.∑∑∑===+=sr j kt i i irta121210012βα=∑∑==+-sr j kt i rt1212)201(ββ=∑∑==⨯-kt i kt t1122012201β+)(1212∑∑==+sr j kt i rtββ=∑=⨯-kt i t k 122012201β+)200...642(2222++++=)2201(2011∑=-kt i tk β+6)1200)(1100(1004++⨯〔2〕将〔1〕代入〔2〕得62011011004)20(20110012⨯⨯⨯+-⨯=∑=i i a =1349380.2.5估值例6 令n a 表示前n 个质数之和，即21=a ，5322=+=a ,105323=++=a ,…,证明：对任意的正整数n ，区间[1,+n n a a ]中包含有一个完全平方数.分析 设质数从小到大依次为12,,...,k p p p …，要结论成立，只要存在正整数m ，使得12+≤≤n n a m a ，只要 1+≤≤n n a m a ，只要11≥-+n n a a ，只要 n n n a a a 211+≥-+， 只要 n n a p 211+≥+只要 〔1〕证 直接验证易知[2,1,a a ]，[32,a a ]，[43,a a ]，[54,a a ]中都含有1个完全平方数.当5≥n 时，我们证明〔1〕式成立.为此，令2112(1)(1)4(...)n k f n p p p p ++=--+++，2112(1)44(...)n n k p a p p p +-≥=+++那么n n n p p p n f n f 4)1()1()()1(221----=-++=n n n n n p p p p p 4)2)((11--+-++. 因为当2≥n 时，n p 为奇数，所以21≥-+n n p p ，1(1)()2(22)n n n f n f n p p p ++-≥+--=)2(21--+n n p p 0≥，故当2≥n 时，数列)(n f 为递增数列.由于)(4)1()5(432125p p p p p f +++--==)7532(4)111(2+++--=32>0所以当5≥n 时，0)5()(>≥f n f .故当5≥n 时〔1〕式成立.例7 求出不定方程1)!1(-=-k n n 〔1〕的全部正整数解.解 当2=n 时，易得1=k ；当2>n 时，〔1〕式左边为偶数，故右边也是偶数，所以n 为奇数.当3=n 时，由13!2-=k ，得1=k .当5=n 时，由15!4-=k ，得2=k .当5>n 且为奇数时，321-<-n n ，221≠-n ，故)!2(|212--⋅n n ，即)!2(|)1(--n n ，因此2(1)|(1)!n n --，所以)1(|)1(2--k n n .另一方面，由二项式定理知1)1)1((1-+-=-k k n n =A 〔2)1-n +)1(-n k .其中A 为整数，所以)1(|)1(2--n k n ，故k n |)1(-， 因此1-≥n k ，从而有)!1(111->-≥--n n n n k .这说明当5>n 时，方程〔1〕无解，故方程〔1〕的解为)1,2(),(=k n ，)1,3(，)2,5( 2.6同余 例8 证明991993991993+能被1984整除.证 993993993)991(-≡=9912)991()991(--=)1984(mod )991()991)(11984495(991991-≡-+⨯，∴)1984(mod 0991)991(991993991991991993≡+-≡+. ∴991993991993|1984+.例9 用数码1，2，3，4，5，6，7 排成7位数，每个数码恰用一次，证明：这些7位数中没有一个是另一个的倍数. 证 假设有两个7位数a ，b ，使得kb a = 〔1〕 由于a ，b 均是由1，2，...,7所排成，故72≤≤k 由〔1〕得)9(mod kb a ≡，∴)9(mod 11⋅≡k ，即)9(mod 1≡k ，这与92≤≤k 矛盾，故结论成立.2.7构造例10 假设一个正整数的标准分解中，每个素约数的幂次都大于1，那么称它为幂数，证明：存在无穷多个互不一样的正整数，它们及它们中任意多个不同数的和都不是幂数.证 将全体素数从小到大依次记为1p ，2p ，...，n p ，….令11p a =，2212p p a =，当2≥n 时，n n n n n n p p p p p p a a 21222111...---==，下证 1a ，2a ，…，n a ，…满足要求.事实上， n n a p |，但2n p |/n a ，所以n a 不是幂数.又对于k i i i <<<≤ 211， )1(112121i i i i i i i i a a a a a a a a k k +++=+++ =)1(11i i Ap a +=)1(111212221i i i Ap p p p p +- ， 其中A 为正整数.因为1)1,(11=+i i Ap p ，所以1i p 在)(21k i i i a a a +++ 的标准分解中的幂次为1，因而不是幂数.例11 设}2011,,3,2,1{ 中质数的个数为a ，n 为正整数且a n ≤<1，求证必有2011个连续正整数，其中恰有n 个质数.证 令}2010,,2,1,{+++=k k k k A k ，并令)(k f 为k A 中质数的个数，那么易知a f =)1(，0)2!2012(=+f . 对于)1!2012(,,2,1+= k ，显然有1|)()1(|≤-+k f k f ，所以对于a n ≤<0，必存在一个0k ，使得n k f =)(0，从而0k A 中的2011个连续整数满足要求.2.9 数学归纳法例12 设n 是正整数，求证：124323|51222-+-n n n .证 令22()332241n f n n n =-+-.因为0)1(=f ，所以)1(|512f ，假设)(|512n f ，那么对于1+n ，因为)183(8)()1(2--=-+n n f n f n ，所以要证)1(|512+n f ，只需证)183(8|5122--n n ，即只需证明)183(|642--n n .为此，令183)(2--=n n g n .显然有0)1(|64=g ，假设)(|64n g ，由于)199(64)19(8)()1(21+++=-=-+-- n n n n g n g ，∴)1(|64+n g ，由归纳法原理知对一切n ，有183|642--n n，从而有)1(|512+n f ，再由归纳法原理知，对于正整数n ，有)(|512n f .2.10反证法例13 试证方程042333=--z y x 〔1〕 无正整数解.分析 假设〔z y x ,,〕为〔1〕的一组解，那么x 为偶数，令12x x =，那么有0243331=--z y x ，从而知y 为偶数，再令12y y =，代入上式得04233131=--z y x ，从而知z 为偶数，再令12z z =，代入上式得042313131=--z y x ，因此),,(111z y x 也是方程〔1〕的解.这样由方程〔1〕的一组正整数解),,(z y x 必可得到另一组正整数解),,(111z y x ，且x x <1.因此，假设开场取得的正整数解使得x 到达最小，那么这种下降不可能进展.证 反证法. 假设方程〔1〕存在正整数解，设),,(000z y x 是使得x 到达最小的正整数解，那么依分析的过程知必可得到方程〔1〕的一组正整数解),,(111z y x ，且01x x <，这与0x 到达最小相矛盾，这个矛盾说明方程〔1〕无正整数解.注：此题中分析的方法称为无穷递降法习 题1．设1≥≥n m ，m ，n 为整数，证明nm C mn m ),(是整数.2．设a ，b 为整数，证明：))1(()2)((|)!(1b n a b a b a a b n n -+++- .3.设n 是大于3的奇数，证明可将集合}1,,3,2,1{-n 的元素分成两组，每组21-n 个元素，使得两组数的和模n 同余.。
