近五年全国高中数学联赛选编数论
近五年全国高中数学联赛选编——数论 2015.8.16
1.(2010年 加试 2) 设k 是给定的正整数，12
r k =+．记(1)()()f r f r r r ==????，()
()l f r = (1)(()),2l f f r l -≥．证明：存在正整数m ，使得()()m f r 为一个整数．这里，x ????表示不小于实数x 的最小
整数，例如：112
??=????
，11=????．
证明：记2()v n 表示正整数n 所含的2的幂次．则当2()1m v k =+时，()
()m f r 为整数．
下面我们对2()v k v =用数学归纳法． 当0v =时，k 为奇数，1k +为偶数，此时
()111()1222f r k k k k ?
?????=++=++ ? ????
?????
为整数． 假设命题对1(1)v v -≥成立．
对于1v ≥，设k 的二进制表示具有形式
1212222v v v v v k αα++++=+?+?+L ，
这里，0i α=或者1，1,2,i v v =++L ． 于是 ()111()1222f r k k k k ?
?????
=+
+=++ ? ?????????
2122k
k k =+++ 11211212(1)2()222
v v v v
v v v ααα-++++=+++?++?+++L L
1
2
k '=+， ①
这里
1121122(1)2()22v v v v v v v k ααα-++++'=++?++?+++L L .
显然k '中所含的2的幂次为1v -．故由归纳假设知，1
2
r k ''=+
经过f 的v 次迭代得到整数，由①知，(1)()v f r +是一个整数，这就完成了归纳证明．
2. (2011年 加试 2) 证明：对任意整数4≥n ，存在一个n 次多项式
0111)(a x a x a x x f n n n ++++=--Λ
具有如下性质：
（1）110,,,-n a a a Λ均为正整数；
（2）对任意正整数m ，及任意)2(≥k k 个互不相同的正整数k r r r ,,,21Λ，均有)()()()(21k r f r f r f m f Λ≠． 证明：令2)()2)(1()(++++=n x x x x f Λ， ①
将①的右边展开即知)(x f 是一个首项系数为1的正整数系数的n 次多项式．
下面证明)(x f 满足性质（2）．
对任意整数t ，由于4≥n ，故连续的n 个整数n t t t +++,,2,1Λ中必有一个为4的倍数，从而由①知)4(mod 2)(≡t f ．
因此，对任意)2(≥k k 个正整数k r r r ,,,21Λ，有
)4(mod 02)()()(21≡≡k k r f r f r f Λ．
但对任意正整数m ，有)4(mod 2)(≡m f ，故
)4)(mod ()()()(21k r f r f r f m f Λ≡/，
从而)()()()(21k r f r f r f m f Λ≠．
所以)(x f 符合题设要求．
3. (2012年 加试 2)
4. (2013年加试2)
5. (2014年加试4)
高中数学竞赛中数论问题的常用方法
高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相
高中数学竞赛数论部分
高中数学竞赛数论部分文档编制序号：[KKIDT-LLE0828-LLETD298-POI08]
初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1．请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首 届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明2131n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++能整除123n ???（1956年上海首 届数学竞赛第一题） （3） 证明：3231 122 n n n ++-对于任何正整数n 都是整数，且用3除时余2。（1956年 北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数 214 143 n n ++不可约简。（1956年首届国际数学奥林匹 克竞赛第一题） （5） 令(,, ,)a b g 和[,, ,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数， 试证：[][][][]()()()() 2 2 ,,,,,,,,,,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题，占% 。
高中数学竞赛辅导初等数论不定方程
不定方程 不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题. 1．几类不定方程 （1）一次不定方程 在不定方程和不定方程组中，最简单的不定方程是整系数方程 )0,0(,0≠>=++b a c by ax 通常称之为二元一次不定方程.一次不定方程解的情况有如下 定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. 定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）。 （2）沛尔)(pell 方程 形如12 2 =-dy x （*d N ∈，d 不是完全平方数）的方程称为沛尔方程. 能够证明它一定有无穷多组正整数解；又设),(11y x 为该方程的正整数解),(y x 中使d y x +最小的 解，则其的全部正整数解由111111111[()()]2)()] n n n n n n x x x y x x ?=+-?? ??=-?? （1,2,3, n =）给 出. ①只要有解),(11y x ，就可以由通解公式给出方程的无穷多组解. ②n n y x , 满足的关系：1(n n x y x y +=+；112 11222n n n n n n x x x x y x y y ----=-?? =-? ， （3）勾股方程2 2 2 z y x =+ 这里只讨论勾股方程的正整数解，只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数。容易看出y x ,一奇一偶，无妨设y 为偶数，下面的结果勾股方程的全部本原解通解公式。 定理三：方程2 2 2 z y x =+满足1),(=y x ，2|y 的全部正整数解),,(z y x 可表为 2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且
高中数学竞赛资料-数论部分 (1)
初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞 赛第一题) （2） ①设n Z ∈，证明213 1n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++ 能整除123n ??? ？（1956年上海首届数学竞赛第一题） （3） 证明：3 231 122 n n n + +-对于任何正整数n 都是整数，且用3除时余2。（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数 214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数，试证： [][][][]()()()() 2 2 ,,,,,,,,,,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题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()2 1 02 x abx a b -++=是否有两个整数解？ 如果有，请把它们求出来；如果没有，请给出证明。 （2007全国初中联赛12）
数论历届高中数学联赛真题分类汇编含详细答案
数论部分 2018A 四、（本题满分50分）数列{}n a 定义如下：1a 是任意正整数，对整数1≥n ，1+n a 与∑=n i i a 1 互 素，且不等于n a a a ,.,,21 的最小正整数，证明：每个正整数均在数列{}n a 中出现。 ★证明：显然11=a 或者12=a .下面考虑整数1>m ，设m 有k 个不同的素因子，我们对k 归纳证明 m 在{}n a 中出现.记n n a a a S +++= 21，1≥n . 1=k 时，m 是素数方幂，记αp m =，其中0>α，p 是素数.假设m 不在{}n a 中出现.由于{}n a 各 项互不相同，因此存在正整数N ，当N n ≥时，都有αp a n >.若对某个N n ≥，n S p |/，那么αp 与 n S 互素，又n a a a ,.,,21 中无一项是αp ，故有数列定义知αp a n ≤+1，但是αp a n >+1，矛盾！ 因此对每个N n ≥，都有n S p |.又1|+n S p ，可得1|+n a p ，从而1+n a 与n S 不互素，这与1+n a 的定义矛盾！ 假设2≥k ，且结论对1-k 成立.设m 的标准分解为k k p p p m αα α 2121=.假设m 不在{}n a 中出现，于 是存在正整数/N ，当/ N n ≥时，都有m a n >.取充分大的正整数 121,,-k βββ ，使得 n N n k a p p p M k /1211121max ≤≤->=-βββ . 我们证明，对/ N n ≥，有M a n ≠+1. 对于任意/ N n ≥，若n S 与k p p p 21互素，则m 与n S 互素，又m 在n a a a ,.,,21 中均未出现，而 m a n >+1，这与数列的定义矛盾，因此我们得到：对于任意/N n ≥，n S 与k p p p 21不互素*， ⑴若存在i （11-≤≤k i ），使得n i S p |，则()1,1=+n n S a ，故1|+/n i a p ，从而M a n ≠+1（因为M p i |）。 ⑵若对每个i （11-≤≤k i ），均有n i S p |/，则由*知，必有n k S p |.于是1|+/n k a p ，进而1|++/n n k a S p ，即1|+/n k S p .故由*知：存在0i （110-≤≤k i ），使得1|0+n i S p ，再由n n n a S S +=+1及前面的假设n i S p |/，可知1|0+/n i a p ，故M a n ≠+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 的一个剩余类(也叫同余类)。K 0,K 1,…,K m-1为模m 的全部剩余类. (2)性质(ⅰ)i m i K Z 1 0-≤≤=Y 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里. (ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ?a ≡b(modm). 2.剩余系的定义与性质 (1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系. 特别地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的绝对最小完全剩余系:当m 为奇数时,2 1 ,,1,0,1,,121,21--+----m m m ΛΛ;当m 为偶数时,12 ,,1,0,1,,12,2--+-- m m m ΛΛ或2,,1,0,1,,12m m ΛΛ-+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系?两两对模m 不同余. (ⅱ)若(a,m)=1，则x 与ax+b 同时遍历模m 的完全剩余系. 证明:即证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),也矛盾!
全国高中数学联赛试题分类汇编-数论(1981年-2019年)
（1981年~2019年） 2019A 5、在1,2,3, ,10中随机选出一个数a ，在1,2,3,,10----中随机选出一 个数b ，则2a b +被3整除的概率为 ． 答案： 37100 解析：首先数组(),a b 有1010100 ?=种等概率的选法． 考虑其中使2a b +被3整除 的选法数N ．①若a 被 3 整除，则b 也被 3 整除．此时,a b 各有3种选法，这样的(),a b 有 339?=组． 若a 不被 3 整除，则()21mod3a ≡，从而()1mod3b ≡-．此时a 有7 种选法，b 有4种选法，这样的(),a b 有7428?=组． 因此92837N =+=．于是所求概率为 37 100 。 2019A 三、（本题满分 50 分）设m 为整数，2m ≥．整数数列12,,a a 满足：12,a a 不 全为零，且对任意正整数n ，均有21n n n a a ma ++=-．证明：若存在整数,r s , (2r s >≥ )使得1r s a a a ==，则r s m -≥． 解析：证明：不妨设12,a a 互素（否则，若()12,1a a d =>，则12,1a a d d ?? = ?? ?互素，并且用 12 ,,a a d d 代替12,, a a ，条件与结论均不改变）． 由数列递推关系知()234mod a a a m ≡≡≡ ． ① 以下证明：对任意整数3n ≥，有()()2123mod n a a a n a m m ≡-+-????． ② ………10 分 事实上，当3n =时②显然成立．假设n k =时②成立（其中k 为某个大于2的整数），注意到①，有()212mod k ma ma m -≡，结合归纳假设知 ()()()2 1122221232mod k k k a a ma a k a m ma a a k a m +-≡-≡+--=-+-???????? ，即1n k =+时②也成立．因此②对任意整数3n ≥均成立． ………………20 分
高中数学竞赛专题讲座---竞赛中的数论问题
竞赛中的数论问题的思考方法 一. 条件的增设 对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。 1. 大小顺序条件 与实数范围不同，若整数x ，y 有大小顺序x 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模 的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。 从而对，使得； 若，，则，，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。 除外，别的数可两两配对，积除以余1。故。 定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为： 这里，，以及满足，（即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：（拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。 定理6：若为对模的阶，为某一正整数，满足，则必为的倍数。 以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到 高中数学竞赛资料-数论部分-(1) 初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和 9x+5y 能同时被整除。(1894年首届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明213 1 n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++L 能整除 123n ???L ？（1956年上海首届数学竞赛第一题） （3） 证明：3 231 122 n n n ++-对于任何正整数n 都是整数，且 用3除时余2。（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,,,)a b g L 和[,,,]a b g L 分别表示正整数,,,a b g L 的最大 公因数和最小公倍数，试证：[][][][]()()()() 2 2 ,,,,,,,,,,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题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。 如果将有一定“数论味”的计数型题目统计在内，那么 比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程323 ++=-+的整数解(,)x y的个数是（） 652 x x x y y A、0 B、1 C、3 D、 无 穷 多 （ 2 7 全 国 初 中 联 课程简介：全国高中数学联赛是中国高中数学学科的最高等级的数学竞赛，其地位远高于各省自行组织的数学竞赛。在这项竞赛中取得优异成绩的全国约90名学生有资格参加由中国数学会主办的“中国数学奥林匹克（CMO）暨全国中学生数学冬令营”。优胜者可以自动获得各重点大学的保送资格。各省赛区一等奖前6名可参加中国数学奥林匹克，获得进入国家集训队的机会。中小学教育网重磅推出“全国高中数学联赛”辅导课程，无论是有意向参加竞赛的初学者，还是已入围二试的竞赛选手，都有适合的课程提供。本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学教师李秋生等名师主讲，轻松突破你的数学极限！ 课程招生简章：https://www.wendangku.net/doc/c818748278.html,/webhtml/project/liansaigz.shtml 选课中心地址： https://www.wendangku.net/doc/c818748278.html,/selectcourse/commonCourse.shtm?courseeduid=170037#_170037_ 第一章数论专题 我们把未知数的个数多于方程的个数,且其解受到某种限制的方程,叫做不定方程.通常主要研究不定方程的正整数解、整数解、有理数解等. 不定方程问题的常见类型是： （1）求不定方程的解； （2）判定不定方程是否有解； （3）确定不定方程解的数量（有限还是无限）. 不定方程问题的常用解法是： （1）代数分析与恒等变形法，如因式分解、配方、换元等； （2）估计范围法，利用不等式放缩等方法,确定出方程中某些变量的取值范围,进而求整解； （3）同余法，即恰当选取模m,对方程两边做同余分析,以缩小变量的范围或发现性质,从而得出整解或判定无解； （4）构造法，构造出符合要求的特解,或构造一个求解的递推式,证明方程有无穷多解； （5）无穷递降法，无穷递降法是一种用反证法表现的特殊形式的归纳法,由Fermat创立并运用它证明了方程x4+y4=z4没有非零整解.从此,无穷递降作为一种重要的数学思想方法广为流传应用,并在平面几何、图论及组合中经常用到它. 引例：求所有正整数对（x,y）满足x y=y x-y. 高一竞赛数论专题 1.整除 设,,0.a b Z a ∈≠如果存在,q Z ∈使得,b aq =那么就说b 可被a 整除(或a 整除b ),记做|.a b 且称b 是a 的 倍数,a 是b 的约数(也可称为除数、因数).b 不能被a 整除就记做a b ? . 整除关系的基本性质 (1)|,||.a b b c a c ? (2)|,|a b a c ?对任意的,,x y Z ∈有|.a bx cy + 设12,a a 是两个不全为零的整数,如果1|d a 且2|,d a 那么d 就称为1a 和2a 的公约数,我们把1a 和2a 的公约数中的最大的称为1a 和2a 的最大公约数,记做12(,).a a 若12(,)1,a a =则称1a 和2a 是既约的,或是互素的. 设12,a a 是两个均不为零的整数,如果1|,a l 且2|,a l 那么l 就称为1a 和2a 的公倍数,我们把1a 和2a 的公倍数中的最小的称为1a 和2a 的最小公倍数,记做12[,].a a 1.设12,a a 是两个不全为零的整数,证明对任意整数q ,都有12121(,)(,).a a a a qa =+ 2.设(,)1,a b =证明(1)若|,|a c b c 则|.ab c (2)若|a bc 则|.a c 3.(Bezout 定理)设,a b 是不全为零的整数,证明(,)1a b =的充要条件是存在整数,x y 使得 1.ax by += 4.证明对任意整数n ,652 22n n n n +--能被120整除. 5.设m 是一个大于2正整数,若存在正整数n 使得21|21m n -+.求m 的所有可能取值. 初等数论简介 绪言：在各种数学竞赛量出现数论题，题目的容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学 竞赛第一题) （2） ①设n Z ∈，证明213 1n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++能整除123n ???？（1956年首届数学竞赛第 一题） （3） 证明：3 231 122 n n n + +-对于任何正整数n 都是整数，且用3除时余2。 （1956年、市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,, ,)a b g 和[,, ,]a b g 分别表示正整数,, ,a b g 的最大公因数和最小公倍数，试证： [][][][]()()()() 2 2 ,,,,,,,,,,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题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在，那么比例还会高很多。 3.请看近年来国外重大竞赛中出现的数论题： (1)方程3 2 3 652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()2 1 02 x abx a b -++=是否有两个整数解？ 如果有，请把它们求出来；如果没有，请给出证明。 （2007全国初中联赛12） 数学竞赛中的数论问题 罗增儒 引言 数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支． 什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数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岁的波萨就发表了图论中“波萨定理”． ●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大 数论 一 、欧拉定理 设1m >的整数，()()(),1,1m a m a mod m ?=≡则. 例1 设(1000 5x = +，求 []x 的末三位数. 解 由二项式定理， ()()() () 2499 500 998349963998 2 3 3 100010001000 5235235 2323C C ?++ ++?? () (500 1000 3 25 225mod +335， ()(500 1000 250025 25 212mod =≡≡()328y mod ≡， (2552y mod ≡(2y mod ≡则 ()28min y mod =， 所以 则 因为 所以 ()()10010021125,31125mod mod ≡≡， 于是，有 ()()150050021125,31125mod mod ≡≡， () ()500 3 2232125mod ≡， 又因为 ()150********mod ≡， () 2255=(320y mod +≡ （2）p 为素数，则 ()p a a mod p ≡. 例2 ,,,a b c d 为整数，证明 ()44240/b d c d a a ++-. 证明 4240235=， 由于 所以 ()()444403b d c d d b c a a a a a mod ++-=-≡. 即 443/()b d c d a a ++-. 由于奇数的4次方被16除余1，偶数的4次方被16除余0，故有 ()()4444016b d c d d b c a a a a a mod ++-=-≡. () ()3 8 9 333a a a a a a mod ≡==≡≡， 同理 则 ()19991999199903d a b c a b c mod =++≡++≡. 即3/d . 数学奥赛辅导 第四讲 不定方程 不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题. 1．几类不定方程 （1）一次不定方程 在不定方程和不定方程组中，最简单的不定方程是整系数方程 )0,0(,0≠>=++b a c by ax ①通常称之为二元一次不定方程.一次不定方程解的情况有 如下定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. 定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）。 （2）沛尔)(pell 方程 形如122=-dy x （*d N ∈，d 不是完全平方数）的方程称为沛尔方程. 能够证明它一定有无穷多组正整数解；又设),(11y x 为该方程的正整数解),(y x 中使d y x +最小的 解，则其的全部正整数解由111111111[()()]2)()] n n n n n n x x x y x x ?=+?? ??=--?? （1,2,3,n = ）给 出. ①只要有解),(11y x ，就可以由通解公式给出方程的无穷多组解. ②n n y x , 满足的关系：1(n n x y x y +=+；112 11222n n n n n n x x x x y x y y ----=-?? =-? ， （3）勾股方程2 2 2 z y x =+ 这里只讨论勾股方程的正整数解，只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数。容易看出y x ,一奇一偶，无妨设y 为偶数，下面的结果勾股方程的全部本原解通解公式。 定理三：方程2 22z y x =+满足1),(=y x ，2|y 的全部正整数解),,(z y x 可表为 2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且 近五年全国高中数学联赛选编——数论 2015.8.16 1.(2010年 加试 2) 设k 是给定的正整数，12 r k =+．记(1)()()f r f r r r ==????，() ()l f r = (1)(()),2l f f r l -≥．证明：存在正整数m ，使得()()m f r 为一个整数．这里，x ????表示不小于实数x 的最小 整数，例如：112 ??=???? ，11=????． 证明：记2()v n 表示正整数n 所含的2的幂次．则当2()1m v k =+时，() ()m f r 为整数． 下面我们对2()v k v =用数学归纳法． 当0v =时，k 为奇数，1k +为偶数，此时 ()111()1222f r k k k k ? ?????=++=++ ? ???? ????? 为整数． 假设命题对1(1)v v -≥成立． 对于1v ≥，设k 的二进制表示具有形式 1212222v v v v v k αα++++=+?+?+L ， 这里，0i α=或者1，1,2,i v v =++L ． 于是 ()111()1222f r k k k k ? ????? =+ +=++ ? ????????? 2122k k k =+++ 11211212(1)2()222 v v v v v v v ααα-++++=+++?++?+++L L 1 2 k '=+， ① 这里 1121122(1)2()22v v v v v v v k ααα-++++'=++?++?+++L L . 显然k '中所含的2的幂次为1v -．故由归纳假设知，1 2 r k ''=+ 经过f 的v 次迭代得到整数，由①知，(1)()v f r +是一个整数，这就完成了归纳证明． 2. (2011年 加试 2) 证明：对任意整数4≥n ，存在一个n 次多项式 0111)(a x a x a x x f n n n ++++=--Λ 具有如下性质：初等数论中的几个重要定理高中数学竞赛
高中数学竞赛资料-数论部分-(1)
高中数学联赛数论专题
高一年级竞赛数学数论专题讲义：1整除
高中数学竞赛资料-数论部分
数学竞赛中的数论问题
高中竞赛数学辅导：数论重要定理
高中数学竞赛辅导-初等数论(不定方程)
近五年全国高中数学联赛选编数论
- 数论历届高中数学联赛真题分类汇编含详细答案
- 完整word版,高中数学竞赛辅导-初等数论(不定方程)
- 高中数学竞赛——数论
- 数学竞赛中的数论问题
- 高中数学竞赛中数论问题的常用方法
- 高中数学竞赛资料-数论部分
- 高中数学竞赛专题讲座---竞赛中的数论问题
- 高中数学竞赛资料-数论部分-(1)
- 高中数学竞赛资料数论部分
- 高中数学竞赛 数论部分
- 高中数学竞赛资料-数论部分 (1)
- 学习版高中数学竞赛数论.doc
- 初等数论中的几个重要定理 高中数学竞赛
- 高中数学竞赛资料数论部分
- (完整版)高中数学竞赛辅导-初等数论(不定方程)
- 全国高中数学联赛试题分类汇编-数论(1981年-2019年)
- 高中数学联赛初等数论专题练习(带答案详解版)
- 高中数学竞赛数论部分
- 四川省成都七中高中数学竞赛数论专题讲义及详解：1整除
- 高中数学竞赛辅导初等数论不定方程