高中数学竞赛数论部分

全国高中数学联赛赛前集训资料整理——数论部分1.求所有的质数对(,)p q ,使得|(55)p q pq +.解：若2|pq ,不妨设2p =,则2|(55)|(525)p q q q q +⇒+,由费马小定理知|(55)q q -,得|30q ,验证知(2,5)符合.若,p q 为奇数,且5|pq ,此时不妨设5p =,则有515|(55)|(6255)q q q q -+⇒+,当5q =时,(5,5)符合要求,当5q ≠时,由费马小定理有1|(51)q q --,故|626q ,由于q 为奇质数,但626的奇质因子只有313,故313q =.验证知符合要求,若,p q 都不等于2和5,则11|(55)p q pq --+,故11550(m od )p q p --+≡① 由费马小定理知151(m od )p p -≡② 由①②知151(m od )q p -≡-③设12(21)k p r -=-,12(21)l q s -=-,,,,k l r s 为正整数,若k l ≤,则由②③易知：2(21)12(21)2(21)(21)1212111(5)5(5)(1)1(m od )l kl kls p s r s q r r p ----------=≡==≡-≡-,这与2p ≠矛盾,因此k l >,由,p q 对称性有k l <,矛盾.此时无解.故(,)p q 为(2,3),(3,2),(2,5),(5,2),(5,5),(5,313),(313,5).2.设3k ≥,数列{}n a 满足2k a k =,且对n k >都有1 1 2 n n n n a a n a n a n -+⎧=⎨⎩与互质与不互质,证明：数列1{}n n a a --中有无穷多项是质数.证明：假设2()l a l l k =≥,p 为1l -的最小质因子,则 1 1(1,) i p l i p i p≤<⎧-=⎨=⎩.故有 1 1(22,1) i p l i l i p i p≤<⎧+-+-=⎨=⎩,由题设知12 1 1(22 l i l i i p a l p i p+-+-≤<⎧=⎨+-=⎩. 则12(222)(22)l p l p a a l p l p p +-+--=+--+-=(质数),故12(1)l p a l p +-=+-,由以上讨论,可知有无穷多个l k ≥使得2l a l =且12l p l p a a p +-+--=为1l -的最小质因子.3.已知1110()m m m m f x c x c xc x c --=++++ ,其中(0,1,,)i c i m = 是非零整数,数列{}n a 满足：10a =, 1()()n n a f a n N ++=∈,求证：(1)对于正整数,()i j i j <,1j j a a +-是1i i a a +-的倍数；(2)证明：20080a ≠. 证明：(1)当10i i a a +-=时,成立；当10i i a a +-≠时,211111()()()()m mi i i i m i i i i a a f a f a c a a c a a +++++-=-=-++- .故21i i a a ++-能被1i i a a +-整除,余下的可用数学归纳法证明.(2)假设20080a =,则1020092008(0)a a f a a -==-,由(1)可知,2007个差值213220082007,,,a a a a a a --- 都等于(0)f ±,且这些差值的和为200810a a -=,由于2007为奇数,且0(0)0f c =≠,矛盾! 故20080a ≠.第49届I MO预选题(四)第50届IMO预选题(四)费马小定理和欧拉定理的应用关于组合数的几个整除问题多项式一、带余除法与因式定理1、余数定理：多项式()f x 除以x a -的余数为()f a .2、因式定理：()()0x a p x p a -⇔=注：高次多项式因式分解常用因式定理例 1 设,,a b c 为互异的实数,()p x 为实系数多项式,如果()p x 除以x a -的余式为a ,()p x 除以x b -的余式为b ,()p x 除以x c -的余式为c .求()p x 除以()()()x a x b x c ---的余式.解：因为 (),(),()p a a p b b p c c ===所以设()()()()()()p x x a x b x c q x r x =---+,其中(())2r x ∂≤ 则 ()(),()(),()()r a p a a r b p b b r c p c c ======, 所以,,a b c 一定是()0r x x -=的根而 (())2r x x ∂-≤,所以 ()0r x x -≡即 ()r x x ≡所以()p x 除以()()()x a x b x c ---的余式为x .例2 已知()p x 是整系数多项式,1234,,,m m m m 是互不相同的整数,且1234()()()()7p m p m p m p m ====,试证：没有整数m 使得()14p m =.分析：即证()14p x =没有整数解证：因为1234,,,m m m m 是()70p x -=的根所以 1234()7()()()()()p x x m x m x m x m q x -=----,其中()q x 一定是整系数多项式 若存在整数m 使()14p m =,则有 12347147()()()()()m m m m m m m m q m =-=---- 而7为素数,矛盾.故没有整数m 使得()14p m =.注：可以根据例2中规律命制试题()i p m =素数即可.例3 设()p x 是非常数的整系数多项式,()n p 表示满足2(())10p x -=的所有不同整数x 的个数,则()deg(())2n p p x -≤,其中deg(())p x 表示()p x 的次数.分析：2(())1(()1)(()1)0()10p x p x p x p x =⇔-+=⇔-=或()10p x +=()n p 为()10p x -=与()10p x +=的整数解的个数设()10p x -=有k 个整数解12,,,k m m m ⋅⋅⋅,()10p x +=有s 个整数解12,,,s n n n ⋅⋅⋅, 则有 121()1()()()()k p x x m x m x m q x -=--⋅⋅⋅- ①122()1()()()()s p x x n x n x n q x +=--⋅⋅⋅- ②②－①得1221212()()()()()()()()s k x n x n x n q x x m x m x m q x =--⋅⋅⋅----⋅⋅⋅-证：我们证明方程 ()10p x -= ③与()10p x += ④中至少有一个方程的正根的个数不超过2.下用反证法证明.若结论不成立,设方程③与方程④均至少有3个正根.设123,,m m m 是③的3个不同正根,123,,n n n 是④的3个不同正根, 则 1231()1()()()()p x x m x m x m q x -=--- ⑤ 1232()1()()()()p x x n x n x n q x +=--- ⑥ ⑥－⑤,得123212312()()()()()()()()x n x n x n q x x m x m x m q x =------- ⑦ 不妨设 {}3123123max ,,,,,m m m m n n n =将3x m =代入⑦式得 313233232()()()()m n m n m n q m =---因为2是素数,而313233,,m n m n m n ---是互不相同的正整数,故矛盾. 所以结论得证.二、多项式恒等定理如果次数不超过n 的多项式()f x 有1n +个根,则()f x 必为零多项式,即()0f x ≡. 例4 已知自然数1m >,求出所有满足条件(())(())m p p x p x =的所有多项式()p x . 证明：当()p x c =(常数)时,由m c c =有0c =或22cossin,(0,1,,2)11k k c i k m m m ππ=+=⋅⋅⋅---当(())1p x ∂≥时,则对任意复数β,方程()p x β=一定有解,即0x ∃使0()p x β=,又00(())(())m p p x p x =,即()m p ββ=.故一切复数均为()0m p x x -=的解,即()0m p x x -=有无穷多个解,故由多项式恒等定理有()m p x x =.例5 求所有满足条件22(2)(2),f x x f x x R -=-∈的多项式()f x分析：因为222(1)1x x x -=--,2(1)1x x -=--,所以22(2)(2)f x x f x -=- 可化为2((1)1)((1)1)f x f x --=--. 解：令1y x =-,则有22(1)(1)f y f y -=- ① 令()(1)g y f y =-,则有22()(1)g y f y =-,故①式变为22()()g y g y = ② 设 1110(),n n n n g y a y a y a y a --=++⋅⋅⋅++其中0n a ≠ 则②式左边222(1)2110()n n n n g y a y a y a y a --==++⋅⋅⋅++ ②式右边212110()()n n n n g y a y a y a y a --==++⋅⋅⋅++所以有22(1)212110110()n n n n n n n n a y a y a y a a y a y a y a ----++⋅⋅⋅++=++⋅⋅⋅++ ③ 下证122100n n a a a a a --==⋅⋅⋅====,用反证法,设1221,,,,n n a a a a --⋅⋅⋅0,a 中有一个不为0,设k a 是使得0i a ≠的下标最大者, 即1210,0k k k n a a a a ++-≠==⋅⋅⋅==比较2()g y 与2()g y 中n k y +的系数,因为22k n k n <+<,所以③式等号左边n k y +的系数为0,而③式右边n k y +的系数为n k a a ,所以 0n k a a =.这与0,0n k a a ≠≠矛盾,所以 122100n n a a a a a --==⋅⋅⋅====,故()n n g y a y = 再由②式有 222n n n n a y a y =. 又因0n a ≠,所以 1n a =故 ()n g y y =即(1)n f y y -=,所以有()(1)n f x x =+. 例6 确定所有符合下列条件的多项式)(x P ：0)0(1)()1(22=+=+P x P x P 且. 解：构造不动点,令.)(,0,1021n n n n x x P x x x ==+=+下证 用数学归纳法：当0000)0()(,00x P x P x n =====时，； 假设kk x x P k n ==)(时，结论成立，即.222111()(1)()111.()0()0().k k k k k n n k P x P x P x x x n k x P x x P x x P x x ++=+=+=+=+==+∴-=∴-≡≡当时，即当时，结论成立是的根，即例 7 试确定所有实系数多项式)(x P ,使得 )()2()1(t P t t tP -=- (1)对所有实系数t 均成立.(1995年 澳大利亚)解：取.0)0(10==P t ），得代入（ 取.0)1(12==P t ），得代入（则设 )()1()(x q x x x P -=代入(1),有)()1()2()1()2)(1(t q t t t t q t t t --=---, 当时，2,1,0≠t )1()(-=t q t q 则 c t q ≡)(则R c x cx x P ∈-=),1()( 另一方面,若)1()(,-=∈x cx x p R c 满足条件中的等式, 因此所求的多项式为.),1()(R c x cx x P ∈-=三、根与系数的关系例8 (1996 澳大利亚)设)(x P 是三次多项式,321,,x x x 是)(x P 的三个根,已知323121111,1000)0()21()21(x x x x x x P P P ++=-+求的值.解：设d cx bx ax x P +++=23)(,又323121111x x x x x x ++=d b ad ab x x x x x x =--=++321321 且 ,212221)0()21()21(1000d b d db P P P ⋅+=+=-+= 则1996=a b ,于是.1996111323121=++x x x x x x 四、拉格朗日插值公式拉格朗日插值公式：设)(x P 为n 次多项式,则)()())(()())(()()())(()())(()()())(()())(()(1101101121012000201021n n n n n n n n n n x P x x x x x x x x x x x x x P x x x x x x x x x x x x x P x x x x x x x x x x x x x P --------++------+------=推论：若.)(,)()()(10c x P c x P x P x P n ≡====则 例9 设n P P P ,,,21 是半径为1的圆周上的n 个不同的点,.11,11121≥⋅⋅=∑=+-nk kn k k k k k k k k d P P P P P P P P P P d 求证：证明：以单位圆的圆心为原点,建立复平面,令k P 所对应的复数为k Z ,.,,2,1n k =则nk k k k k k k k Z Z Z Z Z Z Z Z Z Z d --⋅--⋅-=+- 1121,令)())(()())(()())(()())(()(1211211312132--------++------=n n n n n n n Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z f (1)则)(Z f 的次数不超过.1-n 1)()()(21====n Z f Z f Z f .1)(≡∴Z f 特别地,取0=Z 代入(1),有1)()()1()()()1()0(111211121321=--⋅-++---=----n n n n n n nn Z Z Z Z Z Z Z Z Z Z Z Z Z Z f则 )()()1()()()1(1111211121321-------++---=n n n n n n nn Z Z Z Z Z Z Z Z Z Z Z Z Z Z)()()1()()()1(111211121321-------++---≤n n n n n n nn Z Z Z Z Z Z Z Z Z Z Z Z Z Z nd d d 11121+++==∑=nk kd 11已知10n z -=,其单位根为22cossini w i n nππ=+,则解的集合为{}011,,,n w w w -….结论1：若{}12 n m m m ，，…，是模n 的完全剩余系,则{}{}1211,,,,,,nm m m n w w w ww w-=……结论2：设{}{}01112,,,,,,n n z z z w w w -=……,则 (1)120n z z z +++=…；(2)112(1)n n z z z +=-…；(3)12 0 (,)1m m mn n n m z z z n m ⎧+++=⎨=⎩，…，.例 10 设)(),(),(),(x S x R x Q x P 均为多项式,且满足)()1()())(()(2345255x S x x x x x R x x Q x x P ++++=++ (1),求证：1-x 是)(x P 的因式.(美国) 证明：令52sin52cosππωi +=,取），得代入（1k x ω=0)1()1()1(2=++R Q P k k ωω)4,3,2,1(=k ,)1()()1()()1(48642432=++++++++R Q P ωωωωωωωω则0)1()1()1(4=--R Q P (2) 由得,)1(k ω⨯.4,3,2,1,0)1()1()1(32==++k R Q P k k k ωωω 将4个等式相加,得0)1()()1()()1()(4333231342322212432=+++++++++++⋅⋅⋅⋅⋅⋅⋅⋅R Q P ωωωωωωωωωωωω故0)1()1()1(=---R Q P (3) 得),3()2(-0)1(5=P ,则0)1(=P ,由因式定理得).(1x P x -平方差型不定方程的解法数论中的不等式问题一道巴尔干地区竞赛题的思考一道印度竞赛题的简解一道预赛题的简证一道数论题的新证法一道重要的二元二次不定方程——佩尔方程。

第一讲 因式分解（一）1、 几种常用的因式分解方法①、拆项和添项：把代数式中的某项拆成两项或更多项的代数和，叫做拆项；把代数式添上两个符号相反的项，叫做添项。

一般情况下，如何拆项或添项，依赖于对题目特点的观察和分析。

例1、分解因式：⑴、2426923+++x x x ⑵、15++x x例2、分解因式：24222)1()1(2)1(y x y x y -++-+例3、分解因式：abc c b a 3333-++例4、若a 为正整数，则9324+-a a 是质数还是合数？给出你的证明。

②、按一个变量降次排列：按一个变量降次排列在代数式变换中，是常用的方法之一，按一个变量降次排列的方法，常有利于因式分解的进行。

例5、分解因式：1+++++++z y x zx yz xy xyz例6、分解因式：a x a x a x +++++)12()2(23③、换元法：在作代数式变换时，常常要考虑把一个式子看成一个数（或字母），从而应用基本知识解决问题。

例7、分解因式：2)1()2)(2(ab b a ab b a -+-+-+例8、分解因式：333)42()323()(a b c c b a c b a -++--+++例9、证明：四个连续自然数的积与1之和必是一个完全平方数。

④、待定系数法：待定系数法也是代数式变换的一个常用方法，这个方法的特点是假设变换已经完成，然后再去求出那些尚未确定的系数。

例10、分解因式：35825322-+--+y x y xy x例11、化简912104234++++x x x x例12、分解因式：4925322-++-+y x y xy x例13、求证：y x y xy x +++-22不能分解成两个一次因式的乘积。

例14、求证：1234++++x x x x 可表示成两个多项式的平方差第一讲 因式分解（一）练习1、分解因式：①、32422+++-b a b a =___________________________.②、.____________________262793223=-+-a x a ax x③、._____________________20)5)(3)(1(2=-++-x x x④、._________________________2414723522=-+--+y x y xy x⑤、.__________________________12)2)((42222=-++++y y xy x y xy x ⑥、.___________________________)1)(1)(1(=++++xy y x xy⑦、._______________________)1()2)(2(2=++++-+ab b a ab b a⑧、.___________________________)(3333=---++c b a c b a2、m 为何值时，多项式m y x y xy x +-++-5112101222能分解成两个一次因式的积？3、求满足19832222=-++-x x y xy y x 的整数对),(y x .4、在实数范围内分解因式：1)2(3+++-a x a x .5、已知33332222,,c z y x b z y x a z y x =++=++=++，求xyz 。

数学竞赛中的数论问题 罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支．什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，…是这样一个集合N +：（1）有一个最小的数1．（2）每一个数a 的后面都有且只有一个后继数/a ；除1之外，每一个数的都是且只是一个数的后继数．这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对N +的子集M ，若1M ∈，且当a M ∈时，有后继数/a M ∈，则M N +=．就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．欧拉认为这是对的，但证不出来．1900年希尔伯特将其归入23个问题中的第8个问题． 1966年陈景润证得：一个素数+素数⨯素数（1+2），至今仍无人超越． ●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠．……”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U ．Dudley 《数论基础》前言）．下面，是一个有趣的故事．当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有1n +个正整数，这些正整数小于或等于2n ，那么你一定有一对整数是互素的，你知道这是什么原因吗？不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n 分成（1，2），（3，4），…，（21,2n n -）共n 个抽屉，手头的1n +个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算；简单的一次不定方程．在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*．根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；ϕ欧拉函数；（7）数论函数、[]x高斯函数、()n（8）进位制（十进制、二进制）．下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．第一讲 数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理． 首先约定，本文中的字母均表示整数．定义1 （带余除法）给定整数,,0,a b b ≠如果有整数(),0q r r b ≤<满足 a qb r =+，则q 和r 分别称为a 除以b 的商和余数．特别的，0r =时，则称a 被b 整除，记作b a ，或者说a 是b 的倍数，而b 是a 的约数．（,q r 的存在性由定理1证明）定义2 （最大公约数）设整数12,,,n a a a 中至少有一个不等于零，这n 个数的最大公约数是能整除其中每一个整数的最大正整数，记作()12,,,n a a a ．()12,,,n a a a 中的i a 没有顺序，最大公约数也称最大公因数．简单性质：()()1212,,,,,,n n a a a a a a =．一个功能：可以把对整数的研究转化为对非负整数的研究． 定义3 （最小公倍数）非零整数12,,,n a a a 的最小公倍数是能被其中每一个()1i a i n ≤≤所整除的最小正整数，记作[]12,,,n a a a ．简单性质：如果k 是正整数,a b 的公倍数，则存在正整数m 使[],k m a b =证明 若不然，有[],k m a b r =+（[]0,r a b <<），由[],,k a b 都是,a b 的公倍数得r也是,a b 的公倍数，但[]0,r a b <<，与[],a b 的最小性矛盾．故[],k ma b =．定义4 如果整数,a b 满足(),1a b =，则称a 与b 是互素的（也称互质）．定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．定理1 若,a b 是两个整数，0b >，则存在两个实数,q r ，使()0a qb r r b =+≤<，并且,q r 是唯一性．证明1 先证存在性．作序列,3.2,,0,,2,3,b b b b b b ---则a 必在上述序列的某两项之间，从而存在一个整数q ，使()1qb a q b ≤<+，即 0a qb b ≤-<， 取 r a qb =-， 0r b ≤<， 得 a qb r =+，即存在两个实数,q r ，使()0a qb r r b =+≤<． 再证唯一性．假设不唯一，则同时存在11,q r 与12,q r ，使 ()1110a q b r r b =+≤<， ()2220a q b r r b =+≤<， 相减 ()1221q q b r r -=-， 1221q q b r r b -=-<， 1201q q ≤-<，但12q q -为整数，故120q q -=，得12q q =，从而12r r =．注：如果取消0r b ≤<，当0r <或r b >，不保证唯一．经典方法：紧扣定义，构造法证存在性，反证法证唯一性． 证明2 只证存在性，用高斯记号，由 01a a b b ⎡⎤≤-<⎢⎥⎣⎦， 有 0a a b b b⎡⎤≤-<⎢⎥⎣⎦，记a r a b b⎡⎤=-⎢⎥⎣⎦，故存在,,0a a q r a b r b b b ⎡⎤⎡⎤==-≤<⎢⎥⎢⎥⎣⎦⎣⎦使()0a qb r r b =+≤<．证明3 只证存在性，作集合{}|,0M a bx x Z a bx =-∈-≥这是一个有下界的非空整数集，其中必有最小的，设x q =时，有最小值r ()0r ≥ a qb r =+．再证r b <，若不然，r b ≥，记1r b r =+，有()()111a qb r qb b r b q r =+=++=++()11r a b q M =-+∈即M 有1r 比r 更小，这与r 为最小值矛盾． 故存在两个实数,q r ，使()0a qb r r b =+≤<．定理 2 设,,a b c 是三个不全为0的整数，满足a qb c =+，其中q 也为整数，则()(),,a b b c =．证明 设A =｛,a b 的公约数｝， B =｛,b c 的公约数｝．任取||||d a d c a bqd A d B A B d b d b=-⎧⎧∈⇒⇒⇒∈⇒⊆⎨⎨⎩⎩， 任取||||d b d bd B d A B A d c d a bq c ⎧⎧∈⇒⇒⇒∈⇒⊆⎨⎨=+⎩⎩，得 A B =．有A 中元素的最大值B =中元素的最大值，即()(),,a b b c =．注：这是辗转相除法求最大公约数的理论基础．经典方法：要证明A B =，只需证A B ⊆且B A ⊆． 定理3 对任意的正整数,a b ，有 ()[],,a b a b ab ⋅=．证明 因为ab 是,a b 的公倍数，所以,a b 的最小公倍数也是ab 的约数，存在q 使 [],ab q a b =，有[],a b a q b=且[],a b b为整数，故q 是a 的约数．同理q 是b 的约数，即q 是,a b 的公约数．下面证明，q 是,a b 的最大公约数．若不然，(),q a b <．有[]()[],,,ab q a b a b a b =<． ①设()(),,ab b k a a b a b ==，可见k 是a 的倍数，同样()(),,ab ak b a b a b ==，k 是b 的倍数，即k 是,a b 的公倍数，则存在正整数m 使[],k ma b =，有()[][],,,abm a b a b a b =≥， 得 []()[],,,ab q a b a b a b =≥与①矛盾，所以，(),q a b =，得证()[],,a b a b ab ⋅=．注 也可以由[]()(),1,,ab a b k q m ab a b a b q≤===，得(),q a b ≥，与(),q a b <矛盾．两步[](),,,ab q a b ab a b k ==可以交换吗？定理4 ,a b 是两个不同时为0的整数，若00ax by +是形如ax by +（,x y 是任意整数）的数中的最小正数，则（1）00ax by +|ax by +； （2）00ax by +(),a b =． 证明 （1）由带余除法有()00ax by ax by q r +=++，000r ax by ≤<+， 得 ()()0000r a x qx x b y qy ax by =-+-<+，知r 也是形如ax by +的非负数，但00ax by +是形如ax by +的数中的最小正数，故0r =，即00ax by +|ax by +．（2）由（1）有00ax by +|10a b a +=， 00ax by +|01a b b +=，得00ax by +是,a b 的公约数．另一方面，,a b 的每一个公约数都可以整除00ax by +，所以00ax by +是,a b 的最大公约数，00ax by +(),a b =．推论 若(),1a b =，则存在整数,s t ，使1as bt +=．（很有用） 定理5 互素的简单性质： （1）()1,1a =． （2）(),11n n +=． （3）()21,211n n -+=．（4）若p 是一个素数，a 是任意一个整数，且a 不能被p 整除，则(),1a p =． 证明 因为(),|a p p ，所以，素数p 的约数只有两种可能：()(),1,,a p a p p ==．但a 不能被p 整除，(),a p p ≠，得(),1a p =．推论 若p 是一个素数，a 是任意一个整数，则(),1a p =或(),a p p =． （5）若(),1a b =，则存在整数,s t ，使1as bt +=．（定理4推论） （6）若()(),1,,1a b a c ==，则(),1a bc =． 证明 由(),1a b =知存在整数,s t ，使1as bt +=． 有 ()a cs bct c +=， 得 ()(),,1a bc a c ==．（7）若(),1a b =，则(),1a b a ±=，(),1a b b ±=， (),1a b ab ±=． 证明 ()()(),,,1a b a b a b a ±=±==， ()(),,1a b b a b ±==， 由（6）(),1a b ab ±=．（8）若(),1a b =，则(),1m n a b =，其中,m n 为正整数． 证明 据（6），由(),1a b =可得(),1ma b =．同样，由(),1ma b =可得(),1m n a b =．定理6 设a 是大于1的整数，则a 的除1之外的最小的正约数q 必是素数，且当a 是合数时，q ≤证明 用反证法，假设q 不是素数，则存在正整数数1q ，11q q <<，使1|q q ，但|q a ，故有1|q a ，这与q 是a 的除1之外的最小正约数矛盾，故q 是素数．当a 是合数时，设1a a q =，则1a 也是a 的一个正约数，由q 的最小性得1q a ≤，从而21q a q a ≤=，开方得q ≤定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为12,,,n p p p ，作一个新数1211n p p p p =+>．若p 为素数，则与素数只有 n 个12,,,n p p p 矛盾．若p 为合数，则必有{}12,,,i n p p p p ∈，使|i p p ，从而|1i p ，又与1i p >矛盾．综上所述，素数不能只有有限多个，所以素数有无穷多个．2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．注：这个证明中，包含着数学归纳法的早期因素：若假设有n 个素数，便有1n +个素数．（构造法、反证法）秒定理8（整除的性质）整数,,a b c 通常指非零整数 （1）1a ，1|a -；当0a ≠时，|a a ，|0a ．（2）若b a ，0a ≠，则b a ≤;若b a ，b a >，则0a =;若0ab >，且,b a a b ，则a b =．证明 由b a ，0a ≠，有a bq =，得a b q b =≥． 逆反命题成立“若b a ，b a >，则0a =”; 由b a ≤且b a ≥得a b =，又0ab >，得a b =． （3）若a b c d +=+，且|,|,|e a e b e c ，则|e d ． （4）若c b ，b a ，则c a ． 证明 （定义法）由c b ，b a ，有 12,b q c a q b ==， 得 ()12a q q c =，即 c a ．（5）若c a ，则bc ab ．（6）若c a ，c b ，则对任意整数,m n ，有c ma nb +． 证明 （定义法）由c a ，c b ，有 12,a q c b q c ==， 得 ()12ma nb mq nq c +=+， 即 c ma nb +．（7）若(),1a b =，且a bc ，则a c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有()()a cs bc t c +=，因为a a ，a bc ，所以a 整除等式的左边，进而整除等式的右边，即a c ．注意 不能由a bc 且|a b /得出a c ．如649⨯，但6|4/且6|9/． （8）若(),1a b =，且,a c b c ，则ab c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有acs bct c +=，又由,a c b c 有12,c aq c bq ==代入得()()21ab q s ab q t c +=，所以ab c ．注意 不能由a c 且b c 得出ab c ．如不能由630且10|30得出60|30． （9）若a 为素数，且a bc ，则a b 或a c ．证明 若不然，则|a b /且|a c /，由a 为素数得()(),1,,1a b a c ==，由互素的性质（6）得(),1a bc =，再由a 为素数得|a bc /，与a bc 矛盾． 注意 没有a 为素数，不能由a bc 推出a b 或a c ．如649⨯，但6|4/且6|9/．定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡；若()|c a b -/，则称,a b 关于模c 不同余，记作a(mod )b c ．定理9（同余的性质）设,,,,a b c d m 为整数，0,m > （1）若(mod )a b m ≡且(mod )b c m ≡，则(mod )a c m ≡； 证明 由(mod )a b m ≡且(mod )b c m ≡，有 12,a b mq b c mq -=-=，()12a c m q q -=+，得(mod )a c m ≡．（2）若(mod )a b m ≡且(mod )c d m ≡，则(mod )a c b d m +≡+且(mod )ac bd m ≡． 证明 由(mod )a b m ≡且(mod )c d m ≡，有12,a b mq c d mq -=-=， ① 对①直接相加 ，有()()()12a c b d m q q +-+=+，得 (mod )a c b d m +≡+.对①分别乘以,c b 后相加，有()()()12ac bd ac bc bc bd m cq bq -=---=+，得 (mod )ac bd m ≡．（3）若(mod )a b m ≡，则对任意的正整数n 有(mod )nna b m =且(mod )an bn mn ≡. （4）若(mod )a b m ≡，且对非零整数k 有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 证明 由(mod )a b m ≡、，有 a b mq =+， 又(,,)k a b m ，有,,a b mk k k均为整数，且a b mq k k k=+， 得mod a b m k k k ⎛⎫≡ ⎪⎝⎭． 定理10 设,a b 为整数，n 为正整数， （1）若a b ≠，则()()nna b a b--．()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++．（2）若a b ≠-，则()()2121n n a b ab --++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+．（3）若a b ≠-，则()()22nn a b ab +-．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-．定义7 设n 为正整数，k 为大于2的正整数, 12,,,m a a a 是小于k 的非负整数，且10a >．若12121m m m m n a k a k a k a ---=++++，则称数12m a a a 为n 的k 进制表示．定理11 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．如12121101010m m m m n a a a a ---=++++，109,0i a a ≤≤>（10进制） 12121222m m m m n a a a a ---=++++．101,0i a a ≤≤>（２进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212k k n p p p ααα=，其中12k p p p <<<为素数，12,,,k ααα为正整数． （分解唯一性）证明1 先证明，正整数n 可分解为素数的乘积12m n p p p =． ①如果大于1的正整数n 为素数，命题已成立．当正整数n 为合数时，n 的正约数中必有一个最小的，记为1p ，则1p 为素数，有11n p a =，11a n <<．如果1a 为素数，命题已成立．当1a 为合数时，1a 的最小正约数2p 为必为素数，有11122n p a p p a ==，211a a n <<<．这个过程继续进行下去，由于n 为有限数，而每进行一步i a 就要变小一次，于是，经过有限次后，比如m 次，n 就变为素数的乘积12m n p p p =．下面证明分解式是唯一的．假设n 还有另一个分解式 12t n q q q =， ② 则有 1212m t p p p q q q =． ③因为等式的右边能被1q 整除，所以左边也能被1q 整除，于是1q 整除12,,,m p p p 中的某一个i p ，但i p 为素数，所以i p 与1q 相等，不妨设i p 为1p ，有11p q =．把等式③两边约去11p q =，得 2323m t p p p q q q =．再重复上述步骤，又可得22p q =，33p q =，…，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t <），则有121m m t q q q ++=． ④但12,,,m m t q q q ++均为素数，素数都大于1，有121m m t q q q ++>，这表明等式④不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按i p 的递增排列，并将相同的i p 合并成指数形式，即得1212k k n p p p ααα=．其中12k p p p <<<为素数，12,,,k ααα为正整数．证明2 用第二数学归纳法证明12m n p p p =，12m p p p ≤≤≤．（1）当2n =，因为2为素数，命题成立．（2）假设命题对一切大于1而小于n 的正整数已成立． 这时，若n 为素数，命题成立；若n 不为素数，必存在,a b ，使 n ab =，1,1a n b n <<<<， 由归纳假设，小于n 的,a b 可分解为素数的乘积//////1212//////1212, ,, ,s s s s t s s ta p p p p p pb p pp pp p ++++=≤≤≤=≤≤≤得 //////1212s s s t n p p p q q q ++=，适当调整/i p 的顺序，可得命题对于正整数n 成立．由数学归纳法，命题对一切大于1的正整数n 成立．下面证明分解式是唯一的．假设n 的分解式不唯一，则至少有两个分解式12m n p p p =，12m p p p ≤≤≤， 12t n q q q =，12t q q q ≤≤≤，得 1212m t p p p q q q =．有 112|t p q q q 且112|m q p p p ，这就存在,i j q p ，使1|i p q 且1|j q p ，但11,,,i j p q q p 均为为素数，所以11,i j p q q p ==，又 111i j p q q p p =≥=≥， 所以 11p q =．把等式两边约去11p q =，得 2323m t p p p q q q =．再重复上述步骤，又可得22p q =，33p q =，…，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t <），则有121m m t q q q ++=．但12,,,m m t q q q ++均为素数，素数都大于1，有121m m t q q q ++>，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按i p 的递增排列，并将相同的i p 合并成指数形式，即得1212k k n p p p ααα=．其中12k p p p <<<为素数，12,,,k ααα为正整数．定理13 若正整数n 的素数分解式为 1212k k n p p p ααα=则n 的正约数的个数为()()()()12111k d n a a a =+++，n 的一切正约数之和为()121111212111111k k k p p p S n p p p ααα+++---=⋅⋅⋅---． 证明 对于正整数1212k k n p p p ααα=，它的任意一个正约数可以表示为1212k k m p p p βββ=，0i i βα≤≤ ， ①由于i β有0,1,2,,i α共1i α+种取值，据乘法原理得n 的约数的个数为()()()()12111k d n a a a =+++．考虑乘积 ()()()12010101111222k kk k p p p p p p pp p ααα+++++++++，展开式的每一项都是n 的某一个约数（参见①），反之，n 的每一个约数都是展开式的某一项，于是，n 的一切约数之和为()()()110101111kk k S n p p p pp p αα=++++++121111212111111k k k p p p p p p ααα+++---=⋅⋅⋅---． 注 构造法．定义8 （高斯函数）对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+．定理14 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦．证明 由于p 为素数，故在!n 中p 的次方数是1,2,,n 各数中p 的次方数的总和（注意，若p 不为素数，这句话不成立）．在1,2,,n 中，有n p ⎡⎤⎢⎥⎣⎦个p 的倍数；在n p ⎡⎤⎢⎥⎣⎦个p 的倍数的因式中，有2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数；在2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数的因式中，有3n p ⎡⎤⎢⎥⎣⎦个3p 的倍数；…，如此下去，在正整数!n 的素因子分解式中，素数p 作为因子出现的次数就为23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦．注 省略号其实是有限项之和． 画线示意50!中2的指数．35678912450!23571113171923293137414347ααααααααα=定理15 （费玛小定理）如果素数p 不能整除整数a ，则()11p p a --．证明1 考察下面的1p -个等式： 11a pq r =+，10r p ≤<，222a pq r =+，20r p ≤<……()111p p p a pq r ---=+，10p r p -≤<由于素数p 不能整除整数a ，所以，p 不能整除每个等式的左边，得121,,,p r r r -均不为0，只能取1,2,,1p -．下面证明121,,,p r r r -各不相等．若不然，存在,,11t s t s p ≤<≤-，使,,,s s t t s t sa pq r ta pq r r r =+=+=相减 ()()s t s t a p q q -=-．应有素数p 整除()s t a -，但素数p 不能整除a ，所以素数p 整除()s t -，然而由11t s p ≤<≤-可得02s t p p <-≤-<， 要素数p 整除()s t -是不可能的，得121,,,p r r r -各不相等．有()()1211211!p rr r p p -=-=-．再把上述1p -个等式相乘，有 ()11211!p p p a Mp rr r ---=+，即 ()()11!1!p p a Mp p --=+-， 其中M 是一个整数．亦即 ()()11!1p p a Mp ---=．由于p 是素数，不能整除()1!p -，所以素数p 整除11p a --，得证()11p p a--证明2 改证等价命题：如果素数p 不能整除整数a ，则()mod pa a p ≡． 只需对1,2,,1a p =-证明成立，用数学归纳法．（1）1a =，命题显然成立．（2）假设命题对()11a k k p =≤<-成立，则当1a k =+时，由于()|1,2,,1i p p C i p =-，故有()11111ppp p p p k k C kC k --+=++++()11mod pk k p ≡+≡+．（用了归纳假设） 这表明，命题对1a k =+是成立． 由数学归纳法得()mod pa a p ≡．又素数p 不能整除整数a ，有(),1a p =，得()11p p a--．定义9 （欧拉函数）用()n ϕ表示不大于n 且与n 互素的正整数个数． 定理16 设正整数1212k k n p p p ααα=，则()12111111k n n p p p ϕ⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭．证明 用容斥原理．设{}1,2,,S n =，记i A 为S 中能被i p 整除的数所组成的集合（1,2,i k =），用i A 表示i A 中元素的个数，有 i inA p =，1212,,i j k i jkn n A A A A A p p p p p ==．易知，{}1,2,,S n =中与n 互素的正整数个数为12k A A A ，由容斥原理得()12111211k i i ji ki j kkijm k i j m kA A A S A A A A A A A A A ≤≤≤<≤≤<<≤=-+-++-∑∑∑()()1111211112121111*********.ki ki j k i j m k i i j i j mk ki ki j k i j m k i i j i j mk k n n nn n p p p p p p p p p n p p p p p p p p p n p p p ≤≤≤<≤≤<<≤≤≤≤<≤≤<<≤=-+-++-⎡⎤=-+-++-⎢⎥⎢⎥⎣⎦⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭∑∑∑∑∑∑ 注 示意3n =的容斥原理．推论 对素数p 有()()11,p p p p p αααϕϕ-=-=-．定理17 整系数不定方程ax by c +=（0ab ≠）存在整数解的充分必要条件是(),a b c ．证明 记(),d a b =．（1）必要性（方程有解必须满足的条件）．若方程存在整数解，记为00,,x x y y =⎧⎨=⎩，则00ax by c +=，由|,|d a d b ， 有00|d ax by +，得证(),|a b c ．（2）充分性（条件能使方程有解）．若|d c ，可设c de =由于形如ax by +的数中有最小正数00ax by +满足00ax by +(),a b =．两边乘以e ，得()()00a ex b ey c +=这表明方程有解00,.x ex y ey =⎧⎨=⎩定理18 若0ab ≠,(),1a b =，且00,,x x y y =⎧⎨=⎩是整系数不定方程ax by c +=的一个整数解，则方程的一切整数解可以表示为00,,x x bt y y at =-⎧⎨=+⎩()t Z ∈． ①证明 直接代入知①是方程的整数解，下面证明任意一个整数解都有①的形式. 由()00,x y 是方程的一个解，有00ax by c +=，又方程的任意一个解(),x y 满足ax by c +=， ② 相减 ()()000a x x b y y -+-=． ③ 但(),1a b =，故有 ()0|a y y -， 有00,x x y y t t Z b a--==∈- 得方程的任意一个整数解可以表示为 00,,x x bt y y at =-⎧⎨=+⎩()t Z ∈．定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．第二讲 数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．一、奇数与偶数整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n ，奇数可以表示为21n -或21n +．一般地，整数被正整数m 去除，按照余数可以分为m 类，称为模m 的剩余类(){}mod i C x x i m =≡，从每类中各取出一个元素i i a C ∈，可得模m 的完全剩余系（剩余类派出的一个代表团），0,1,2,,1m -称为模m 的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用． 关于奇数和偶数，有下面的简单性质：（1）奇数≠偶数．（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9． （3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；． （4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．（5）除2外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半． （7）偶数乘以任何整数的积为偶数．（8）两数和与两数差有相同的奇偶性，()mod2a b a b +≡-． （9）乘积为奇数的充分必要条件是各个因数为奇数． （10）n 个偶数的积是2n的倍数．（11）()11k -=的充分必要条件是k 为偶数，()11k-=-的充分必要条件是k 为奇数．（12）()()()()()()22220mod 4,211mod 4,211mod8n n n ≡-≡-≡． （13）任何整数都可以表示为()221mn k =-．……例1 （1906，匈牙利）假设12,,,n a a a 是1,2,,n 的某种排列，证明：如果n 是奇数，则乘积()()()1212n a a a n ---是偶数．解法1 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，奇数个奇数的和还是奇数奇数=()()()1212n a a a n -+-++-()()12120n a a a n =+++-+++=，这与“奇数≠偶数”矛盾． 所以()()()1212n a a a n ---是偶数．评析 这个解法说明()()()1212n a a a n ---不为偶数是不行的，但没有指出为偶数的真正原因．体现了整体处理的优点，但掩盖了“乘积”为偶数的实质．解法2 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，i a 与i 的奇偶性相反，{}1,2,,n 中奇数与偶数一样多，n 为偶数．但已知条件n 为奇数，矛盾． 所以()()()1212n a a a n ---是偶数．评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“n 为奇数”．那么为什么“n 为奇数”时“乘积”就为偶数呢？解法3 121,2,,,,,,n n a a a 中有1n +个奇数，放到n 个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得()()()1212n a a a n ---为偶数．评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“当n 为奇数时，1,2,,n 中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”． 类似题：例1-1（1986，英国）设127,,,a a a 是整数，127,,,b b b 是它们的一个排列，证明()()()112277a b a b a b ---是偶数．（127,,,a a a 中奇数与偶数个数不等）例1-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a 为该24个数字的任一排列，求证()()()12342324a a a a a a ---必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等） 例2 能否从1,2,,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14？解 考虑14个差的和S ，一方面1214105S =+++=为奇数．另一方面，每两个数,a b 的差与其和有相同的奇偶性 (mod2)a b a b -≡+，因此，14个差的和S 的奇偶性与14个相应数之和的和/S 的奇偶性相同，由于图中的每一个数a 与2个或4个圈中的数相加，对/S 的贡献为2a 或4a ，从而/S 为偶数，这与S 为奇数矛盾，所以不能按要求给图中的圆圈填数．评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．例4 有n 个数121,,,,n n x x x x -，它们中的每一个要么是1，要么是1-．若1223110n n n x x x x x x x x -+++++=，求证4|n ．证明 由{}1,1i x ∈-，有{}11,1i i x x +∈-，再由1223110n n n x x x x x x x x -+++++=，知n 个1i i x x +中有一半是1，有一半是1-，n 必为偶数，设2n k =．现把n 个1i i x x +相乘，有2222122311121(1)(1)1k kn n n n n x x x x x x x x x x x x ---+===，可见，k 为偶数，设2k m =，有4n m =，得证4|n ．例5 n 个整数121,,,,n n a a a a -，其积为n ，其和为0，试证4|n ．证明 先证n 为偶数，若不然，由121n n a a a a n -=知，121,,,,n n a a a a -全为奇数，其和必为奇数，与其和为0（偶数），故n 必为偶数．（121,,,,n n a a a a -中至少有1个偶数）再证n 为4的倍数，若不然，由n 为偶数知，121,,,,n n a a a a -恰有一个为偶数，其余1n -个数全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与121,,,,n n a a a a -之和为0矛盾，所以，n 为4的倍数，4|n ．（121,,,,n n a a a a -中至少有2个偶数）评析 要证4|n ，只须证121,,,,n n a a a a -中至少有2个偶数，分两步，第一步证至少有1个偶数，第二步证至少有2个偶数．例6 在数轴上给定两点1，在区间内任取n 个点，在此2n +个点中，每相邻两点连一线段，可得1n +条互不重叠的线段，证明在此1n +条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．证明 将2n +个点按从小到大的顺序记为122,,,n A A A +…，并在每一点赋予数值i a ，使1, 1,i i i A a A ⎧=⎨-⎩当为有理数点时，　当为无理数点时. 与此同时，每条线段1i i A A +也可数字化为1i i a a +（乘法）1111,, 1,,i i i i i i A A a a A A +++-⎧=⎨⎩　当一为有理数点，另一为无理数时， 当同为有理数点或无理数点时,记11i i a a +=-的线段有k 条，一方面112233412()()()()(1)(1)(1)k n k k n n a a a a a a a a -+++=-+=-…另一方面 12233412()()()()n n a a a a a a a a ++…21231212()1n n n a a a a a a a -++===-…，得()11k-=-，故k 为奇数． 评析 用了数字化、奇偶分析的技巧． 二、约数与倍数最大公约数与最小公倍数的求法． （1）短除法．（2）分解质因数法．设1212,0,1,2,,k k i a p p p i k αααα=≥=， 1212,0,1,2,,k k i b p p p i k ββββ=≥=．记 {}{}min ,,max ,i i i i i i γαβδαβ==， 则 ()1212,k k a b p p p γγγ=， []1212,k k a b p p p δδδ=．（3）辗转相除法()()()()()121,,,,,0n n n n a b b r r r r r r r -======．例7 （1）求()8381,1015，[]8381,1015； （2）()144,180,108，[]144,180,108． 解（1）方法1 分解质因数法．由283811729,10155729,=⨯=⨯⨯得 ()8381,101529=，[]28381,1015571729293335=⨯⨯⨯=．方法2 辗转相除法．883811015381207831261232823223229或23214221313823226110158381232232783812029232261q q q q r r r r ========或 ()()()()()8381,1015261,1015261,23229,23229,029=====． []()83811015838110158381,10158381352933358381,101529⨯⨯===⨯=．（2）方法1 短除法．由2144 180 108272 90 54336 30 27312 10 9 4 5 3得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．方法2 分解质因数法．由42222314423,180235,10823,=⨯=⨯⨯=⨯，得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．例8 正整数n 分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n 的最小值为 ．解 依题意，对最小的n ，则1n +是2,3,4,5,6,7,8,9,10的公倍数3212357n +=⨯⨯⨯，得2519n =．例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？解 相当于求不定方程15276x y +=的整数解． 由()15,273=知，存在整数,u v ，使15273u v +=，可得一个解2,1u v ==-，从而方程 ()1542726⨯+⨯-=．即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．例10 对每一个2n ≥，求证存在n 个互不相同的正整数12,,,n a a a ，使i j i j a a a a -+，对任意的{},1,2,,,i j n i j ∈≠成立．证明 用数学归纳法．当2n =时，取121,2a a ==，命题显然成立． 假设n k =时，命题成立，即存在12,,,k a a a ，使 i j i j a a a a -+，对任意的{},1,2,,,i j k i j ∈≠成立．现取b 为12,,,k a a a 及它们每两个数之差的最小公倍数，则1k +个数12,,,,k b a b a b a b +++满足 ()()()()()(),,t t ij i j a b b a b b a b a b a b a b ⎧+-++⎪⎨+-++++⎪⎩即命题对1n k =+时成立．由数学归纳法知命题对2n ≥成立．例11 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约．证明1 （反证法）假若214143n n ++可约，则存在1d >， ①使 ()214,143n n d ++=， 从而存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩②③消去n ，()()3322⨯-⨯，得()132d q p =-， ④ 的 1d =． ⑤由（1）、（5）矛盾，得1d =． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．（2）式④是实质性的进展，表明()()131432214n n =+-+， 可见 ()214,1431n n ++=． 由此获得2个解法．证明2 设()214,143n n d ++=．存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩①② 消去n ，②×3-①×2，得()132d q p =- ③ 得 1d =．证明3 由()()131432214n n =+-+ 得 ()214,1431n n ++=．证明4 ()214,143n n ++()71,143n n =++ ④ ()71,1n =+ ⑤1=．解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．例12 不存在这样的多项式()1110m m m m f n a n a n a n a --=++++，使得对任意的正整数n ，()f n 都是素数．证明 假设存在这样的多项式,对任意的正整数n ，()f n 都是素数，则取正整数n b =，有素数p 使()1110mm m m f b a b a ba b a p --=++++=，进而对任意的整数,k 有()()()()1110mm m m f b kp a b kp a b kp a b kp a --+=+++++++()1110m m m m a b a b a b a Mp --=+++++（二项式定理展开）()1P M =+，其中M 为整数，这表明()f b kp +为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数n ，()f n 都是素数． 三、平方数若a 是整数，则2a 就叫做a 的完全平方数，简称平方数． 1．平方数的简单性质（1）平方数的个位数只有6个：0,1,4,5.6.9．（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．（3）()()()()2220mod 4,211mod 4n n ≡-≡． （４）()()2211mod8n -≡．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．。

数学竞赛中的数论问题定理4 ,a b 是两个不同时为0的整数，若00ax by +是形如ax by +（,x y 是任意整数）的数中的最小正数，则（1）00ax by +|ax by +；（2）00ax by +(),a b =．证明 （1）由带余除法有()00ax by ax by q r +=++，000r ax by ≤<+， 得 ()()0000r a x qx x b y qy ax by =-+-<+，知r 也是形如ax by +的非负数，但00ax by +是形如ax by +的数中的最小正数，故0r =，即00ax by +|ax by +． （2）由（1）有00ax by +|10a b a +=g g ，00ax by +|01a b b +=g g ，得00ax by +是,a b 的公约数．另一方面，,a b 的每一个公约数都可以整除00ax by +，所以00ax by +是,a b 的最大公约数，00ax by +(),a b =．推论 若(),1a b =，则存在整数,s t ，使1as bt +=．（很有用）定理5 互素的简单性质： （1）()1,1a =．（2）(),11n n +=．（3）()21,211n n -+=． （4）若p 是一个素数，a 是任意一个整数，且a 不能被p 整除，则(),1a p =． 推论 若p 是一个素数，a 是任意一个整数，则(),1a p =或(),a p p =． （6）若()(),1,,1a b a c ==，则(),1a bc =．证明 由(),1a b =知存在整数,s t ，使1as bt +=．有 ()a cs bct c +=，得 ()(),,1a bc a c ==． （7）若(),1a b =，则(),1a b a ±=，(),1a b b ±=， (),1a b ab ±=．证明 ()()(),,,1a b a b a b a ±=±==，()(),,1a b b a b ±==，由（6）(),1a b ab ±=． （8）若(),1a b =，则(),1m n a b =，其中,m n 为正整数．证明 据（6），由(),1a b =可得(),1m a b =．同样，由(),1m a b =可得(),1m n a b =． 定理7 素数有无穷多个，2是唯一的偶素数．证明 假设素数只有有限多个，记为12,,,n p p p L ，作一个新数 1211n p p p p =+>g gL g ． 若p 为素数，则与素数只有 n 个12,,,n p p p L 矛盾．若p 为合数，则必有{}12,,,i n p p p p ∈L ，使|i p p ，从而|1i p ，又与1i p >矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个． 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．注：这个证明中，包含着数学归纳法的早期因素：若假设有n 个素数，便有1n +个素数．（构造法、反证法）定理8（整除的性质）整数,,a b c 通常指非零整数 （1）1a ，1|a -；当0a ≠时，|a a ，|0a ．（2）若b a ，0a ≠，则b a ≤;若b a ，b a >，则0a =;若0ab >，且,b a a b ，则a b =．证明 由b a ，0a ≠，有a bq =，得a b q b =≥．逆反命题成立“若b a ，b a >，则0a =”; 由b a ≤且b a ≥得a b =，又0ab >，得a b =． （7）若(),1a b =，且a bc ，则a c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有()()a cs bc t c +=， 因为a a ，a bc ，所以a 整除等式的左边，进而整除等式的右边，即a c ．（8）若(),1a b =，且,a c b c ，则ab c ．证明 由(),1a b =知存在整数,s t ，使1as bt +=，有acs bct c +=，又由,a c b c 有12,c aq c bq ==代入得()()21ab q s ab q t c +=，所以ab c ．注意 不能由a c 且b c 得出ab c ．如不能由630且10|30得出60|30． （9）若a 为素数，且a bc ，则a b 或a c ．证明 若不然，则|a b /且|a c /，由a 为素数得()(),1,,1a b a c ==，由互素的性质（6）得(),1a bc =，再由a 为素数得|a bc /，与a bc 矛盾．定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡；若()|c a b -/，则称,a b 关于模c 不同余，记作a(mod )b c ．定理9（同余的性质）设,,,,a b c d m 为整数，0,m >若(mod )a b m ≡且(mod )c d m ≡，则(mod )a c b d m +≡+且(mod )ac bd m ≡．证明 由(mod )a b m ≡且(mod )c d m ≡，有12,a b mq c d mq -=-=， ① 对①直接相加 ，有()()()12a c b d m q q +-+=+，得 (mod )a c b d m +≡+.对①分别乘以,c b 后相加，有()()()12ac bd ac bc bc bd m cq bq -=---=+，得 (mod )ac bd m ≡． （3）若(mod )a b m ≡，则对任意的正整数n 有(mod )nna b m =且(mod )an bn mn ≡.（4）若(mod )a b m ≡，且对非零整数k 有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 证明 由(mod )a b m ≡、，有 a b mq =+，又(,,)k a b m ，有,,a b mk k k均为整数，且 a b mq k k k=+，得 mod a b m k k k ⎛⎫≡ ⎪⎝⎭．定理10 设,a b 为整数，n 为正整数， （1）若a b ≠，则()()nna b a b--．()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++L ．（2）若a b ≠-，则()()2121n n a b ab --++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+L ．（3）若a b ≠-，则()()22nn a b ab +-．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-L ．定义7 设n 为正整数，k 为大于2的正整数, 12,,,m a a a L 是小于k 的非负整数，且10a >．若 12121m m m m n a ka k a k a ---=++++L ，则称数12m a a a L 为n 的k 进制表示．定理11 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．如12121101010m m m m n a a a a ---=++++L ，109,0i a a ≤≤>（10进制） 12121222m m m m n a a a a ---=++++L ．101,0i a a ≤≤>（２进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212kkn p p p ααα=L ，其中12k p p p <<<L 为素数，12,,,k αααL 为正整数． （分解唯一性）定理13 若正整数n 的素数分解式为 1212kkn p p p ααα=L 则n 的正约数的个数为()()()()12111k d n a a a =+++L ，n 的一切正约数之和为 ()121111212111111k k k p p p S n p p p ααα+++---=⋅⋅⋅---L ． 证明 对于正整数1212kk n p p p ααα=L ，它的任意一个正约数可以表示为1212kkm p p p βββ=L ，0i i βα≤≤ ， ①由于i β有0,1,2,,i αL 共1i α+种取值，据乘法原理得n 的约数的个数为()()()()12111k d n a a a =+++L ．考虑乘积()()()12010101111222k k k k p p p pp p p p p ααα+++++++++L L L L ， 展开式的每一项都是n 的某一个约数（参见①），反之，n 的每一个约数都是展开式的某一项，于是，n 的一切约数之和为()()()11101111kk kS n p p p pp p αα=++++++L L L 121111212111111k k k p p p p p p ααα+++---=⋅⋅⋅---L ． 注 构造法．定义8 （高斯函数）对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+． 定理14 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是 23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦L ． 证明 由于p 为素数，故在!n 中p 的次方数是1,2,,n L 各数中p 的次方数的总和（注意，若p 不为素数，这句话不成立）．在1,2,,n L 中，有n p ⎡⎤⎢⎥⎣⎦个p 的倍数；在n p ⎡⎤⎢⎥⎣⎦个p 的倍数的因式中，有2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数；在2n p ⎡⎤⎢⎥⎣⎦个2p 的倍数的因式中，有3n p ⎡⎤⎢⎥⎣⎦个3p 的倍数；…，如此下去，在正整数!n 的素因子分解式中，素数p 作为因子出现的次数就为23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦L ．注 省略号其实是有限项之和． 定理15 （费玛小定理）如果素数p 不能整除整数a ，则()11p p a--．证明2 改证等价命题：如果素数p 不能整除整数a ，则()mod pa a p ≡． 只需对1,2,,1a p =-L 证明成立，用数学归纳法． （1）1a =，命题显然成立．（2）假设命题对()11a k k p =≤<-成立，则当1a k =+时，由于()|1,2,,1ip p C i p =-L ，故有()11111ppp p p p k k C kC k --+=++++L ()11mod p k k p ≡+≡+．（用了归纳假设） 这表明，命题对1a k =+是成立． 由数学归纳法得()mod pa a p ≡．又素数p 不能整除整数a ，有(),1a p =，得()11p p a--．定义9 （欧拉函数）用()n ϕ表示不大于n 且与n 互素的正整数个数． 定理16 设正整数1212kkn p p p ααα=L ，则 ()12111111k n n p p p ϕ⎛⎫⎛⎫⎛⎫=--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭L ． 推论 对素数p 有()()11,p p p pp αααϕϕ-=-=-．．第二讲 数论题的范例讲解（12）()()()()()()22220mod 4,211mod 4,211mod8n n n ≡-≡-≡． （13）任何整数都可以表示为()221m n k =-．例1-1（1986，英国）设127,,,a a a L 是整数，127,,,b b b L 是它们的一个排列，证明()()()112277a b a b a b ---L 是偶数．（127,,,a a a L 中奇数与偶数个数不等）例1-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a L 为该24个数字的任一排列，求证()()()12342324a a a a a a ---L 必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）例2 能否从1,2,,15L 中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14L ？解 考虑14个差的和S ，一方面1214105S =+++=L 为奇数．另一方面，每两个数,a b 的差与其和有相同的奇偶性 (mod2)a b a b -≡+，因此，14个差的和S 的奇偶性与14个相应数之和的和/S 的奇偶性相同，由于图中的每一个数a 与2个或4个圈中的数相加，对/S 的贡献为2a 或4a ，从而/S 为偶数，这与S 为奇数矛盾，所以不能按要求给图中的圆圈填数．评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．例4 有n 个数121,,,,n n x x x x -L ，它们中的每一个要么是1，要么是1-．若1223110n n n x x x x x x x x -+++++=L L ，求证4|n ．证明 由{}1,1i x ∈-，有{}11,1i i x x +∈-，再由1223110n n n x x x x x x x x -+++++=L L ， 知n 个1i i x x +中有一半是1，有一半是1-，n 必为偶数，设2n k =．现把n 个1i i x x +相乘，有2222122311121(1)(1)1k kn n n n n x x x x x x x x x x x x ---+===g gL g g g L g ，可见，k 为偶数，设2k m =，有4n m =，得证4|n ．例6 在数轴上给定两点1，在区间内任取n 个点，在此2n +个点中，每相邻两点连一线段，可得1n +条互不重叠的线段，证明在此1n +条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．证明 将2n +个点按从小到大的顺序记为122,,,n A A A +…，并在每一点赋予数值i a ，使1, 1,i i i A a A ⎧=⎨-⎩当为有理数点时，　当为无理数点时.与此同时，每条线段1i i A A +也可数字化为1i i a a +（乘法） 1111,, 1,,i i i i i i A A a a A A +++-⎧=⎨⎩　当一为有理数点，另一为无理数时， 当同为有理数点或无理数点时,记11i i a a +=-的线段有k 条，一方面112233412()()()()(1)(1)(1)k n k k n n a a a a a a a a -+++=-+=-... 另一方面 12233412()()()()n n a a a a a a a a ++ (2)1231212()1n n n a a a a a a a -++===-…，得()11k-=-，故k 为奇数．评析 用了数字化、奇偶分析的技巧． 二、约数与倍数最大公约数与最小公倍数的求法． （1） 短除法．（2）分解质因数法．设1212,0,1,2,,k k i a p p p i k αααα=≥=L L ，1212,0,1,2,,k k i b p p p i k ββββ=≥=L L ．记 {}{}min ,,max ,i i i i i i γαβδαβ==，则 ()1212,k k a b p p p γγγ=L ，[]1212,k k a b p p p δδδ=L ．（3）辗转相除法 ()()()()()121,,,,,0n n n n a b b r r r r r r r -======L ． 例7 （1）求()8381,1015，[]8381,1015； （2）()144,180,108，[]144,180,108．解（1）方法1 分解质因数法．由283811729,10155729,=⨯=⨯⨯得()8381,101529=，[]28381,1015571729293335=⨯⨯⨯=． 方法2 辗转相除法．或 ()()()()()8381,1015261,1015261,23229,23229,029=====．[]()83811015838110158381,10158381352933358381,101529⨯⨯===⨯=．（2）方法1 短除法．由()22144,180,1082336=⨯=，得2144 180 108272 90 54336 30 27312 10 9 4 5 3[]43144,180,1082352160=⨯⨯=．方法2 分解质因数法．由42222314423,180235,10823,=⨯=⨯⨯=⨯，得 ()22144,180,1082336=⨯=，[]43144,180,1082352160=⨯⨯=．例8 正整数n 分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n 的最小值为 ． 解 依题意，对最小的n ，则1n +是2,3,4,5,6,7,8,9,10的公倍数3212357n +=⨯⨯⨯，得2519n =． 例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？ 解 相当于求不定方程15276x y +=的整数解．由()15,273=知，存在整数,u v ，使15273u v +=，可得一个解2,1u v ==-，从而方程 ()1542726⨯+⨯-=．即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．例10 对每一个2n ≥，求证存在n 个互不相同的正整数12,,,n a a a L ，使i j i j a a a a -+，对任意的{},1,2,,,i j n i j ∈≠L 成立．证明 用数学归纳法．当2n =时，取121,2a a ==，命题显然成立．假设n k =时，命题成立，即存在12,,,k a a a L ，使 i j i j a a a a -+，对任意的{},1,2,,,i j k i j ∈≠L 成立． 现取b 为12,,,k a a a L 及它们每两个数之差的最小公倍数，则1k +个数12,,,,k b a b a b a b +++L 满足 ()()()()()(),,t t ij i j a b b a b b a b a b a b a b ⎧+-++⎪⎨+-++++⎪⎩即命题对1n k =+时成立．由数学归纳法知命题对2n ≥成立．例11 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约．证明1 （反证法）假若214143n n ++可约，则存在1d >， ①使 ()214,143n n d ++=，从而存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩②③消去n ，()()3322⨯-⨯，得 ()132d q p =-， ④的 1d =． ⑤由（1）、（5）矛盾，得1d =． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．（2）式④是实质性的进展，表明 ()()131432214n n =+-+，可见 ()214,1431n n ++=．由此获得2个解法． 证明2 设()214,143n n d ++=．存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩①② 消去n ，②×3-①×2，得()132d q p =- ③ 得 1d =．证明3 由()()131432214n n =+-+ 得 ()214,1431n n ++=．证明4 ()214,143n n ++ ()71,143n n =++ ④()71,1n =+ ⑤ 1=． 解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．例12 不存在这样的多项式 ()1110mm m m f n a n a na n a --=++++L ，使得对任意的正整数n ，()f n 都是素数．证明 假设存在这样的多项式,对任意的正整数n ，()f n 都是素数，则取正整数n b =，有素数p 使 ()1110mm m m f b a b a ba b a p --=++++=L ，进而对任意的整数,k 有 ()()()()1110mm m m f b kp a b kp a b kp a b kp a --+=+++++++L()1110m m m m a b a b a b a Mp --=+++++L （二项式定理展开）()1P M =+，其中M 为整数，这表明()f b kp +为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数n ，()f n 都是素数．三、平方数若a 是整数，则2a 就叫做a 的完全平方数，简称平方数． 1．平方数的简单性质（1）平方数的个位数只有6个：0,1,4,5.6.9．（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．（3）()()()()2220mod 4,211mod 4n n ≡-≡．（４）()()2211mod8n -≡．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足222a b c +=的整数(),,a b c 叫做勾股数．勾股数的公式为2222,2,,a m n b mn c m n ⎧=-⎪=⎨⎪=+⎩其中,m n 为正整数，(),1m n =且,m n 一奇一偶．这个公式可给出全部素勾股数．2．平方数的证明方法（1）反证法．（2）恒等变形法．（3）分解法．设a 为平方数，且a bc =，(),1b c =，则,b c 均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法（1）若()221n x n <<+，则x 不是平方数．（2）约数有偶数个的数不是平方数．（3）个位数为2，3，7，8的数不是平方数．（4）同余法：满足下式的数n 都不是平方数．()2mod3n ≡， ()23mod4n ≡或， ()23mod5n ≡或， ()23567mod8n ≡或或或或，()2378mod10n ≡或或或．（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．如个位数与十位数都是都是奇数的数， 个位数是6、而十位数是偶数的数．例13 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，…，99，100．每盏灯由一个拉线开关控制着．最初，电灯全是关着的．另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解 （1）直接统计100次拉线记录，会眼花缭乱．（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次．（3）灯被拉的次数与亮不亮（开、关）有什么关系：灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数． （5）1～100中有哪些平方数：共10个：1，4，9，16，25，36，49，64，81，100．答案：编号为1，4，9，16，25，36，49，64，81，100共10个灯还亮．例14 已知直角三角形的两条直角边分别为正整数,a b ，斜边为正整数c ，若a 为素数，求证()21a b ++为平方数．证明 由勾股定理222c a b =+，有 ()()2c b c b a +-=，但a 为素数，必有 2,1,c b a c b ⎧+=⎨-=⎩解得 ()2112b a =-，从而 ()()()22212121a b a a a ++=+-+=+，为平方数．例15 求证，任意3个连续正整数的积不是平方数．证明 设存在3个连续正整数1,,1n n n -+（1n >）的积为平方数，即存在整数m ，使 ()()211n n n m -+=，即 ()221n n m -=，但()21,1n n -=，故21,n n -均为平方数，有2221,,,n a n b m ab ⎧-=⎪=⎨⎪=⎩得 ()222211211n a n n n =-≥--=->，（注意1n >）这一矛盾说明，3个连续正整数的积不是平方数．四．整除整除的判别方法主要有7大类．1．定义法．证b a a bq ⇔=，有三种方式．（1）假设a qb r =+，然后证明0r =．（定理4）（2）具体找出q ，满足a bq =．（3）论证q 的存在． 例18 任意一个正整数m 与它的十进制表示中的所有数码之差能被9整除．证明 设1110101010n n n n m a a a a --=⨯+⨯++⨯+L ，其中09,0i n a a ≤≤≠，则()()()(){{110111121111101101101911111111,n n nn n n n n n n m a a a a a a a a a a a ------++++=-+-++-⎛⎫=⨯-+⨯++⨯+ ⎪⎝⎭L L L L L 个个按定义 ()1109n n m a a a a --++++L ． 2．数的整除判别法．（1）任何整数都能被1整除．（2）如果一个整数的末位能被2或５整除，那么这个数就能被2或５整除． （3）如果一个整数的末两位能被４或25整除，那么这个数就能被4或25整除． （4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除． （5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除．证明 由()()101mod3,101mod9≡≡，有()1110110101010mod3n n n n n n a a a a a a a a ---⨯+⨯++⨯+≡++++L L ，3．分解法．主要用乘法公式．如()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++L ．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+L ．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-L ．例19 试证()()555129129++++++L L ．证明 改证()55545129+++L ．设555129S =+++L ，则()()()()()()()()()555555555512344123418273645918273645999,S m m m m m m m m =++++++++=++++++++=++++得9S ．又 ()()()()555555555192837465S =++++++++()()()()()5123441234192837465522225,m m m m m m m m =++++++++=++++得5S ．但()9,51=，得45S ，即()()555129129++++++L L ．例20 ()2111979,IMO -设p 与q 为正整数，满足111112313181319p q =-+--+L ，求证p 可被1979整除（1979p ） 证明111112313181319p q =-+--+L 1111111122313181319241318⎛⎫⎛⎫=+++++-+-+ ⎪ ⎪⎝⎭⎝⎭L L111111111231318131923659⎛⎫⎛⎫=+++++-++-+ ⎪ ⎪⎝⎭⎝⎭L L111166066113181319=++++L 6601319661131898999066013196611318989990+++=+++⨯⨯⨯L 19796606611319659!19791319!MM=⨯⨯⨯⨯=⨯L得1979整除1319!p ，但1979为素数，()1979,1319!1=，得p 可被1979整除．例20-1 2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908m n =+++L 的分子m 是吉祥数．证明：由111220090908m n =+++L 1111111200909082200909071004545410045455200909092009090920090909120090908220090907100454541004545520090909,122009090720090908p⎛⎫⎛⎫⎛⎫=++++++ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭=+++⨯⨯⨯=⨯⨯⨯⨯⨯L L L 其中p 为正整数，有 20090909122009090720090908n p m ⨯⨯=⨯⨯⨯⨯⨯L ，这表明，20090909整除122009090720090908m ⨯⨯⨯⨯⨯L ，但20090909为素数，不能整除122009090720090908⨯⨯⨯⨯L ，所以20090909整除m ，得m 是吉祥数．4． 余数分类法．例21 试证()()3121n n n ++．证明1 任何整数n 被3除其余数分为3类 3,31,32,n k n k n k k Z ==+=+∈，（1）3n k =时，有 ()()()()12133161,n n n k k k ++=++⎡⎤⎣⎦有()()3121n n n ++．（2）31n k =+时，有()()()()()1213313221,n n n k k k ++=+++⎡⎤⎣⎦ 有()()3121n n n ++．（3）32n k =+()()()()()121332165,n n n k k k ++=+++⎡⎤⎣⎦ 有()()3121n n n ++．综上得，()()3121n n n ++． 证明 2 ()()()()222211214n n n n n n ++++=，得 ()()322221n n n ++，又()3,41=，得()()3121n n n ++．5．数学归纳法．6．反证法．7．构造法． 例22 k 个连续整数中必有一个能被k 整除． 证明 设k 个连续整数为,1,2,,1a a a a k +++-L ，若这k 个数被k 除没有一个余数为0，则这k 个数的余数只能取1,2,,1k -L ，共1k -种情况，必存在两个数 ,,0a i a j i j k ++<-< ，使 1,a i kq r +=+2,a j kq r +=+ 其中12q q ≠，相减 ()12i j k q q -=-，有 12i j k q q k -=-≥， 即 i j k -≥与i j k -<矛盾．故k 个连续整数中必有一个能被k 整除．也可以由()12i j k q q -=-得 ()120i j k q q k <-=-<，推出1201q q <-<，与12q q -为整数矛盾．例23 k 个连续整数之积必能被!k 整除．证明 设k 个连续整数为,1,2,,1n n n n k +++-L ， （1）若这k 个连续整数为正整数，则()()()()121!!!!n n n n k n k k n k +++-=+L ()k nC =只须证明，对任何一个素数p ，分子中所含p 的方次不低于分母中所含p 的方次，由高斯函数的性质[][][]x y x y +≥+，有()s s s s k n k n k n k p p p p +-⎡⎤⎡⎤⎡⎤⎡⎤-=≥+⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦∑∑∑∑ 得k nC为整数（证实了组合数的实际意义）（2）若这k 个连续整数中有0，则连乘积为0，必能被!k 整除．（3）若这k 个连续整数为负整数，则()()()()()()()()()121!1211!1,k kk nn n n n k k n n n n k k C-+++--------+=-=-L L由（1）知kn C -为整数，故()()()121!n n n n k k +++-L 为整数．例24 有男孩、女孩共n 个围坐在一个圆周上（3n ≥），若顺序相邻的3人中恰有一个男孩的有a 组，顺序相邻的3人中恰有一个女孩的有b 组，求证3a b -．证明 现将小孩记作(1,2,,)i a i n =…，且数字化1,1, i i i a a a ⎧=⎨-⎩　表示男孩时表示女孩时则“3人组”数值化为12121212123,,,3,,,1,,,1,,,i i i i i i i i i i i i i i i i a a a a a a A a a a a a a a a a ++++++++++⎧⎪-⎪=++=⎨⎪⎪-⎩ 均为男孩 均为女孩 恰有一个女孩 恰有一个男孩其中n j j a a +=．又设取值为3的i A 有p 个，取值为3-的i A 有q 个，依题意，取值为1的i A 有b 个，取值为1-的i A 有a 个，得 12123234123()()()()n n a a a a a a a a a a a a +++=+++++++++……3(3)(1)3()()p q a b p q b a =+-+-+=-+-， 可见3a b -．例25 （1956，中国北京）证明3231122n n n ++-对任何正整数n 都是整数，并且用3除时余2． 分析 只需说明()23131222n n n n -+=为整数，但不便说明“用3除时余2”，应说明()()3212131222n n n n n n ++++=是3的倍数．作变形 ()()()32222213111,3,81228n n n n n n ++++-=-= ， 命题可证．证明 已知即()()321213111222n n n n n n ++++-=-， ① 因为相邻2个整数(),1n n +必有偶数，所以3231122n n n ++-为整数．又①可变为 ()()32222213111228n n n n n n ++++-=-，因为相邻3个整数()()2,22,21n n n ++必有3的倍数，故()()22221n n n ++能被3整除；又()3,81=，所以()()222218n n n ++能被3整除；得3231122n n n ++-用3除时余2．五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．例26 正方体的顶点标上1+或1-，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．证明 记14个数的和为S ，易知，这14个数不是1+就是1-，若八个顶点都标上1+，则14S =，命题成立．对于顶点有1-的情况，我们改变1-为1+，则和S 中有4的数,,,a b c d 改变了符号，用/S 表示改变后的和，由()0mod2a b c d +++≡知 ()/20mod 4S S a b c d -=+++≡， 这表明，改变一个1-，和S 关于模4的余数不变，重复进行，直到把所有的1-都改变为1+，则()/111142mod4S S ≡≡+++≡≡L ，所以，0S ≠．例27 设多项式()n n n n a x a x a x a x f ++++=--1110Λ的系数都是整数，并且有一个奇数α及一个偶数β使得()αf 及()βf 都是奇数，求证方程()0=x f 没有整数根．证明 由已知有()()()0121mod21mod2n fa a a a α≡⇔++++≡L ， ①()()()1mod21mod2n f a β≡⇔≡， ②若方程()0=x f 存在整数根0x ，即()00f x =．当0x 为奇数时，有()()()00120mod20mod2n f x a a a a ≡⇔++++≡L ，与①矛盾．有0x 为偶数时，有()()()00mod20mod2n f x a ≡⇔≡，与②矛盾．所以方程()0=x f 没有整数根． 六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．例28 解方程719213x y +=． 解法1 由()7,191=知方程有整数解． 观察特解，列表得一个特解0025,2,x y =⎧⎨=⎩从而通解为2519,27.x t y t =-⎧⎨=+⎩方法总结：第1步，验证(),a b c ，经常是(),1a b =．第2步，求特解（观察、列举、辗转相除等）． 第3步，代入公式．方法总结：()mod ax by c ax c b +=⇔≡或()mod by c a ≡． 例29 求方程3222009x x y +=的整数解． 解 由2009的分解式，有 ()222212009741xx y +=⨯=⨯，有 21,1,1,1004,1005,22009,x x x y y x y ==-⎧=⎧⎧⇒⎨⎨⎨==+=⎩⎩⎩ 227,7,7,17,24.241,x x x y y x y ==-⎧=⎧⎧⇒⎨⎨⎨==+=⎩⎩⎩例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）解法1 设甲、乙两队的队员按出场顺序分别为1234567,,,,,,A A A A A A A 和1234567,,,,,,B B B B B B B ．如果甲方获胜，设i A 获胜的场数是i x ，则07,17i x i ≤≤≤≤而且1277x x x +++=L ， ①容易证明以下两点：在甲方获胜时（i ）不同的比赛过程对应着方程①的不同非负整数解；（ii ）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：1A 胜1B 和2B ；3B 胜1A 、和3A ；4A 胜3B 后负于4B ；5A 胜4B 、5B 和6B 但负于7B ；最后6A 胜7B 结束比赛．下面求方程①的非负整数解个数，设1i i y x =+，问题等价于方程123456714y y y y y y y ++++++=，正整数解的个数，将上式写成1111111111111114+++++++++++++=，从13个加号取6个的方法数613C 种．得甲方获胜的不同的比赛过程有613C 种．同理，乙方获胜的不同的比赛过程也有713C 种，合计61323432C =种比赛过程例31（1989，高中）如果从数1，2，…，14中按由小到大的顺序取出123,,a a a ，使同时满足 21323, 3a a a a -≥-≥，那么，所有符合上述要求的不同取法有多少种？解 由已知得121323 10,30 30, 140,a a a a a a -≥--≥--≥-≥4项均为非负数，相加得()()()()121323133 147a a a a a a -+--+--+-=，于是123,,a a a 的取法数就是不定方程 12347x x x x +++=的非负整数解的个数，作一一对应11i y x =+，问题又等价于不定方 123411y y y y +++= 的正整数解．由 11111+++=L ，得310C 个解，即符合要求的不同取法有310C 种．七．数论函数主要是[]x 高斯函数，()n ϕ欧拉函数．例32 某学校要召开学生代表大会，规定各班每10人推选一名代表，当各班人数除以10的余数大于．．6．时再增选一名代表．那么，各班可推选代表人数y 与该班人数x 之间的函数关系用取整函数[]y x =（[]x 表示不大于x 的最大整数）可以表示为(A)10x y ⎡⎤=⎢⎥⎣⎦ (B)310x y +⎡⎤=⎢⎥⎣⎦ (C) 410x y +⎡⎤=⎢⎥⎣⎦ (D)510x y +⎡⎤=⎢⎥⎣⎦ （2010年全国高考数学陕西卷理科第10题）解法1 选（B ）．（求解对照）．规则是“六舍七入”，故加3即可进1． 选310x y +⎡⎤=⎢⎥⎣⎦． 解法2 选（B ）．（特值否定）．取56x =，按规定应选5人，可否定(C)、(D)；再取57x =，按规定应选6人，可否定(A)．注：主要错误选(C) ，误为“五舍六入”．例33 用[]x 表示不大于x 的最大整数，求122004366366366366⎡⎤⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦L ． 讲解 题目的内层有2004个高斯记号，外层1个高斯记号．关键是弄清[]x 的含义，进而弄清加法谁与谁加、除法谁与谁除：（1）分子是那些数相加，求出和来；由36651830200421963666⨯=<<=⨯，知分子是0～5的整数相加，弄清加数各有几个（2）除法谁除以366，求出商的整数部分．原式()036536612345175366⨯+++++⨯⎡⎤=⎢⎥⎣⎦1036687536614310236612.⨯+⎡⎤=⎢⎥⎣⎦⎡⎤=++⎢⎥⎣⎦= 命题背景2004年有12个月、366天．例34 50!的标准分解式中2的指数．解 35678912450!23571113171923293137414347ααααααααα=gg g g g 2的指数为2345505050505025126314722222⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤++++=++++=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦． 图示（5条横线，25个偶数中2的方次，按横线求和）八、综合练习例35 整数勾股形中，证明（1）必有一条直角边长是3的倍数；（2）必有一条直角边长是4的倍数； （3）必有一条边长是5的倍数；（4）三角形的面积是6的倍数．证明 当整数勾股形的三边有公约数时，可以先约去，使三边长,,x y z 互素，且满足222x y z +=.这时，若,x y 两个均为偶数，则z 也为偶数，与,,x y z 互素矛盾；若,x y 两个均为奇数，有()()221mod4,1mod4x y ≡≡，得 ()2222mod4z x y ≡+≡， 这与平方数模4只能取0，1矛盾.所以，,x y 中有且只有一个为偶数，不妨设x 为偶数.（1）设,x y 中无一为3的倍数，则()()221mod3,1mod3x y ≡≡，得 ()2222mod3z x y ≡+≡，这与平方数模3只能取0，1矛盾，故,x y 中有一个为3的倍数. （2）由x 为偶数.，必有,y z 均为奇数，记2,21,21x m y p z q ==+=+有 ()()()22222222421214m x z y q p q q p p ==-=+-+=+--则 ()()211m q q p p =+-+右边是两个偶数的差，必为偶数，从而x 为4的倍数.（3）若,x y 中有5的倍数，命题已成立. 若,x y 均不是5的倍数，则若,x y 只能是形如51k ±或52k ±的正整数.若,x y 均为51k ±型，则()222112mod5z x y ≡+≡+≡这与平方数模5只能取0，1，4矛盾若,x y 均为52k ±型，则()222443mod5z x y ≡+≡+≡这与平方数模5只能取0，1，4矛盾.所以，,x y 只能分别取51k ±与52k ±型，有 ()222410mod5z x y ≡+≡+≡得25z ，但5是素数，得5z .（4）由上证（1）、（2）及()3,41=知，xy 是12的倍数，则12xy 是6的倍数，得三角形的面积是6的倍数． 例36 已知ABC V 内有n 个点，连同,,A B C 共有3n +个点，以这些点为顶点，把ABC V 分割为若干个互不重叠的小三角形，现把,,A B C 分别染上红色、蓝色、黄色，而其余n 个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数．（斯潘纳定理）证明1 给这些小三角形的边赋值：当边的两端点同色时，记为0；当边的两端点异色时，记为1；再用三边之和给小三角形赋值：当三角形的三顶点同色时，和值为0，记这样的小三角形有a 个；当三角形的三顶点中仅有两点同色时，和值为2，记这样的小三角形有b 个；当三角形的三顶点两两异色时，和值为3，记这样的小三角形有c 个.下面用两种方法计算所有三角形赋值的总和S ，一方面02323S a b c b c =⨯+⨯+⨯=+. ①另方面，,,AB BC CA 的赋值均为1，和为奇数；而ABC V 内的每一条连线，在上述S 的计算中都被计算了两次，和为偶数；这两者之和得S 为奇数，记为21S k =+ ②由①，②得 2123k b c +=+可见c 为奇数，即三顶点都不同色的小三角形的总数必是奇数．（证明：n 个连续整数的乘积一定能被n!整除设a 为任一整数，则式： (a+1)(a+2)...(a+n) =(a+n)!/a! =n!*[(a+n)!/(a!n!)]而式中[(a+n)!/(a!n!)]恰为C(a+n,a),也即是从a+n 中取出a 的组合数，当然为整数。

高中数学竞赛知识点总结
高中数学竞赛涉及的知识点非常广泛，以下是一份简要的知识点总结：
1. 数论基础：包括整除、余数、最大公约数、最小公倍数等。

2. 代数：包括方程组、不等式、函数、数列等。

3. 平面几何：包括三角形、四边形、圆、相似形、解析几何等。

4. 立体几何：包括球、长方体、四面体等。

5. 平面解析几何：包括直线、二次曲线、极坐标等。

6. 组合数学：包括排列、组合、二项式定理、组合恒等式等。

7. 图论：包括图的性质、欧拉路径、哈密顿路径等。

8. 概率与统计：包括概率、期望、方差等。

9. 初等数论：包括同余、费马小定理、中国剩余定理等。

10. 数学逻辑与问题解决：包括逻辑推理、集合论、问题解决策略等。

以上仅为基础知识点，竞赛中还可能涉及更深层次的知识和技巧。

如果想要深入学习，建议查阅数学竞赛的相关教材或咨询专业教师。

数学竞赛中的数论问题第二部分 数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．一、奇数与偶数整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n ，奇数可以表示为21n -或21n +．一般地，整数被正整数m 去除，按照余数可以分为m 类，称为模m 的剩余类(){}mod i C x x i m =≡，从每类中各取出一个元素i i a C ∈，可得模m 的完全剩余系（剩余类派出的一个代表团），0,1,2,,1m -称为模m 的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用． 关于奇数和偶数，有下面的简单性质：（1）奇数≠偶数．（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9． （3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；． （4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．（5）除2外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半． （7）偶数乘以任何整数的积为偶数．（8）两数和与两数差有相同的奇偶性，()mod 2a b a b +≡-． （9）乘积为奇数的充分必要条件是各个因数为奇数． （10）n 个偶数的积是2n的倍数．（11）()11k-=的充分必要条件是k 为偶数，()11k-=-的充分必要条件是k 为奇数．（12）()()()()()()22220mod 4,211mod 4,211mod8n n n ≡-≡-≡． （13）任何整数都可以表示为()221mn k =-．……例1 （1906，匈牙利）假设12,,,n a a a 是1,2,,n 的某种排列，证明：如果n 是奇数，则乘积()()()1212n a a a n ---是偶数．类似题：例1-1（1986，英国）设127,,,a a a 是整数，127,,,b b b 是它们的一个排列，证明()()()112277a b a b a b ---是偶数．（127,,,a a a 中奇数与偶数个数不等）例1-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a 为该24个数字的任一排列，求证()()()12342324a a a a a a ---必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）例2 能否从1,2,,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14？例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？例4 有n 个数121,,,,n n x x x x -，它们中的每一个要么是1，要么是1-．若1223110n nn x x x x x x x x -+++++=，求证4|n ．例5 n 个整数121,,,,n n a a a a -，其积为n ，其和为0，试证4|n ．例6 在数轴上给定两点1，在区间内任取n 个点，在此2n +个点中，每相邻两点连一线段，可得1n +条互不重叠的线段，证明在此1n +条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．二、约数与倍数最大公约数与最小公倍数的求法． （1）短除法．（2）分解质因数法．设1212,0,1,2,,k k i a p p p i k αααα=≥=， 1212,0,1,2,,k k i b p p p i k ββββ=≥=．记 {}{}min ,,max ,i i i i i i γαβδαβ==， 则 ()1212,k k a b p p p γγγ=， []1212,k k a b p p p δδδ=．（3）辗转相除法()()()()()121,,,,,0n n n n a b b r r r r r r r -======．例7 （1）求()8381,1015，[]8381,1015； （2）()144,180,108，[]144,180,108．例8 正整数n 分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n 的最小值为 ．．例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？例10 对每一个2n ≥，求证存在n 个互不相同的正整数12,,,n a a a ，使i j i ja a a a -+，对任意的{},1,2,,,i j n i j ∈≠成立．例11 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约．例12 不存在这样的多项式 ()1110mm m m f n a n a na n a --=++++，使得对任意的正整数n ，()f n 都是素数． ．三、平方数若a 是整数，则2a 就叫做a 的完全平方数，简称平方数． 1．平方数的简单性质（1）平方数的个位数只有6个：0,1,4,5.6.9．（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．（3）()()()()2220mod 4,211mod 4n n ≡-≡． （４）()()2211mod 8n -≡．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足222a b c +=的整数(),,a b c 叫做勾股数．勾股数的公式为2222,2,,a m n b mn c m n ⎧=-⎪=⎨⎪=+⎩其中,m n 为正整数，(),1m n =且,m n 一奇一偶．这个公式可给出全部素勾股数．2．平方数的证明方法 （1）反证法． （2）恒等变形法．（3）分解法．设a 为平方数，且a bc =，(),1b c =，则,b c 均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法（1）若()221n x n <<+，则x 不是平方数．（2）约数有偶数个的数不是平方数．（3）个位数为2，3，7，8的数不是平方数． （4）同余法：满足下式的数n 都不是平方数．()2mod3n ≡， ()23mod4n ≡或， ()23mod5n ≡或，()23567mod8n ≡或或或或，()2378mod10n ≡或或或．（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．如个位数与十位数都是都是奇数的数， 个位数是6、而十位数是偶数的数．例13 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，…，99，100．每盏灯由一个拉线开关控制着．最初，电灯全是关着的．另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？例14 已知直角三角形的两条直角边分别为正整数,a b ，斜边为正整数c ，若a 为素数，求证()21a b ++为平方数．例15 求证，任意3个连续正整数的积不是平方数．例16 ()2311986,IMO -设d 是异于2，5，13的任一整数．求证在集合{}2,5,13,d 中可以找到两个不同元素,a b ，使得1ab -不是完全平方数．例17 (296IMO -)设,a b 为正整数，1ab +整除22a b +．证明221a b ab ++是完全平方数．四．整除整除的判别方法主要有7大类．1．定义法．证b a a bq ⇔=，有三种方式． （1）假设a qb r =+，然后证明0r =．（定理4） （2）具体找出q ，满足a bq =． （3）论证q 的存在．例18 任意一个正整数m 与它的十进制表示中的所有数码之差能被9整除．2．数的整除判别法． ()1011010mod3n n a a a a a a -++⨯+≡++++， ()1011010mod9n n a a a a a a -++⨯+≡++++如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或1210a a a()13132101001n n a a a a a a a -⨯--，()13210132101001n n n a a a a a a a a a a a --⇔⨯-，13，而7,11,13均为素数知，m 能被7或11或13()()()()11101110101010111mod11.n n n n nn n n a a a a a a a a ----⨯+⨯++⨯+≡-+-++-+3．分解法．主要用乘法公式．如()()123221n n n n n n n a b a b a a b a b ab b ------=-+++++．()()212122232422322n n n n n n n a b a b a a b a b ab b -------+=+-+--+．()()2221222322221n n n n n n n a b a b a a b a b ab b ------=+-+-+-．例19 试证()()555129129++++++．例20 ()2111979,IMO -设p 与q 为正整数，满足111112313181319p q =-+--+， 求证p 可被1979整除（1979p ）例20-1 2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908m n =+++的分子m 是吉祥数．4． 余数分类法．例21 试证()()3121n n n ++．例22 k个连续整数中必有一个能被k整除．例23 k个连续整数之积必能被!k整除．n≥），若顺序相邻的3人中恰有一例24 有男孩、女孩共n个围坐在一个圆周上（3-．个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3a b例25 （1956，中国北京）证明3231122n n n ++-对任何正整数n 都是整数，并且用3除时余2．五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．例26 正方体的顶点标上1+或1-，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．．例27 设多项式()n n n n a x a x a x a x f ++++=--1110 的系数都是整数，并且有一个奇数α及一个偶数β使得()αf 及()βf 都是奇数，求证方程()0=x f 没有整数根．六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．例28 解方程719213x y +=．例29 求方程3222009x x y +=的整数解．例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）例31（1989，高中）如果从数1，2，…，14中按由小到大的顺序取出123,,a a a ，使同时满足21323, 3a a a a -≥-≥，那么，所有符合上述要求的不同取法有多少种？七．数论函数主要是[]x 高斯函数，()n ϕ欧拉函数．例32 某学校要召开学生代表大会，规定各班每10人推选一名代表，当各班人数除以10的余数大于．．6．时再增选一名代表．那么，各班可推选代表人数y 与该班人数x 之间的函数关系用取整函数[]y x =（[]x 表示不大于x 的最大整数）可以表示为 (A)10x y ⎡⎤=⎢⎥⎣⎦ (B)310x y +⎡⎤=⎢⎥⎣⎦ (C) 410x y +⎡⎤=⎢⎥⎣⎦ (D)510x y +⎡⎤=⎢⎥⎣⎦ （2010年全国高考数学陕西卷理科第10题）例33 用[]x 表示不大于x 的最大整数，求 122004366366366366⎡⎤⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦．例34 50!的标准分解式中2的指数．八、综合练习例35 整数勾股形中，证明（1）必有一条直角边长是3的倍数；（2）必有一条直角边长是4的倍数；（3）必有一条边长是5的倍数；（4）三角形的面积是6的倍数．例36 已知ABC 内有n 个点，连同,,A B C 共有3n 个点，以这些点为顶点，把ABC 分割为若干个互不重叠的小三角形，现把,,A B C 分别染上红色、蓝色、黄色，而其余n 个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数．（斯潘纳定理）例37 对整点25边形的顶点作三染色，求证，存在一个三顶点同色的三角形，它的重心也是整点．。

初等数论简介绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。

1． 请看下面的例子：（1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。

(1894年首届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明2131n -是168的倍数。

②具有什么性质的自然数n ，能使123n ++++能整除123n ⋅⋅⋅（1956年上海首届数学竞赛第一题）（3） 证明：3231122n n n ++-对于任何正整数n 都是整数，且用3除时余2。

（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数214143n n ++不可约简。

（1956年首届国际数学奥林匹克竞赛第一题）（5） 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数，试证：[][][][]()()()()22,,,,,,,,,,a b c a b c a b b c c a a b b c c a =⋅⋅（1972年美国首届奥林匹克数学竞赛第一题）这些例子说明历来数论题在命题者心目中首当其冲。

2.再看以下统计数字：（1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。

（2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占% 。

这说明：数论题在命题者心目中总是占有一定的分量。

如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。

3.请看近年来国内外重大竞赛中出现的数论题：(1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ）A 、 0B 、1C 、3D 、无穷多（2007全国初中联赛5）（2）已知,a b 都是正整数，试问关于x 的方程()2102x abx a b -++=是否有两个整数解如果有，请把它们求出来；如果没有，请给出证明。

高中数学竞赛专题讲座---竞赛中的数论问题-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN竞赛中的数论问题的思考方法一. 条件的增设对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。

1. 大小顺序条件与实数范围不同，若整数x ，y 有大小顺序x <y ，则必有y ≥x +1，也可以写成y =x +t ，其中整数t ≥1。

例1. （IMO-22）设m ，n 是不大于1981的自然数，1)(222=--m nm n ，试求22n m +的最大值。

解：易知当m =n 时,222=+n m 不是最大值。

于是不访设n >m ,而令n =m +u 1，n >u 1≥1，得-2(m -1mu 1)(22112=--u mu m 。

同理，又可令m = u 1+ u 2，m >u 2≥1。

如此继续下去将得u k+1= u k =1，而11+-+=i i i u u u ，i ≤k 。

故n m u u u u k k ,,,,,,121 +是不大于1981的裴波那契数，故m =987，n =1597。

例2. （匈牙利—1965）怎样的整数a ，b ，c 满足不等式?233222c b ab c b a ++<+++解：若直接移项配方，得01)1()12(3)2(222<--+-+-c b b a 。

因为所求的都是整数，所以原不等式可以改写为：c b ab c b a 234222++≤+++，变形为：0)1()12(3)2(222≤-+-+-c b ba ，从而只有a =1，b =2，c =1。

2. 整除性条件对于整数x ，y 而言，我们可以讨论其整除关系：若x |y ，则可令y =tx ；若x ∤y ，则可令y =tx +r ，0<r ≤|x |-1。

高中数学竞赛 数论剩余类与剩余系1.剩余类的定义与性质(1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类((2)2.(1)a r ，得m 个数特别地,完全为偶数时,,2-m (2)证明:即证a 0,a 1,…,a m-1与aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系,因a 0,a 1,…,a m-1为模m 的完系时,若aa i +b ≡aa j +b(modm),则a i ≡a j (modm),矛盾!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,若a i ≡a j (modm),则有aa i +b ≡aa j +b(modm),也矛盾!(ⅲ)设m 1,m 2是两个互质的正整数,而x,y 分别遍历模m 1,m 2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!3.(1).在与模m的一个(2)(ϕm)x1≡x2,则a1,a2,…,aφ(m)是模m的一个既约剩余系.证明:因a1,a2,…,aφ(m)是)m(ϕ个与m互质的整数,并且两两对模m不同余,所以,a1,a2,…,aφ(m)属于)m(ϕ个剩余类,且每个剩余类都与m互质,故a1,a2,…,aφ(m)是模m的一个既约剩余系.(ⅴ)设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m 2x+m 1y 历遍模m 1m 2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1,(m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2x+m 1y, m 1m 2)=1.反之若(m 2x+m 1y, m 1m 2)=1,则(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2) =1,1m 2的既)(2m ϕ)., 1,α(4.欧拉欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,则)(m od 1)(m a m ≡ϕ. 证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r a ϕϕ)(21m r r r ϕ ,因()(21m r r r ϕ ,m)=1,所以,)(m od 1)(m a m ≡ϕ.推论(Fermat 定理) 设p 为素数,则对任意整数a 都有)(m od p a a p ≡.证明:若(a , p )=1,由1)(-=p p ϕ及Euler 定理得)(m od 11p a p ≡-即)(m od p a a p ≡;若(a , p )≠1,则p |a ,显然有)(m od p a a p ≡.例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .例(m 整除,.例m,使得2011|f n f 3因所以,例,是整数序列负整数假设对每个正整数:在数列123,,,a a a 中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣<k:若∣a k ∣≥k,则取n=∣a k ∣,则a 1≡a k ≡0(mod n),矛盾.现在对k 归纳证明a 1,a 2,…,a k 适当重排后是绝对值小于k 的k 个相邻整数.k=1显然.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i (0≤i ≤k -1),由于a 1,a 2,…,a k ,a k+1是(mod k+1)的一个完全剩余系,故必a k+1≡i+1(mod k+1), 但∣a k+1∣<k+1,因此a k+1只能是i+1或-(k -i),从而a 1,a 2,…,a k ,a k+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).若整数u 和v (u<v) 都出现在数列中,则u 与v 之间的所有整数也出现在数列中.得到:例,(i,j)也历mod2n 的和≡例可被,且是周期数列,所以, 数列{a n }中存在无穷多项可被2011整除.例7证明:存在无穷多个正整数n,使得n 2+1∤n!.证明:引理1对素数p >2,⇔≡)4(mod 1p 存在x(1≤x ≤p -1)使)(m od 12p x -≡. 证:充分性:因对1≤x ≤p -1,( p ,x)=1,所以,)(mod 1)(2121p x x p p ≡=--,≡-212)(p x)(mod 1)1(21p p ≡--,所以,21-p 为偶数,即).4(mod 1≡p 必要性:因1≤x ≤p -1时,x,2x,…,(p -1)x 构成modp 的既约剩余系,所以,存在1≤a ≤p -1,使得a x ≡-1(mod p ),若不存在a (1≤a ≤p -1), a =x,使a x ≡-1(mod p ),则这样的a ,x 共配成21-p 对,则有)(mod 1)!1()1(21p p p -≡-≡--,即21-p 为奇数,与 p 2证a =4(p 1p 设2p 1 p 2…12x -≡,相应的x 例(1)(2)n n+1n (n=1,2, …),且每个a n 都是f(x)的周期.证明：(1)设T=nm (正整数m,n 互质,且n ≥2),因(m,n)=1,所以,m,2m,…,nm 构成 modn 的完系,故存在k ∈N *使得km ≡1(modn),即存在t ∈N *使得km=nt+1,因f(x)=f(x+kT)=f(x+n km )=f(x+t+n 1)=f(x+n 1),所以n1是周期. 设n=kp ,其中k ∈N *, p 为素数,则n k p 11⋅=是周期.故存在素数p,使p 1是周期. (2)当T 为无理数时,取a 1=T,则T 为无理数, 0<T<1.设k≤n 时存在无理数a k ,使得0<a k <a k-1<1,且a k 是周期.对k+1,总存在存在u,v ∈N *,使得0<u a k -v<a k <1,取例解:,对任意}包含了modn+1零剩余,≤k ≤n, a 1+a 2+取例. 例11求所有的奇质数p ,使得∑=-11|k p k p .例12求所有质数p ,使得2122213)()()(|-+++p p p p C C C p .例13设n 为大于1的奇数,k 1,k 2,…,k n 是n 个给定的整数,对1,2,…,n 的每一个排列a=(a 1,a 2,…,a n ),记S(a)=∑=ni i i a k 1.证明:存在两个1,2,…,n 的排列b 和c(b ≠c),使得n!|S(b)-S(c).证明:如果对1,2,…,n 的任意两个不同排列b 和c(b ≠c),都有n!∤S(b)-S(c),那么当a 取遍所有排列时(共n!个),S(a)遍历模n!的一个完系, 因此,有∑a a S )(≡1+2+…+n!≡2!2)1!(!n n n ≡+(modn!) ①, 另一方面,我们有 ∑a a S )(=)!(mod 0)1(!])!1[(n k n n j n k a k a k n i n n in i i n i i ≡+=-==∑∑∑∑∑∑∑ ②. 由①∑a .例modm 因(m,2n 例x 例在A同余方程与同余方程组1.同余方程(组)及其解的概念定义1 给定正整数m 及n 次整系数多项式0111)(a x a x a x a x f n n n n ++++=--，则同余式f(x)≡0(modm)①叫做模m 的同余方程,若a n 0(modm),则n 叫做方程①的次数.若x=a是使f(a)≡0(modm)成立的一个整数,则x≡a(modm)叫做方程①的一个解,即把剩余类a(modm)叫做①的一个解.若a1(modm),a2(modm)均为方程①的解,且a1,a2对模m不同余,就称它们是方程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.例12解:例2解:.2.设a x解,例3解:tx即)8-≡x.3,1-(mod≡t),1,08(mod1=4+例4解方程12x≡6(mod9).因(12,9)=3,且-1是一个特解,所以,方程12x≡6(mod9)的解为:(modx即)8t5,2,1，≡t≡-x.(mod),2,1,083+1=-3.同余方程组定义3给定正整数m 1,m 2,…,m k 和整系数多项式f 1(x),f 2(x),…,f k (x),则同余式组 ⎪⎪⎩⎪⎪⎨⎧≡≡≡)(mod 0)()(mod 0)()(mod 0)(2211k k m x f m x f m x f ②,叫做同余方程组.若x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,则x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.例5解:⎩⎨⎧-≡≡13x x .M=m 1m ⎪⎪⎩⎪⎪⎨⎧≡≡≡21k a x a x a x 其中M j ).(2)j j j j 则x ≡y (modm j ),即m j |x -y ,因m 1,m 2,…,m k 两两互质,所以M| x-y 即x ≡y (modM). 注:(1)存在无穷多个整数x 满足同余方程组③,这些x 属于同一模m 的剩余类;(2)同余方程组③仅有一个解x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM).(3)当(a ,m i )=1(=1,2,…,n)时,同余方程组⎪⎪⎩⎪⎪⎨⎧≡≡≡⇔⎪⎪⎩⎪⎪⎨⎧≡≡≡---)(mod )(mod )(mod )(mod )(mod )(mod 12211112211k k k k m a a x m a a x m a a x m a ax m a ax m a ax仍然具有定理结论. 这在数论解题中具有重要应用.例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何”.解,352115≡x 例.解:210×210-1≡210-1≡1(mod11)⇔210-1≡1(mod11),所以,同余方程组的解为: )2310(mod 2111637121010330438553462≡=⨯+⨯+⨯+⨯≡x ,即x=2310k+2111(k ∈N).例8证明:对任意n 个两两互质的正整数:m 1,m 2,…,m n ,总存在n 个连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).证明:由剩余定理知,总存在整数k 使得⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡)(mod )(mod 2)(mod 121n m n k m k m k,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).例9证明:对任意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当 数⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡21n m m m例,且A 例 {k +a n }⎩⎨⎧-≡≡)(mod 102p x x 123⎪⎩-≡)(mod 232p x 2的最小正整数a 2=38.假定a 1,a 2,…,a n 都已确定,则取a n+1适合⎪⎪⎩⎪⎪⎨⎧-≡-≡≡+)(mod )(mod 1)(mod 0121n p n x p x p x 且大于a n 的最小正整数,由剩余定理知满足条件的a n+1存在.则上述递推关系定义的数列{a n }满足题意:因对任意k ∈N *,当n ≥k+1时,都有k+a n ≡0(mod p k+1),由{a n }递增可知{k +a n }从第k+2项起每一项都是p k+1的倍数,且都大于p k+1,所以,数列{k +a n }中至多有k+1项为素数.例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对任意正整数k ，该数列的前k 项之和是k 的倍数？解:,S=a 1+a 2⎩⎨⎧++≡+t r S r S {a n }例的质因数.例例。

【高中数学竞赛专题大全】 竞赛专题15 初等数论 （50题竞赛真题强化训练）一、填空题1．（2020·浙江·高三竞赛）将1~2020的数字按顺时针方向围成一个圆圈，然后从1开始，按顺时针依次隔一个数拿走，即拿走1，3，5，…，这个过程一直进行下去，直到剩下最后一个数字，则最后剩下的数字是___________. 【答案】1992. 【解析】 【详解】在第一轮中，从1开始到拿走1991，共取走996个数，此时余下1024个数， 1991后一项偶数为1992，此后共取10次，余下的数为1992， 故答案为:1992.2．（2021·全国·高三竞赛）关于x 、y 的方程11112007x y xy ++=的正整数解(,)x y 的个数为________． 【答案】48 【解析】 【详解】解析：由11112007x y xy ++=得2007200720070xy x y ---=，整理得 32(2007)(2007)2007200823223251x y --=⨯=⨯⨯⨯，从而，原方程的正整数解有(31)(21)(11)(11)48++++=（个）． 故答案为：48.3．（2021·全国·高三竞赛）{}n a 为正整数列，满足112,n a a +=为213133n n a a -+的最小素因子，12,,,,n a a a ，构成集合A ，P 为所有质数构成的集合，则集合P A 的最小元素为___________． 【答案】5 【解析】由于122,3a a ==，故2,3A ∈，所以集合P A -的最小元素5≥．假设存在正整数n ，使得5(3)n a n =≥，则211513133n n a a ---+，故()21512n a -++，这不可能，因为()212n a ++除以5的余数为1,3， 所以5P A ∈-．集合P A -的最小元素为5． 故答案为：5.4．（2021·全国·高三竞赛）质数p 和正整数m 满足32(2)1p m p m p ++=++，则p m +=___________.【答案】7 【解析】 【详解】由()221(1)p p m m +-=-，易见1m ，所以1p m -.设()1m kp k N +-=∈，则()2222,,(1)p p kp k p p k k p k k +=+==-.所以2k =，2,5p m ==，7p m +=.5．（2021·浙江·高三竞赛）已知集合{}12,,,n A a a a =⋅⋅⋅，n 为正整数.若对任意的1i j n ≤≠≤，i j a a -被4整除，但不被16整除，则n 的最大值为______.【答案】4 【解析】 【分析】 【详解】 考虑同余：对任意的1,i j i j n a a ≤≠≤-被4整除,则有(mod 4)i j a a k ≡≡,其中{0,1,2,3}k ∈, 而这类型的数模16的余数至多只有4种,所以n 最大值为4. 故答案为：4.6．（2021·浙江·高二竞赛）设数列123n n n a a a +⎡⎤⎡⎤=+⎢⎥⎢⎥⎣⎦⎣⎦，1n =，2，…，7这里[]x 表示不超过x的最大整数.若88a =，则正整数1a 有______种可能的取值情况.【解析】 【分析】根据高斯函数的性质，由88a =逐次往前求， 注意先定范围再验证，即可得到答案. 【详解】由88a =，可得710a =或11， 可得612a =或13或14； 可得515a =或16或17； 可得418a =或19或20或21； 可得322a =或23或24或25或26； 可得227a =或28或29或30或31或32；可得133a =或34或35或36或37或38或39，共7种.7．（2021·全国·高三竞赛）所有能使25n ⎡⎤⎢⎥⎣⎦为质数的正整数n 的倒数和为_________．【答案】3760【解析】 【分析】 【详解】1,2,3n =时，25n ⎡⎤⎢⎥⎣⎦都不是质数；4n =时，235n ⎡⎤=⎢⎥⎣⎦是质数；5n =时，255n ⎡⎤=⎢⎥⎣⎦是质数；6n =时，275n ⎡⎤=⎢⎥⎣⎦是质数．当8n ≥时，可设5n k r =±（其中k 为不小于2的正整数，0,1r =或2），则()22222111(5)2510(52)5555n k r k kr r k k r r =±=±+=±+， 所以2(52)5n k k r ⎡⎤=±⎢⎥⎣⎦．因为2k ≥，所以522k r ±>，所以2(52)5n k k r ⎡⎤=±⎢⎥⎣⎦不是质数．因此，能使25n ⎡⎤⎢⎥⎣⎦为质数的正整数n 只有4、5、6，它们的倒数和为1113745660++=．故答案为：3760. 8．（2021·全国·高三竞赛）若2020在p 进制下的各位数字之和为5p +，则质数p 的所有可能值为___________. 【答案】2,107 【解析】 【分析】 【详解】类似于在十进制下，我们有()()120|205p p --+⎡⎤⎣⎦， 于是()12014195|23p -=⨯⨯， 再注意p 为质数，就有2,3,107p =， 逐一验证得2p =或107p =. 故答案为：2,107.9．（2021·全国·高三竞赛）在1，2，3，4，…，1000中，能写成()221a b a N -+∈的形式，且不能被3整除的数有________个． 【答案】501. 【解析】 【详解】 设{}1,2,3,4,,1000S =，若221n a b =-+，则()3mod4n ≠.又()()2242211k k k =--+，()()2241111k k k +=+--+，()()22422121k k k +=+-+，因此，221n a b =-+当且仅当()3mod44n ≠.令(){|3mod44}A a S a =∈≡，(){|0mod3}B b S b =∈≡，则(){|3mod12}A B c S c ⋂=∈≡，因为250A =，333B =，84A B ⋂=，从而符合条件的数的个数为100025033384501--+=. 故答案为50110．（2020·浙江·高三竞赛）设a ，b ，c 为正整数，且2225548450a b c ab ac bc ++-+-=，则所有的解中a b c ++的最大值为___________. 【答案】30. 【解析】 【详解】配方得：222(22)50a c b a c ++--=（a ，c 等价）. 注意到：22250017=++，22250055=++，22250345=++. 不妨设a c ≤且22b a c ≥+，（1）当22017b a c a c --=⎧⎪=⎨⎪=⎩，即1167a b c =⎧⎪=⎨⎪=⎩，此时116724a b c ++=++=.（2）当22055b ac a c --=⎧⎪=⎨⎪=⎩，即5205a b c =⎧⎪=⎨⎪=⎩，此时520530a b c ++=++=.（3）当22534b a c a c --=⎧⎪=⎨⎪=⎩，即3194a b c =⎧⎪=⎨⎪=⎩，此时319426a b c ++=++=.（4）当22435b ac a c --=⎧⎪=⎨⎪=⎩，即3205a b c =⎧⎪=⎨⎪=⎩，此时320528a b c ++=++=.（5）当22345b a c a c --=⎧⎪=⎨⎪=⎩，即4215a b c =⎧⎪=⎨⎪=⎩，此时421530a b c ++=++=.综上所述，所有的解中a b c ++的最大值为30. 故答案为：30.11．（2020·江苏·高三竞赛）设正整数a ，b ，c ，d 满足23a b =，45c d =，且303b d -=，则a c -的值为___________． 【答案】123801 【解析】 【详解】解析：由题意可得a =c =b 必为完全平方数，d 一定能开4次方．设2b n =，4d m =，则()()223101b d n m n m -=+-=⨯，且注意到3，101都是质数，则223031n m n m ⎧+=⎨-=⎩或者221013n m n m ⎧+=⎨-=⎩，解得52n =，7m =，则35123801a c n m -=-=． 故答案为：123801.12．（2020·江苏·高三竞赛）设,m n N ∈，,2m n ≥，若33333333213111213112n m n m ----⋅=++++，则m n +的值为___________． 【答案】6 【解析】 【详解】解析：因为3311(1)111(1)1n n n n n n n n --++=⋅++-+， 累乘可得原式22(1)1222(1)33(1)n n n n n n n n ++++=⋅=++，则232333323122211n n m n n m m ++==+++--， 故223232221n n n n m +-=++-， 从而可得()2326131816162(1)(2)(1)(2)n n m n n n n n n ++⎛⎫-==+=+ ⎪+--+-+⎝⎭， 则()()1218n n -+，且,2m n ≥，在()()12n n -+的值为6，9，18， 故4n =，2m =．故6m n +=． 故答案为：6.13．（2021·浙江·高三竞赛）将顺序为1，2，…，2020的2020张卡片变成1011，1，1012，2，…，2020，1010的顺序，即原先的前1010张卡片移至第2，4，…，2020张，这称为一次操作.若从顺序1，2…，2020开始操作，则至少经过______次操作可以恢复到初始顺序. 【答案】1932 【解析】 【分析】 【详解】记第1i 次调整前的位置为i a ,调整后的位置记为1i a +,初始位置记为0a ,则112,101022021,1010i i i i a a a a a +≤⎧=⎨->⎩,所以102(mod 2021)2(mod 2021)n i i n a a a a +≡⇒≡, 因20214347=⨯,所以(2021)(43)(47)1932ϕϕϕ==, 所以193221(mod 2021)≡,要恢复原样,则0n a a =, 所以1932n =. 故答案为：1932.14．（2019·广西·高三竞赛）满足y =(x ，y )有____________ 对. 【答案】6 【解析】 【详解】设2251,2019,,n x m x n N m N =+=+∈∈. 224()()19682341m n m n m n -=+-==⨯⨯，由(m +n )与(m －n )奇偶性相同，可知它们同为偶数，且(m +n )>(m －n ) 实数对(m +n ，m －n )所有可能的取值共有6对：()32341,2⨯⨯，()322341,2⨯⨯，()32341,2⨯⨯， ()3241,23⨯⨯，()22241,23⨯⨯，()3241,23⨯⨯.由有序数对(x ，y )与(m +n ，m －n )一一对应，可知所求正整数对为6对. 故答案为：6．15．（2019·四川·高三竞赛）若正整数n 使得方程33n x y z +=有正整数解(x ，y ，z )，称n 为“好数”.则不超过2019的“好数”个数是_____ . 【答案】1346 【解析】 【详解】首先易知若n 为“好数”，则n +3也是“好数”又显然1、2是“好数”，从而当1,2(mod3)n ≡时，n 均为“好数”. 由费马(Fermat )大定理知：333x y z +=无正整数解，即3不是“好数”.于是n =3k (k ∈N *)都不是“好数”.否则，存在k ∈N *，使得3k 是“好数”，即方程333k x y z +=有正整数解(x ，y ，z 0)，从而333x y z +=有正整数解()000,,kx y z ，矛盾！故当且仅当n 满足1,2(mod3)n ≡时，n 为“好数”. 所以，不超过2019的“好数”个数是2201913463⨯=. 故答案为：1346． 二、解答题16．（2021·全国·高三竞赛）求证：对于正整数n ，令22n a ⎡⎡=+⎣⎣，数列{}n a 中有无穷多个奇数和无穷多个偶数（[]x 表示不超过实数x 的最大整数）． 【答案】证明见解析 【解析】 【详解】1212101100.101100bb c c =⋅⋅⋅=⋅⋅⋅⋅， 其中{}{}0,1,0,1i i b c ∈∈.用反证法，先证明数列中有无穷多个偶数．假设，数列中只有有限个偶数，那么存在整数N ，n N ∀>，n a 是奇数， 则存在正整数M ，使得1212101100101100M n M a bb b c c c =+，且当n M >时，{},{0,1}n n b c =，12(2)110110011N d d d ⋅∈Q ，矛盾！同理可证明数列中有无穷多个偶数．所以数列{}n a 中有无穷多个奇数和无穷多个偶数．17．（2021·全国·高三竞赛）使得A =n 为_________． 【答案】1或11##11或1 【解析】 【详解】,,,(,)1aa b a b b+=∈=N ，则222222222917647799n a a b b n n b b a b a -+=⇒==-++--． 又(,)1a b =，所以()()22222,9,1b b a b a -==，故22964b a -，所以229(3)(3){1,2,4,8,16,32,64}b a b a b a -=+-∈，229b a -模3余2，故2298b a -=或32，故3831b a b a +=⎧⎨-=⎩或3432b a b a +=⎧⎨-=⎩或33231b a b a +=⎧⎨-=⎩或31632b a b a +=⎧⎨-=⎩或3834b a b a +=⎧⎨-=⎩，所以(,)(1,1)=a b 或(7,3)，因此n 为1或11． 故答案为：1或11.18．（2021·全国·高三竞赛）设n 是正整数，12,,,k d d d 是n 的全部正因数.定义1212()(1)(1)(1)k d d d k f n d d d =-+-++-，已知()f n 是2的幂次，求证：n 没有1之外的平方因数.【答案】证明见解析 【解析】 【分析】设2(1)rn s r =≥，其中1i tai i s p ==∏，利用因数和函数可得()f n 与各质因数的关系，再根据()f n 是2的幂次结合反证法可得1i a =，从而可n 没有1之外的平方因数. 【详解】用()n σ表示n 的正因数之和.如果n 是奇数，则()()0f n n σ=-<，舍去. 当n 是偶数时，设2(1)r n s r =≥，其中1i tai i s p ==∏（i p 为n 的奇质因数，i a +∈N ，3i p ≥）.所以()()()111()2221()23i ta rr r i i f n s p σσ-+==+++-=-∏.其中()21i i a a i i i i p p p p σ=++++，因为()f n 是2的幂次，所以1231,1r r +-==，每个()i ai p σ是2的幂次，且i a 是奇数，又()()()12246111i i i a a a i i i i i i i i i p p p p p p p p p σ-=++++=++++++，故1246,11i a i i i i i p p p p p -++++++均为4的倍数，因为23,1(mod 4)i i p p ≥≡，所以如果1i α>，则1241,,,,i a i i i p p p -这些数的总个数是4的倍数，所以12211i a i i i p p p -++++.因为212(mod 4)i p +≡，所以121i a i i p p -+++不是2的幂次，于是1i a >不成立.所以1i a =，所以1ti i s p ==∏（i p 为互异的奇质因数），12ti i n p ==∏，可见n 没有非平凡的平方因数. 【点睛】思路点睛：竞赛中与正因数和有关的问题，多用因数和函数来分析处理，令注意利用因数分解定理把因数问题转化为即质因数的问题来处理.19．（2021·全国·高三竞赛）用()P n 表示正整数n 的各位数字之和，求所有这样的三位数n ，使得满足：1(3)()3P n P n +=．【答案】117、207、108. 【解析】 【分析】 【详解】由于(),(3)P n P n +都是正整数，则据条件，()P n 是3的倍数，因此n 与3n +都是3的倍数． 设n abc =，且数n 加3后必须产生进位，则7c ≥．（因为，如果6c ≤，则数n 加3后不会产生进位，于是(3)()3()P n P n P n +=+>，矛盾）并且b 不能是9，这是因为，若9b =，则当9a =时，99n c =，数n 加3后成为1100c ，1{0,1,2}c ∈，这时1(3)()3P n P n +<．当9a <时，9n a c =，若1113n a b c +=，则1111,0,310a a b c c =+==+-． 由3(3)()P n P n +=，得3[(1)0(310)]9a c a c ++++-=++， 即2()27a c +=，矛盾！所以9b <．今由3[(1)(310)]a b c a b c ++++-=++得9a b c ++=，其中1,7,8a c b ≥≥≤， 依次考虑c 、a 、b 的取值，得到三个数：117、207、108，验证知，它们皆合题意． 20．（2021·全国·高三竞赛）已知a 、b 、c 、d 是不同的正整数，且满足a b c da b b c c d d a+++++++是整数，求证：+++a b c d 不是质数． 【答案】证明见解析. 【解析】 【分析】 【详解】 由1a b c d a b c da b b c c d d a a b c d a b c d a b c d a b c d +++>+++=++++++++++++++++， 且a b c da b b c c d d a+++++++ 1111b c d aa b b c c d d a=-+-+-+-++++ 43b c d a a b b c c d d a ⎛⎫=-+++< ⎪++++⎝⎭，所以2a b c d a b b c c d d a+++=++++， 故2a c b d c aa b c d b c d a b c d a+=--=+++++++， 因此1111a c a b d a b c c d ⎛⎫⎛⎫-=- ⎪ ⎪++++⎝⎭⎝⎭， 所以()()()()d b d b a c a b d a b c c d --⋅=⋅++++且d b ≠， 所以()()()()a b c c d c a b d a ⋅++=⋅++，即22ac abd a c bcd +=+． 整理得()()0ac c a bd a c -+-=且a c ≠，所以ac bd =． 假设p a b c d =+++是质数，则 2()a a b c d a ab ac ad +++=+++ 2a ab bd ad =+++ ()()a b a d ap =++=，所以()p a b +或()p a d +，而,p a b p a d >+>+，矛盾． 综上+++a b c d 不是质数．21．（2021·全国·高三竞赛）解关于实数x 的方程：{}202020201arctank x x k==∑（这里{}[][],x x x x =-为不超过实数x 的最大整数） 【答案】{}0 【解析】 【分析】【详解】（1）当0x <时，{}202020201arctan 0(1,2,,2020),arctan 0k x x k x k k =<=<≤⋅⋅⋅∑，此时原方程无解．（2）当0x =时，有{}202020001arctan0k x x k===∑． （3）当01x <<时，令arct ()1)2an (0x xf x x =-<<，则211()0(01)12f x x x '=-><<+， 故()f x 在()0,1上递增．有()()00f x f >=，即arctan 2x x > 于是，此时{}202020204202020201111125arctan 2224k k k x x x xx x x k k k =====>>=>∑∑∑，即1x >，矛盾．故无解．（4）当1≥x 时，注意到111123tan(arctan arctan )112316++==-， 且由110arctan arctan arctan1arctan1232π<+<+=，知11arctan arctan 234+=π．则{}20202020202011111arctan arctan arctan1arctan arctan 1232k k x x k k π===≥>++=>∑∑，与{}202001x <<，矛盾．故此时无解．由（1）（2）（3）（4），知原方程的解集为{}0．22．（2021·全国·高三竞赛）两两不等的实数x 、y 、z 满足222(2)(2)(2)y x z y x z ⎧=-⎪=-⎨⎪=-⎩，求x y z ++.【答案】5或6. 【解析】 【分析】 【详解】由原方程变形可得到1(1)(3)1(1)(3)1(1)(3)y x x z y y x z z -=--⎧⎪-=--⎨⎪-=--⎩和4(4)4(4)4(4)y x x z y y x z z -=-⎧⎪-=-⎨⎪-=-⎩，又由x 、y 、z 两两不等知,,1,4x y z ≠， 于是()()()3331x y x xyz ---==.令,p x y z q xy yz zx =++=++，化简得39p q =+. 另一方面，原方程三式相加得2(2)412p p q p =--+， 化简得25122p p q -+=，联立就有26530p p p =-+，即5p =或6. 最后，当22224cos 744cos 784cos 7x y z ππ⎧=⎪⎪⎪=⎨⎪⎪=⎪⎩时可以取到5，当2224cos 924cos 944cos 9x y z πππ⎧=⎪⎪⎪=⎨⎪⎪=⎪⎩时可以取到6.23．（2021·全国·高三竞赛）若关于z 的整系数方程320z pz qz r +++=的三个复数根在复平面内恰好成为一个等腰直角三角形的三个顶点，求这个等腰直角三角形的面积的最小值. 【答案】1 【解析】 【分析】 【详解】设该等腰直角三角形斜边中点对应的复数为1z ，直角顶点对应的复数为()1220z z z +≠， 则另外两个顶点对应的复数分别为12z z i +和12z z i -，依题意有： 32121212()()()z pz qz r z z z z z z i z z z i +++=-----+，化简得223223111221112223,32,z x z p z z z z q z z z z z z r +=-++=+++=-，所以3222221223,489z z q p Z z z pq r Z =-+=-∈∈.进而122z z Q +∈，与123z z p Z +=-∈联立就有2z Q ∈.再由22223x q p Z =-∈知2z Z ∈，于是21z ≥，所以等腰直角三角形的面积最小为1.另一方面，3210z x z +++=的三个复数根恰是面积为1的等腰直角三角形的顶点. 24．（2021·全国·高三竞赛）证明：存在无穷多个奇数n ，使得!1n +是合数． 【答案】证明见解析 【解析】 【分析】 【详解】证明当奇数(3)n n ≥时，!1n +与(!)!1n n -+不均为质数即可： 用反证法，若!1n +为质数，设!1n p +=，则结合威尔逊定理可得： 111(!)!(1)!(1)!(1)(2)()(mod )n n p n p n p ----=--≡----1(1)!(1)1(mod )n n n p +≡--⋅≡--≡-，此时有(!)!1n n -+为合数，而n 奇数得!n n -也是奇数， 从而存在无穷多个奇数n ，使得!1n +是合数．25．（2019·山东·高三竞赛）已知4239n n -+是素数，求正整数n 的所有可能值 【答案】n =1，n =2 【解析】 【详解】因为()()4222393333n n n n n n -+=++-+，所以或n 2－3n +3=1，解得n =1，2.将n =1，n =2代入检验均满足题意，所以n =1，n =2为所求.26．（2021·全国·高三竞赛）求方程(31)(31)(31)34x y z xyz +++=的所有正整数解(,,)x y z ． 【答案】(,,)(28,5,2),(11,7,2)x y z =或其排序，共12组解． 【解析】 【详解】 不妨设x y z ≥≥．若z >31z +<．同理，31,31x y +<+<． 三式相乘得(31)(31)(31)34x y z xyz +++<，与原方程矛盾． 于是，5z ≤<． （1）若1z =，则4(31)(31)346()20x y xy xy x y ++=⇒+++=．显然，无正整数解．（2）若2z =，则7(31)(31)68521()70(521)(521)x y xy xy x y x y ++=⇒-+-=⇒--=24762717=⨯⨯．只有47611941434=⨯=⨯，才有对应的正整数,x y ，此时(,)(28,5)x y =或(11,7)． （3）若3z =，则10(31)(31)102615()50x y xy xy x y ++=⇒-+-=．两边取模3即知矛盾，故无解． （4）若4z =，则13(31)(31)1361939()130x y xy xy x y ++=⇒-+-=3(1939)(1939)176821317x y ⇒--==⨯⨯．故此时(1939)42y -≤，故39y ≤≤，逐一检验后无解. 综上，(,,)(28,5,2),(11,7,2)x y z =或其排序，共12组解．27．（2021·全国·高三竞赛）求方程||1r s p q -=的整数解，其中p ､q 是质数，r ､s 是大于1的正整数，并证明所得到的解是全部解. 【答案】证明见解析 【解析】 【详解】容易看到两个质数中肯定有一个为2，不妨假设2,21r sp q =-=，即21r s q -=±.若21r s q =+，从余数去讨论，3(mod4)q ≡，s 为奇数.()1221(1)1rss s q q qq--=+=+-++，所以121212,12,r r s s q q q --⎧+=⎨-++=⎩()1111111(1)(1)(2)2211222222sr sr s r r r s r s r r s s s s ---⎡⎤=-+=-++=-++⎣⎦，从奇偶性可以看出这种情形方程无解.若21r s q =-为偶数，注意到()1221(1)1r s s q q q q --=-=-+++，所以121212,12,r r s s q q q --⎧-=⎨+++=⎩()11111(1)21221122(1)22sr sr s r r r r s s s s --=+-=+++-+.令2u s v =，其中v 为奇数，则 ()11111(1)21221122(1)22sr sr s r r u r u r s v s v --++=+-=+++-+，观察最后一项，则v 为1，故2u s =，所以221ur q =-，故()()1122211u u r q q --=-+，故1112221212u u r r q q --⎧-=⎪⎨+=⎪⎩，所以12222r r +=，所以121,2r r ==，1u =， 所以3q =，3r =，2s =，综上，考察到对称性，原方程恰有两组解：3,2,2,3.p q r s =⎧⎪=⎪⎨=⎪⎪=⎩或2,3,3,2.p q r s =⎧⎪=⎪⎨=⎪⎪=⎩ 28．（2021·全国·高三竞赛）证明：对任意正整数N ，都存在正整数n N >和n 个互不相同的正整数12,,,n x x x ，使()222222121220202020n n x x x x x x -++++是完全平方数．【答案】证明见解析 【解析】 【详解】对于3m ≥，必存在不同的正整数12,,,m x x x 满足2221212m m x x x x x x S =++++，令{}112121max ,,,m m m x x x x x x x +=->，则有()21211212m m m m x x x x x x x x x x +=-()2121211m m x x x x x x =-+-()()2222121211m m x x x x x x S =-++++-22221211m m x x x x S +=++++-．以此类推，当504S >时，存在不同的正整数11504,,,,,m m m S x x x x ++-满足2221250412504504m S m S x x x x x x +-+-=++++．存在6N ≥，定义(1)k x k k N =≤≤，则()2221212504N N x x x x x x -+++>．由前述结论可得存在n N >使得()2221212504n n x x x x x x -+++=，此时()2222222222121212122020202020201010n n n n x x x x x x x x x x x x -++++=-+()2121010n x x x =-为完全平方数．29．（2021·浙江·高三竞赛）已知素数p ，q 满足21p q =+.证明：存在正整数m 使得mp 的十进制表示的各位数字之和是2或3. 【答案】证明见解析 【解析】 【分析】 【详解】2p =，3不合题意，若5p =则取110mp =即可.下面假设7p ≥.由费马小定理()()12101101101101p q q q p --=-=+-可知101q p +或101q p -.前者意味着取101q mp =+满足条件.若是101qp -，我们断言{}012110,10,10,,10q A -=⋅⋅⋅中的数模p 两两不同余，即有q 个不同的余数.这是因为若有()1010mod a b p ≡，（01a b q ≤<≤-）则()101mod b a p -≡，由b a -与q 互素以及裴蜀定理知存在正整数u ，v 使得()1u b a vq --=，这样 ()()()1110101010mod uvb a vq q p -+≡==⨯.这意味着1019p -=即3p =，不合题意因此{}012110,10,10,,10q A -=⋅⋅⋅中的数模p 两两不同余.设它们的余数是{}{}12,,,1,2,,1q B r r r p =⋅⋅⋅⊆⋅⋅⋅-. 我们考虑下面的52p -个余数对，它们覆盖了除了0，1，12p -，2p -，1p -之外的所有余数：()2,3p -，()3,4p -，…，31,22p p -+⎛⎫⎪⎝⎭ 若某个对子的两个余数都在B 中出现，不妨设10a k ≡，101b p k ≡--，则10101a b mp =++是p 的倍数，满足题意.若每个对子中的余数都在B 至多出现一个的话，由于12p B -=，所以0，1，12p -，2p -，1p -在B 中出现至少两个，已知1B ∈，0B ∉，其余三个余数12p -，2p -，1p -至少有一个在B 中出现. 若12p B -∈，即有某个1102a p -≡，则2101a mp =⨯+满足题意.若2p B -∈，即有某个102a p ≡-，则102a mp =+满足题意. 若1p B -∈，有某个101a p ≡-，则101a mp =+满足题意. 综上所述，存在p 的倍数的十进制数字和是2或3.30．（2021·全国·高三竞赛）设m 是一个给定的正整数，d 是它的一个正因子．已知{}0i i a ∞=和{}0i i b ∞=是两个由正整数构成的等差数列，满足：存在正整数i 、j 、k 、l ，使得()(),1,,ijkla b a b m ==．证明：存在正整数t 、s 使得(),t s a b d =．【答案】证明见解析 【解析】 【分析】 【详解】注意到m 可逐次除以它们若干素因子得到d ，这样只需证对m 的任意素因子p ，存在正整数α、β，使得(),ma b pαβ=． 由于(),k t a b m =，故k a p 、l b p 必有一项不能被m 整除．不妨设k ab不能被m 整除． 设等差数列{}i a 、{}j b 的公差分别为u 、v ，则0i a a iu =+，0j b b jv =+． 下面分两种情况：（1）若p v ．令,k a k l p αβ==+．这时k l a vb b pβ=+． 注意到k m ma b p pβ、，又p v 且k a m p ，所以m b β．这说明m p 是a α、b β的公因子，且m 不是它们的公因子．设q 是a α、b β的一个不同于p 的公因子，则q a α、q b β、a qpα． 故,a q a b v p ααβ⎛⎫- ⎪⎝⎭，即(),k t q a b m =．又p q ，故mq p ．故(),m a b p αβ=．（2）若p v ．先证p u ． (*)事实上，假设p u ，由(),k l a b m =知00,k l p a ku a p b lu b -=-=．因此,i j p a p b ，这与(),1ija b =矛盾！故（*）得证．取正整数s ，使得l s b p能被mp 整除，但不能被m 整除． 令,l sb k l p αβ=+=．这时,l kl s b a a u b b p αβ=+=． 注意到k m a p 、l m b p、lsb m p p ，所以m p 是a α与b β的公因子．又lsb m p ，且p u ，所以m a α，从而m 不是a α、b β的公因子．设质数q 是a α，b β不同于p 的公因子，则q b β，l k sbq a u a p α⎛⎫-= ⎪⎝⎭． 即(),k l q a b m =． 又q p ≠，所以mqp．这说明(),m a b p αβ=．由（1），（2）知结论成立．31．（2021·全国·高三竞赛）设多项式02()()(2)==+≥∑dii i P x a x a d 的系数为正整数．定义数列{}n b ：()101,(1)n n b a b P b n +==≥．证明：对于任意的整数2n ≥，均存在质数p ，使得n p b ，且()121,1n p bb b -=．【答案】证明见解析 【解析】 【分析】 【详解】假设存在整数2n ≥，使得n b 的任意一个质因子均为某个(11)i b i n ≤≤-的因子（对于n b 的不同的质因子，i 的取值可以不同）．令p 为n b 的一个质因子，且rn b p l =，其中,,(,)1r l p l +∈=N ． 则110012()()(mod )dr i r n n i i b P b a p l a a b p ++===+≡=∑假设()1mod ,r n i i b b p i +++≡∈N 成立，则()()()111mod r n i n i i i b P b P b b p +++++=≡=．所以由数学归纳法知对任意的正整数i ，均有()1mod r n i i b b p ++≡．进而有()12mod r n n kn b b b p +≡≡≡，所以1r kn n p b b +-．定义()p V m 表示正整数m 的标准分解中所含的p 的幂次数， 由()p n V b r =，得()p kn V b r =．令i p b 对某个(11)i i n ≤≤-成立，同上可证()()()23p i p i p i V b V b V b ===．于是()()()p n p in p i V b V b V b r ===．从而，若p 为n b 的一个质因子，则它在n b 的中的次数等于在某个(11)i b i n ≤≤-中的次数． 所以121n n b bb b -，进而121n n b b b b -≤．由()211n n n b P b b --=>，得21kn n k n b b b --<，所以111211n i n n i nn i i b bb ---==<<∏∏，矛盾，故原命题成立．32．（2021·全国·高三竞赛）一个大于1的整数m ，如果对所有的正整数n ，都存在正整数x 、y 、z ，使得222n mx y z =--，则称m 为上数，否则称为下数．试问：是否存在无数多的上数？是否存在无数多的下数？【答案】存在无数多个上数也存在无数多个下数． 【解析】 【分析】 【详解】存在无数多个上数也存在无数多个下数．首先，存在无数多个下数．考查93m k =+，其中k 为正整数．考查不定方程2226(93)k x y z =+--，若存在解x 、y 、z 则220(mod 3)y z ≡+， 故有()0mod3y z ≡≡，所以2222(93)36(mod 9)k x y z x +--≡≡，即2(mod3)x ≡，矛盾．故无解． 即所有的93k +为下数．其次，我们证明存在无数多个上数，我们考查21c +，其中222c a b =+（a 、b 、c 为勾股数）．（1）注意到22222(1)(1)21c x c x x x +---=-，可知所有的奇数1n >，均存在解． 又22211c a b =+--，可知所有奇数均存在解．（2）对于n 为偶数的情形，考查222222(1)(1)(2)4454(2)9c x cx x c x c c x c +---+-=-+-=---． 令c 为奇数，故有24(2)9x c ---可以为所有模4余2的数． （3）而对于4|n ，可以转为考查2224222n x y z m ⎛⎫⎛⎫⎛⎫=-- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭的问题，不断转化．终会归为（1）或是（2）其中的一类．而存在无数多个勾股数a 、b 、c （a 、b 、c 互质），即存在无数多个满足题意的21c +． 即有无数多个上数．33．（2021·全国·高三竞赛）如果正整数n 满足存在正整数a 、b 、c 使得()()()()()(),,,,,,n b c a bc c a b ca a b c ab =⋅+⋅+⋅，则称n 为好数．求证：存在连续2020个正整数这2020个正整数都是好数．注：对于正整数x ，y ，(),x y 表示x ，y 的最大公因数． 【答案】证明见解析 【解析】 【分析】 【详解】取121111121,(2),1,(2)(2,3,,2020)i i i l i i l x y x x x y y x x i -===+=-⋅⋅⋅=+=∏．对2,3,,2020i =，由()()1,1,21i i i i x x x x +=++=，知,2i i x x +均与121,,,i y y y -互质，故i y 与121,,,i y y y -均互质．则122020,,,y y y 两两互质．对1,2,3,,2020i =，考查i y 的一个倍数，设为()22i i i n my mx x ==+．注意到取2,,i i i a mx b mx c x ===，则有()()()()()(),,,,,,n b c a bc c a b ca a b c ab =⋅+⋅+⋅． 故n 为好数．则由n 的任意性，知i y 的一切倍数均为好数． 注意到122020,,,y y y 两两互质，那么由中国剩余定理知关于x 的同余方程组()()mod 1,2,,2020i x i y i ≡-=有正整数解0x ．这意味着对1,2,3,,2020i =，有0x i +是i y 的倍数，因此0x i +是好数． 取()01,2,,2020x i i +=即可满足题意．34．（2021·全国·高三竞赛）设函数:f N N ++→同时满足以下三个条件： （1）对任意x 、y N +∈，有()()()f xy f x f y =； （2）对任意x N +∈，有()()f f x x =； （3）()220()20f x x x ≠≤≤． 求()2f 的最小值． 【答案】1013． 【解析】 【分析】 【详解】在()()()f xy f x f y =中令1x y ==，得()11f =．①设质数p 满足()f p 不是质数，若()1f p =，则由（2）及①， 有()()()11p f f p f ===，矛盾．故()f p 为合数，设()f p xy =（x ﹐y 均为大于1的正整数）， 则()()()()()p f f p f xy f x f y ===．不妨设()1f x =，则()()()11x f f x f ===，与1x >矛盾． 因此，若p 是质数，则()f p 也是质数．由（1）、（2），有()()()()()()222222f f f f f f ==， 则由()22f 是偶数以及（3），得()222022f ≥． 因为()2f 是质数，所以()21013f ≥．另一方面，设小于2020的且不等于2或1013的质数有t 个，从小到大依次为12t p p p <<⋅⋅⋅<， 大于2020的质数中，最小的t 个从小到大依次为12t q q q <<⋅⋅⋅<考虑如下定义的函数:f N N ++→：()()()()()()11,21013,10132,,1,2,,i i i i f f f f p q f q p i t ======，且对质数t p q >，有()f p p =．对于合数1i ki i y r α==∏，其中质数12k r r r <<⋯<，且12k N ααα+⋯∈、、、，12k i i α=≥∑，有1()(())i ki i f y f r α==∏． 此时，不难验证f 满足（1）、（2）．且对于正整数()22020x x ≤≤，若x 为质数，显然()f x x ≠，若x 是合数，设1jlj j x s β==∏，其中质数12l s s s <<⋯<，且121,,,,2ll j j N ββββ+=∈≥∑．于是，由f 的定义知()f x 一定为至少两个，且每个均不小于1013的正整数的乘积， 故()2020f x x ≥≥，则f 满足（3）． 综上，知()2f 的最小值为1013．35．（2021·全国·高三竞赛）对每个正整数n ，定义()f n 为从1到n 中所有与n 不互质的正整数的和.求证：若()()f m f n =且m n ≠，则m n -是合数. 【答案】证明见解析 【解析】 【分析】 【详解】首先计算()f n 的表达式，注意到从1到n 中所有与n 互质的正整数有()n ϕ个，并且它们是以t 和n t -的形式成对出现的，因此111()(1)()(1())222f n n n n n n n n ϕϕ=+-⋅=+-.若()()f m f n =且m n ≠，不妨设m n >，则()()()()11m m m n n n ϕϕ+-=+-.① 因为()11n n n m ϕ≤+-≤<，所以(),1m n >.若m n -不为合数，设为质数p ，则()1n kpm p k ==+﹐， ①式变为()()()()()()11111k k p k p k kp kp ϕϕ+++-+=+⎦-⎡⎤⎣.由(),11k k +=，可设()()()()()111,11k p k p lk kp kp l k ϕϕ++-+=+-=+ 其中0l p <<，相减得()()()1k p kp p l ϕϕ+-=+，1k =时， ()()21p p p l ϕ--<+不合题意，所以2k ≥，2p =时，()()()1,1l k p kp p l ϕϕ=+-=+左右奇偶性不同，所以3p ≥.注意()()()()()1,11p kp p k p ϕϕ--+，因此()()1|p p l -+.又0,3l p p <<≥，所以2l p =-，所以()()()121,23k p k p kp k p ϕϕ+=++=-+. 若|p k ，则()|p kp ϕ，所以()3|2p k p -+，所以3p =， 所以()()()12121k p k k p ϕϕ+=+<++，矛盾，同理若()1|p k +也得矛盾，所以()()1121p k k p ϕ-+=++，()()123p k k p ϕ-=-+，②所以()()12k k ϕϕ+-=，于是()1k ϕ+和()k ϕ恰有一个不是4的倍数，必模4余2，但()s ϕ模4余2当且仅当4,,2a a s q q =，这里q 是模4余3的奇质数，a 是正整数，分别代回②知都无解.综上，若()()f m f n =且m n ≠，则m n -是合数.36．（2021·全国·高三竞赛）已知正整数,1n n >，设A 为正整数满足2|1n n A ⎡⎤+⎢⎥⎣⎦，求所有A 的值．（[]x 表示不超过x 的最大整数）【答案】当2n =时，3A =，或4，当2n >时，1A n =+． 【解析】 【分析】 【详解】（1）如果2A n >，则211n A ⎡⎤+=⎢⎥⎣⎦，由1n >知，2 1n n A ⎡⎤+⎢⎥⎣⎦；（2）如果2A n =，则212n A ⎡⎤+=⎢⎥⎣⎦，由21n n A ⎡⎤+⎢⎥⎣⎦∣及1n >知2n =，从而4A =；（3）如果20A n <<，则令22n n A r A ⎡⎤=+⎢⎥⎣⎦，其中20r A n ≤<<，即221()n n A A r A ⎛⎫⎡⎤=+-- ⎪⎢⎥⎣⎦⎝⎭． ①当2n A n <<时，222,11n n n n n A A A ⎡⎤⎡⎤<<+<+⎢⎥⎢⎥⎣⎦⎣⎦，由21n n A ⎡⎤+⎢⎥⎣⎦∣，可设21n nH A ⎡⎤+=⎢⎥⎣⎦， 于是1nH n <+，即()11n H -<，这样，只有1H =成立，所以21n n A ⎡⎤+=⎢⎥⎣⎦．代入①式得()2n nA A r =--，即21111n r r A n n n --==+---． 若1r ≠，则11r n --是不小于1的正整数，于是A n ≤，与A n >矛盾， 因此1r =，故1A n =+．当A n =时，211n n A ⎡⎤+=+⎢⎥⎣⎦，由n ∈+N 知211n n n A ⎡⎤+=+⎢⎥⎣⎦；当0A n <<时，由①式及21n n A ⎡⎤+⎢⎥⎣⎦∣知，n A r -∣． 又0,0A n r A n <<≤<<，从而0A r n <-<，矛盾． 综上，当2n =时，3A =，或4，当2n >时，1A n =+．37．（2021·全国·高三竞赛）证明：对任何正整数m ，存在无穷多组整数(),x y ，使得 （1）,x y 互质； （2）2|x y m +； （3）2|y x m +． 【答案】证明见解析. 【解析】 【分析】 【详解】显然，当1x y ==时，符合题意．若正整数对()(),x y x y ≤满足条件，由条件（2）可设2xx y m '=+，其中x Z +'∈．下证命题：正整数对(),y x '也满足条件，且y x <'． 由等式2xx y m '=+知，2xx y yx '>≥，即x y '>． 同时还可知，2|x y m '+且()cd ,|g x y m '．若p 是()gcd ,x y '的一个质因子，则有,p m p y ．结合条件（3）有2|p x m +，从而有|p x ． 这与条件（1）矛盾．故()gcd ,1x y '=．最后，还需证2yx m '+∣．由于gcd(,)1x y =，等价证()22y x x m '+∣． 其中()()()2222220(mod )x x m y m x m m m x y '+=++≡+≡．命题得证，且x y x '>≥．反复利用此命题，便可得到无穷数列{}n a ，其中()212211,n n n a m a a a n a ++++===∈N ． 满足1n n a a +>对2n ≥成立，且整数对()()1,n n a a n ++∈N 符合条件．38．（2021·全国·高三竞赛）正整数2n ≥，且n 的素因子个数不超过2，对于任意整数a ，若(),1n a =，则有()mod n a a n ≡成立，求证：n 是质数.【答案】证明见解析. 【解析】 【分析】 【详解】假设n p q αβ=，（其中p q 、均为质数，N αβ∈﹐）. 首先证明：p q ≠，若n p γ=（p 为质数，γαβ=+）.因为(),1n a =，所以取最小整数δ，使得()1mod a p δγ≡（易知δ为a 对模2p 的阶）.又()111(mod )1mod n n an a p γ--≡⇔≡，所以()()1(1),(1)1p p p n p γγγδϕδδ-=--⇔-∣，所以1p δ-∣. 取()()()11111111(1)11mod p p a p p a p p p p p γγγγγγ------=--⇒≡-≡--+≡+，矛盾.所以n p p q γ≠⇒≠.任取与p q 、互质的a ， 由Euler 定理知：()()1(mod ),()(1)(1)n an n p q p q ϕαβϕϕ≡==--.从而()()1|1p q δ--，又因为()|(1)|1n p q αβδδ-⇒-，所以()11111p q p q p q αβαβαβδ----+--∣.所以111111(mod )p qp q p q a n αβαβαβ----+--≡，所以()111mod p q a p αβα--≡，所以()111mod q p q a p αα--≡.同理()111mod p q aq αββ--≡.不妨设p q >，则p 一定是奇质数.因此它存在原根g ，满足()11mod q gp α-≡/.因此，一定存在整数k ，使得q kp g α+，取a kp g α=+，矛盾! 结合2n ≥，知n 只能有一个质因子，即n 是质数. 又由Fermat 小定理知，当n 为质数时，满足题意.39．（2021·全国·高三竞赛）设a ，b 为正奇数，定义数列{}n f 如下：1f a =，2f b =，当3n ≥时，n f 为12n n f f --+的最大奇因子.求证：当n 充分大时，n f 为常数，并确定出这个常数. 【答案】a ，b 的最大公约数. 【解析】 【详解】从题目条件可以知道，如果有相邻两项k f ，1k f +相等，则当n k ≥时，n f 全相等，为常数. 用反证法，如果n f 不为常数，则序列{|}n f n N ∈的任意相邻两项不等.由于1n f -，2n f -皆为奇数，则12n n f f --+为偶数.那么，有(){}12121max ,2n n n n n f f f f f ----≤+<，于是，有 {}{}{}3456max ,max ,max ,...a b f f f f >>>.显然，这无限递降正奇数数列不存在，矛盾.所以，必存在正整数k ，使得1k k f f +=，即当n k ≥时，n k f f =.设此常数为C ，由于122an n n f f f --+=，这里a 是个正整数，以及n f ，1n f -，2n f -均为奇数，可知1n f -，2n f -的最大公约数()12,n n f f --等于n f ，1n f -的最大公约数()1,n n f f -.从而，序列中任意相邻两项的最大公约数相同.那么，()(),...,C C C a b ===，即这常数为a ，b 的最大公约数.40．（2020·全国·高三竞赛）设12121,2,2,3,4,n n n a a a a a n --===+=证明：对整数5n ≥，n a ，必有一个模4余1的素因子． 【答案】证明见解析. 【解析】 【分析】不妨记11αβ==由递推式及数学归纳法得到n a 有奇素因子p ，然后对正整数进行讨论，证明也存在模4余1的素因子. 【详解】证明：记11αβ=+=-n n n a αβαβ-=-．记2n nn b αβ+=，则数列{}n b 满足122(3)n n n b b b n --=+≥ ①因121,3b b ==均为整数，故由①及数学归纳法，可知{}n b 每项均为整数．由222()22n n n n n αβαβαβαβαβ⎛⎫⎛⎫+--⎛⎫-= ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭， 可知222(1)(1)nn n b a n -=-≥ ②当1n >为奇数时，由于1a 为奇数，故由{}n a 的递推式及数学归纳法，可知n a 为大于1的奇数，所以n a 有奇素因子p ．由②得21(mod )n b p ≡-，故112(1)(mod )p p n b p --≡-．又上式表明(),1n p b =，故由费马小定理得11(mod )p n b p -≡，从而12(1)1(mod )p p --≡．因2p >，故必须12(1)1p --=，因此1(mod 4)p ≡．另一方面，对正整数m ，n ，若|m n ，设n km =，则()(1)(2)(2)(1)n n m mk m k m m m k m k m n a αβαβααβαββαβαβ------==⋅++++--()0(212)(212)1(22)(22)1()(),2=(()(),21i im l i m l i m m l i lm im l i m l i m m l a k l a k l αβαβαβαβαβ=-----=---⎧⋅∑+=⎪⎨⎪⋅∑++=+⎩因2s ss b αβ+=为整数（对正整数s ），1αβ=-为整数，故由上式知n a 等于m a 与一个整数的乘积，从而|m n a a ．因此，若n 有大于1的奇因子m ，则由前面已证得的结论知m a 有素因子1(mod 4)p ≡，而|m n a a ，故|n p a ，即n a 也有模4余1的素因子．最后，若n 没有大于1的奇因子，则n 是2的方幂．设2(3)l n l =≥， 因84082417a ==⨯有模4余1的素因子17，对于4l ≥，由8|2l 知82|l a a ， 从而2l a 也有素因子17．证毕． 【点睛】关键点点睛：本题证明的关键是能够运用数论整除的相关知识以及费马小定理进行证明，不漏掉情况.41．（2019·江苏·高三竞赛）设k 、l 、c 均为正整数，证明：存在正整数a 、b 满足(,)b ac a b -=⋅，且()(),(,)a b l kb a a b a b ττττ⋅=⋅⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭，其中(a ，b )表示a 、b 的最大公因数，()m τ表示正整数m 的所有不同正因子的个数. 【答案】见解析 【解析】 【详解】如果m 的标准分解式为1212n n n m p p p ααα=，那么()()()12()111n m τααα=+++.取定两个不同的素数p 、q 使得(pq ，c )=1.由于(p ，q )=1，利用裴蜀定理，存在正整数00,u v ，使得00k lp u q v c -=.由于(pq ，c )=1，那么0p v 且0q u . 由中国剩余定理，下列同余方程组：0001(mod )1(mod )1(mod )l kl u tq p v tp q u tq c ⎧+≡⎪+≡⎨⎪+≡⎩有正整数解t t =0. 令0000,l ku u t q v v t p =+=+，那么k l p u q v c -=，而且(u ，pqc )=1.因此(,)1,(,)1v pqc u v ==.现在取2211,k l l d p q n q v --==，则l k n c q v c p u +=+=. 从而(,)1n n c +=.令a =nd ，b =(n +c )d ，那么(a ，b )=d ，因此(,)b a cd c a b -==⋅.而且：()()2211()()(),k ll l p q va nd l l la n q v ab ττττττ-+-⋅=⋅=⋅⎛⎫⎪⎝⎭()22221k l l l k l l +==+.()()2211()(())(),kk l kp qub ncd k k k b n c p u a b ττττττ+--+⋅=⋅=⋅+⎛⎫⎪⎝⎭()22221kk l k k l k +==+.所以()()(,)(,)a b l ka b a b a b ττττ⋅=⋅⎛⎫⎛⎫ ⎪ ⎪⎝⎭⎝⎭.42．（2019·江西·高三竞赛）试求所有由互异正奇数构成的三元集{a ，b ，c }，使其满足：2222019a b c ++=.【答案】7个，{1,13,43},{7,11,43},{13,25,35},{5,25,37}，{}11,23,37，{17,19,37},{7,17,41}. 【解析】 【详解】据对称性，不妨设a <b <c ，由于奇平方数的末位数字只具有1、5、9形式，于是222,,a b c 的末位数字，要么是5、5、9的形式，要么是1、9、9的形式.又知，如果正整数n 是3的倍数，那么n 2必是9的倍数；如果n 不是3的倍数，那么n 2被3除余1.由于2019是3的倍数，但不是9的倍数，因此奇数a 、b 、c 皆不是3的倍数. 注意[2019]44c =，即奇数c ≤43，而222232019c a b c >++=， 即c 2>673，且c 不是3的倍数，故奇数c ≥29. 因此奇数{29,31,35,37,41,43}c ∈.。

高中数学竞赛数论剩余类与剩余系1.剩余类的定义与性质(1)定义1设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为：K0,K1,…,K m-1,其中K r={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类(也2.a r，得m 个数小完为偶数时,-(ⅱ)若(a,m)=1，则x与ax+b同时遍历模m的完全剩余系.证明:即证a0,a1,…,a m-1与aa0+b,aa1+b,…,aa m-1+b同为模m的完全剩余系,因a0,a1,…,a m-1为模m的完系时,若aa i+b≡aa j+b(modm),则a i≡a j(modm),矛盾!反之,当aa0+b,aa1+b,…,aa m-1+b为模m的完系时,若a i≡a j(modm),则有aa i+b≡aa j+b(modm),也矛盾!历遍模m 1m 2的完系.证明:因x,y 分别历遍m 1,m 2个整数,所以,m 2x+m 1y 历遍m 1m 2个整数.假定m 2x /+m 1y /≡m 2x //+m 1y //(modm 1m 2),其中x /,x //是x 经历的完系中的数,而y /,y //是y 经历的完系中的数.因(m 1,m 2)=1,所以,m 2x /≡m 2x //(modm 1),m 1y /≡m 1y // //////3.(1).在与模m 的一个既约)m (ϕx 1≡x (ⅳ)若a 1,a 2,…,a φ(m)是)m (ϕ个与m 互质的整数,并且两两对模m 不同余,则a 1,a 2,…,a φ(m)是模m 的一个既约剩余系.证明:因a 1,a 2,…,a φ(m)是)m (ϕ个与m 互质的整数,并且两两对模m 不同余, 所以,a 1,a 2,…,a φ(m)属于)m (ϕ个剩余类,且每个剩余类都与m 互质,故a 1,a 2,…,a φ(m) 是模m 的一个既约剩余系.则m 2x+m 1y 历遍模m 1m 2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1, (m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2=1,余系(2m ϕ.,α, 4.欧拉(Euler)定理设m 是大于1的整数,(a ,m)=1,则)(m od 1)(m am ≡ϕ.证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以,a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r aϕϕ)(21m r r r ϕ ,因()(21m r r r ϕ ,m)=1,所以,)(m od 1)(m a m ≡ϕ.推论(Fermat 定理)设p 为素数,则对任意整数a 都有)(m od p a a p≡.证明:若(a ,p )=1,由1)(-=p p ϕ及Euler 定理得)(m od 11p ap ≡-即)(m od p a a p ≡;若(a ,p )≠1,则p |a ,显然有)(m od p a a p ≡.例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .m 整除,求.m,使得所以,是整数序列 假设对每个正整数:在数列123,,,a a a 中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣<k:若∣a k ∣≥k,则取n=∣a k ∣, 则a 1≡a k ≡0(modn),矛盾.现在对k 归纳证明a 1,a 2,…,a k 适当重排后是绝对值小于k 的k 个相邻整数.k=1显然.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i(0≤i ≤k -1),由于a 1,a 2,…,a k ,a k+1是(modk+1)的一个完全剩余系,故必a k+1≡i+1(modk+1),但 ∣a k+1∣<k+1,因此a k+1只能是i+1或-(k -i),从而a 1,a 2,…,a k ,a k+1适当重排后是绝对值小于k+1的k+1个相邻整数.????中,则????就得到:, 也历mod2n 可被证明:因(40,2011)=1,所以,)2011(m od 140)2011(≡ϕ.因当)2011(ϕ>n 时,!|)2011(n ϕ,所以,数列{a n (mod2011)}构成模2011的完系,且是周期数列,所以,数列{a n }中存在无穷多项可被2011整除.例7证明:存在无穷多个正整数n,使得n 2+1?n!.证明:引理1对素数p >2,⇔≡)4(mod 1p 存在x(1≤x ≤p -1)使)(m od 12p x -≡.证:充分性:因对1≤x ≤p -1,(p ,x)=1,所以,)(mod 1)(2121p x xp p ≡=--,≡-212)(p x)(mod 1)1(21p p ≡--,所以,21-p 为偶数,即).4(mod 1≡p 必要性:因1≤x ≤p -1时,x,2x,…,(p -1)x 构成modp 的既约剩余系,所以,存在 1≤a ≤p -1,使得a x ≡-1(mod p ),若不存在a (1≤a ≤p -1),a =x,使a x ≡-1(mod p ),1-p )(mod 1)!1()1(21p -1-p ,与a =4(使 2p 1p 22x ≡,所以,例8(2)若T 为无理数,则存在各项均为无理数的数列{a n }满足0<a n+1<a n <1 (n=1,2,…),且每个a n 都是f(x)的周期.证明：(1)设T=nm(正整数m,n 互质,且n ≥2),因(m,n)=1,所以,m,2m,…,nm 构成modn 的完系,故存在k ∈N *使得km ≡1(modn),即存在t ∈N *使得km=nt+1,因f(x)=f(x+kT)=f(x+n km )=f(x+t+n 1)=f(x+n 1),所以n1是周期.设n=kp ,其中k ∈N *,p 为素数,则n k p 11⋅=是周期.故存在素数p,使p1是周期. (2)当T 为无理数时,取a 1=T,则T 为无理数,0<T<1.设k≤n 时存在无理数a k ,使得0<a k <a k-1<1,且a k 是周期.对k+1,总存在存在u,v ∈N *,使得0<u a k -v<a k <1,,对任意k }包含了的所1≤k ≤. . 例11求所有的奇质数p ,使得∑=-201111|k p k p .例12求所有质数p ,使得2122213)()()(|-+++p p p p C C C p .例13设n 为大于1的奇数,k 1,k 2,…,k n 是n 个给定的整数,对1,2,…,n 的每一个排列a=(a 1,a 2,…,a n ),记S(a)=∑=ni i i a k 1.证明:存在两个1,2,…,n 的排列b 和c(b ≠c),使得n!|S(b)-S(c).证明:如果对1,2,…,n 的任意两个不同排列b 和c(b ≠c),都有n!?S(b)-S(c),那么当a 取遍所有排列时(共n!个),S(a)遍历模n!的一个完系, 因此,有∑aa S )(≡1+2+…+n!≡2!2)1!(!n n n ≡+(modn!)①,另一方面,我们有 ∑aa S )(=)!(mod 02)1(!])!1[(11111n k n n j n k a k a k ni i ni nj ini a ii a n i ii ≡+=-==∑∑∑∑∑∑∑=====②. 由①.modm 因n 位数字是x 在A 1.定义1给定正整数m 及n 次整系数多项式0111)(a x a x a x a x f n n n n ++++=-- ，则同余式f(x)≡0(modm)①叫做模m 的同余方程,若a n 0(modm),则n 叫做方程①的次数.若x=a 是使f(a )≡0(modm)成立的一个整数,则x ≡a (modm)叫做方程①的一个解,即把剩余类a (modm)叫做①的一个解.若a1(modm),a2(modm)均为方程①的解,且a1,a2对模m不同余,就称它们是方程①的不同解.由此可见,只需在模m的任一组完系中解方程①即可.例1解方程2x2+x-1≡0(mod7).解:取mod7的完系:-3,-2,-1,0,1,2,3,直接验算知x≡-3(modm)是解.例2求方程4x2+27x-12≡0(mod15).是解.2.x使得a0是一个特解x因(12,9)=3,且-1是一个特解,所以,方程12x≡6(mod9)的解为:(modt5,2,1，x即)8≡x.≡t-),82,1,0-(mod3+1=3.同余方程组定义3给定正整数m1,m2,…,m k和整系数多项式f1(x),f2(x),…,f k(x),则同余式组⎪⎪⎩⎪⎪⎨⎧≡≡≡)(mod 0)()(mod 0)()(mod 0)(2211k k m x f m x f m x f ②,叫做同余方程组.若x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,则x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.其中m =[m 1,m 2,…,m k ].例5解方程组⎧≡)7(mod 3x .⎩⎨⎧≡≡x x ). M=m 1m ⎪⎪⎩⎪⎪⎨⎧≡≡≡x x x 其中则x 注:(1)存在无穷多个整数x 满足同余方程组③,这些x 属于同一模m 的剩余类; (2)同余方程组③仅有一个解x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM). (3)当(a ,m i )=1(=1,2,…,n)时,同余方程组⎪⎪⎩⎪⎪⎨⎧≡≡≡⇔⎪⎪⎩⎪⎪⎨⎧≡≡≡---)(mod )(mod )(mod )(mod )(mod )(mod 12211112211k k k k m a a x m a a x m a a x m a ax m a ax m a ax 仍然具有定理结论.这在数论解题中具有重要应用.例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何”.解:设物数x,则有⎪⎩⎪⎨⎧≡≡≡)7(mod 2)5(mod 3)3(mod 2x x x ,这里m 1=3,m 2=5,m 3=7,M=3×5×7=105,所以,-1-1-1x 求兵数.:≡x 即x=2310k+2111(k ∈N).例8证明:对任意n 个两两互质的正整数:m 1,m 2,…,m n ,总存在n 个连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).证明:由剩余定理知,总存在整数k 使得⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡)(mod )(mod 2)(mod 121n m n k m k m k ,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).例9证明:对任意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当然也不是素数).证明:因都不是素数的幂时,只能是素数之积.对任意n ∈N *,取两组不同的素 数p 1,p 2,…,p n 与q 1,q 2,…,q n ,则由剩余定理知存在m ∈N *,使得⎪⎪⎩⎪⎪⎨⎧≡≡≡m m m ,且A {k +a n ⎩⎨⎧-≡≡0x x 2的最小⎩+1n a n 的最小正整数,由剩余定理知满足条件的a n+1存在.则上述递推关系定义的数列{a n }满足题意:因对任意k ∈N *,当n ≥k+1时,都有k+a n ≡0(mod p k+1),由{a n }递增可知{k +a n }从第k+2项起每一项都是p k+1的倍数,且都大于p k+1,所以, 数列{k +a n }中至多有k+1项为素数.例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对任意正整数k ，该数列的前k 项之和是k 的倍数？解:取a 1=1,假设a 1,a 2,…,a m 都已确定,令t 为不在a 1,a 2,…,a m 中出现的最小正整数,S=a 1+a 2+…+a m .由剩余定理知存在无穷多个r ∈N *,使得⎩⎨⎧+≡+++≡+)2(mod 0)1(mod 0m t r S m r S 成立.(如a 1=1,取t=2,适合⎩⎨⎧≡++≡+)3(mod 0)2(mod 011t r a r a 且r>1,2得r=3). 取这样的r,使得r>t 且r>},,,max {21m a a a ,令a m+1=r,a m+2=t,则这样得到的数列{a n }的质因数.例例。

2-4 数学竞赛中的数论问题（09-10-28）数论是研究自然数的一个数学分支. 一、数学竞赛中数论问题的基本内容 主要有8个定义、15条定理.定义 1 （带余除法）给定整数,,0,a b b ≠如果有整数(),0q r r b ≤<满足a qb r =+，则q 和r 分别称为a 除以b 的商和余数．特别的，0r =时，则称a 被b 整除，记作b a ，或者说a 是b 的倍数，而b 是a 的约数．定义2 （最小公倍数）非零整数12,,,n a a a L 的最小公倍数是能被其中每一个()1i a i n ≤≤所整除的最小正整数，记作[]12,,,n a a a L ．定义3 （最大公约数）设整数12,,,n a a a L中至少有一个不等于零，这n 个数的最大公约数是能整除其中每一个整数的最大正整数，记作()12,,,n a a a L ． 定理1 对任意的正整数，有 ()[],,a b a b ab ⋅=．定义4 如果整数,a b 满足(),1a b =，则称a 与b 是互素的（以前也称为互质）．定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（以前也称为质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数． 定理2 素数有无穷多个，2是唯一的偶素数． 定义6 对于整数,,a b c ，且0c ≠，若()c a b -，则称,a b 关于模c 同余，记作(mod )a b c ≡若则称,a b 关于模c 不同余，记作a(mod )b c ．定理3 （整除的性质）设整数,,a b c 为非零整数， （1） 若c b ，b a ，则c a ； （2） 若c a ，则bc ab ；（3） 若c a ，c b ，则对任意整数,m n ，有c ma nb +； （4） 若(),1a b =，且a bc ，则a c ； （5） 若(),1a b =，且,a c b c ，则ab c （6） 若a 为素数，且a bc ，则a b 或a c ．定理4 （同余的性质）设,,,,a b c d m 为整数，0,m > （1） 若(mod )a b m ≡且(mod )b c m ≡，则(mod )a c m ≡； （2） 若(mod )a b m ≡且(mod )c d m ≡，则(mod )a cb d m +≡+且(mod )ac bd m ≡．（3） 若(mod )a b m ≡，则对任意的正整数n 有(mod )n n a b m =，且(mod )an bn mn ≡； （4） 若(mod )a b m ≡，且对非零整数k有(,,)k a b m ，则mod a b m k k k ⎛⎫= ⎪⎝⎭． 定理5 设,a b 为整数，n 为正整数，（1） 若a b ≠，则()()n n a b a b --； （2） 若a b ≠-，则()()2121n n a b a b --++； （3） 若a b ≠-，则()()22n n a b a b +-．定义7 设n 为正整数，k 为大于2的正整数, 12,,,ma a a L 是小于k 的非负整数，且10a >．若 12121m m m m n a k a k a k a ---=++++L，则称数12m a a a L 为n 的k 进制表示．定理6 给定整数2k ≥，对任意的正整数n ，都有唯一的k 进制表示．定理7 任意一个正整数n 与它的十进制表示中的所有数字之和关于模9同余．定理8 （分解唯一性）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的 1212k a a ak n p p p =L .定理9 若正整数n 的素数分解式为 1212,k a a a k n p p p =L 则n 的约数的个数为()()()()12111k d n a a a =+++L ，n 的一切约数之和等于121212111111k a a a k k p p p p p p ---⋅⋅⋅---L ． 定义8 对任意实数x ，[]x 是不超过x 的最大整数．亦称[]x 为x 的整数部分，[][]1x x x ≤<+．定理10 在正整数!n 的素因子分解式中，素数p 作为因子出现的次数是23n n n p p p ⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦L定理11 如果素数p 不能整除整数a ，则()11p p a --． 定理12 设p 为素数，对任意的整数a ，有()mod p a a p ≡． 定理13 设正整数1212.k a a ak n p p p =L ，则不大于n 且与n 互素的正整数个数()n ϕ为 ()12111111k n n a a a ϕ⎛⎫⎛⎫⎛⎫+--- ⎪ ⎪⎪⎝⎭⎝⎭⎝⎭L ． 定理14 整系数二元一次方程ax by c +=存在整数解的充分必要条件是(),c a b ．定理15 若()00,x y 是整系数二元一次方程ax by c +=的一个整数解，则方程的一切整数解可以表示为00,.x x bt y y at =-⎧⎨=+⎩()t Z ∈ 二. 数学竞赛中数论问题的重点类型 主要出现8类问题.：1.奇数与偶数（奇偶分析法、01法）；2.约数与倍数、素数与合数；3.平方数；4.整除；5.同余；6.不定方程；7.数论函数、[]x 高斯函数、()n φ欧拉函数； 8.进位制（十进制、二进制）.三. 例题选讲例1 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，…，99，100.每盏灯由一个拉线开关控制着.最初，电灯全是关着的.另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的讲解（1）直接计算100次记录，会眼花缭乱.（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次.（3）灯被拉的次数与亮不亮（开、关）有什么关系：灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数.（5）1～100中有哪些平方数：共10个：1，4，9，16，25，36，49，64，81，100.答案：编号为1，4，9，16，25，36，49，64，81，100共10个还亮.例2 用[]x 表示不大于x 的最大整数，求122004366366366366⎡⎤⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦L . 讲解 题目的内层有2004个高斯记号，外层1个高斯记号.关键是弄清[]x 的含义，进而弄清加法谁与谁加、除法谁与谁除：（1）分子是那些数相加，求出和来；由366518302004219663666⨯=<<=⨯，知分子是0～5的整数相加，弄清加数各有几个（2）除法谁除以366，求出商的整数部分.原式()036536612345175366⨯+++++⨯⎡⎤=⎢⎥⎣⎦1036687536614310236612.⨯+⎡⎤=⎢⎥⎣⎦⎡⎤=++⎢⎥⎣⎦= 命题背景2004年有12个月、366天.例3 ()111959,IMO -证明对任意正整数n ，分数214143n n ++不可约.证明1 （反证法）假若214143n n ++可约，则存在1d >， ①使 ()214,143n n d ++= 从而存在(),,,1p q p q =，使214, 143, n dp n dq +=⎧⎨+=⎩②③消去n ，()()3322⨯-⨯，得()132d q p =- ④ 的 1d = ⑤由（1）、（5）矛盾，得1d =. 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法 （2）式④是实质性的进展，表明()()131432214n n =+-+ 可见 ()214,1431n n ++=. 由此获得2个解法.证明2 设()214,143n n d ++=。

高中数学联赛数论专题数论是数学中的一个重要分支，涉及整数的性质和关系。

在高中数学联赛中，数论作为一个专题常常被提及，并且在竞赛题目中占据一定比例。

本文将从数论的基本概念、典型问题和解题思路等方面进行探讨。

一、数论的基本概念数论是研究整数的性质和关系的数学领域，其中核心概念包括因数、倍数、质数、互质等。

因数指的是能够整除某个整数的所有正整数，而倍数则是某个整数所能够整除的所有整数。

质数是只能被1和自身整除的整数，而互质则是两个数的最大公因数为1。

二、典型问题在高中数学联赛的数论专题中，常常会出现以下典型问题：1. 质因数分解：给定一个整数，要求将其分解为质因数的乘积。

质因数分解不仅是数论中的重要知识点，还是其他数学学科的基础。

2. 同余定理：同余定理是数论中的重要理论，涉及到整数之间的模运算。

常见的同余定理包括欧拉定理、费马小定理等。

3. 素数判定：判断一个数是否为素数是数论中的常见问题。

除了常规的试除法，还可以运用费马检验、米勒-拉宾素性测试等方法进行判定。

4. 数列问题：数论与数列密切相关，常常会涉及到数列的性质和规律。

例如斐波那契数列、约瑟夫环等经典问题。

5. 不定方程：不定方程指的是关于整数解的方程，解决不定方程需要灵活运用数论知识和技巧。

典型的不定方程问题包括费马方程、佩尔方程等。

三、解题思路在高中数学联赛中，解决数论问题的关键在于运用合适的方法和技巧。

下面给出几点解题思路供参考：1. 寻找规律：数论问题常常有一定的规律性，通过观察和归纳找出规律是解题的关键。

可以通过列数表、找数列规律等方法进行推断。

2. 利用等式性质：利用等式的性质可以化简或者变形给定的数论问题，将其转化为更容易解决的形式。

例如利用同余关系化简方程、利用性质求解方程等。

3. 利用定理和公式：数论中有很多重要的定理和公式，熟练掌握并恰当运用可以大大提高解题效率。

例如欧拉定理、费马小定理等。

4. 分类讨论：针对不同情况进行分类讨论，找出不同情况下的共同性质和规律。

高中数学竞赛数论数论作为数学的一个分支，是数学竞赛中重要的考查内容之一。

高中数学竞赛数论题目常常涵盖了整数性质、模运算、质数等各个方面的知识。

在数论的学习和应用中，往往需要我们灵活运用各种技巧和方法来解决问题。

本文将从基本概念、常见性质、解题技巧等方面来介绍高中数学竞赛数论的相关内容。

一、基本概念1. 整数的性质：整数的奇偶性、整数的除尽性等都是数论中基本的概念。

在解题过程中，我们常常需要利用整数的性质来简化问题。

2. 算术基本定理：任何一个大于1的正整数，都可以表示为若干个质数的乘积，且这种表示方法是唯一的。

这一定理在数论中有着非常重要的作用，解决了很多关于因数分解的问题。

3. 同余方程：在数论中，我们常常会接触到模运算和同余方程。

同余方程是指在整数集合Z上定义的一种关系，通常用符号“≡”来表示。

在解决问题时，求解同余方程是一个常见的手段。

二、常见性质1. 质数性质：质数是指只有1和它本身两个正因数的自然数。

在解题中，我们需要掌握质数的性质，如质数的判定方法、质数之间的性质等。

2. 欧拉定理：欧拉定理是数论中的一个重要定理，它描述了正整数幂的同余性质。

欧拉定理在数论中的应用非常广泛，是解决一类数论问题的重要工具。

3. 数列与递推关系：在数论竞赛中，常常会涉及到数列和递推关系。

我们需要熟练掌握数列的性质和常见的数列递推方法，以便解题时能够迅速找到规律。

三、解题技巧1. 数学归纳法：数学归纳法是数论中常用的证明方法，通过数学归纳法可以证明某个结论对于所有正整数都成立。

在数论竞赛中，经常可以用到数学归纳法来解决问题。

2. 等价转化：有时候，我们需要将原来的问题进行等价转化，从而简化解题过程。

通过巧妙的等价转化，我们可以找到更容易解决的问题。

3. 假设反证法：假设反证法是一种解题思路，通过假设问题的否定，再通过逻辑推导得出矛盾，从而证明原命题成立。

在数论中，假设反证法常常被用来解决一些猜想和证明问题。