数论问题的常用方法数论是研究数的性质的一门科学，它与中学数学教育有密切的联系。

数论问题解法灵活，题型丰富，它是中学数学竞赛试题的源泉之一。

下面介绍数论试题的常用方法.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 =，则11ni i 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 kp n.定理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为正整数，k p 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）得)!(m o d 02)1(!2!)!1(1n k n n n n n i 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 中恰含i E 中的一个元素.设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 k t 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）1201220t ki t k β=-=-∑2112(1)44(...)n n k p a p p p +-≥=+++证 直接验证易知[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 ++=--+++， 则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 nn 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 nn 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 同余.。