初等数论简介
绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子：
（1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞
赛第一题)
（2） ①设n Z ∈，证明213
1n
-是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)方程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） （3）①是否存在正整数,m n ，使得(2)(1)m m n n +=+？
②设(3)k k ≥是给定的正整数，是否存在正整数,m n ，使得()(1)m m k n n +=+？ （2007全国初中联赛14） （4）关于,x y 的方程2
2
229x xy y ++=的整数解(,)x y 得组数为（ ） A 、2 B 、3 C 、4 D 、无穷多
（2009全国初中联赛5） （5）已知12345,,,,a a a a a 是满足条件123459a a a a a ++++=的五个不同的整数，若b 是
关于x 的方程()()()()12345()2009x a x a x a x a x a -----=的整数根，则b 的值为 （2009全国初中联赛8）
（6）已知正整数a 满足3192191a +，且2009a <，求满足条件的所有可能的正整数a 的和。 （2009全国初中联赛12）
（7）n 个正整数12,,,n a a a L 满足如下条件：1212009n a a a =<<<=L ；且12,,,n a a a L 中任意1n -个不同的数的算术平均数都是正数，求n 的最大值。
（2009全国初中联赛14） (8)在一列数123,,,x x x …中，已知11x =，且当2k ≥时，11214()44k k k k x x ---????
=+--?
???????
（取整符号[]a 表示不超过实数a 的最大整数，例如[][]2.62,0.20==）则2010x 等于（ ） A 、 1 B 、 2 C 、 3 D 、 4 （2010全国初中联赛4） （9）求满足2
2
282p p m m ++=-的所有素数P 和正整数m 。
（2010全国初中联赛13）
（10）从1,2,,2010…这2010个正整数中，最多可以取出多少个数，使得所取出的数中任意三个数之和都能被33整除？ （2010全国初中联赛14）
（11）设四位数abcd 满足3
3
3
3
110a b c d c d ++++=+，则这样的四位数的个数为 （2011全国初中联赛10）
（12）已知关于x 的一元二次方程2
0x cx a ++=的两个整数根恰好比方程2
0x ax b ++=的两个根都大1，求a+b+c 的值
（2011全国初中联赛11）
（13）若从1,2,3,,n …中任取5个两两互素的不同的整数12345,,,,a a a a a 其中总有一个整数是素数，求n 的最大值。
（2011全国初中联赛13） （14）把能表示成两个正整数平方差的这种正整数，从小到大排成一列：
12,,n a a a …，例如221213a =-=，222325a =-=，……那么2007a =
（2007福建省高一数学竞赛12）
（15）求最小的正整数n ，使得集合{1,2,3,,2007}…的每一个n 元子集中都有2个元素（可以相同），它们的和是2的幂。
（2007福建省高一数学竞赛14） （16）两条直角边长分别是整数a 和b(其中b<1000)，斜边长是b+1的直角三角形有（ ） A 、20个 B 、21个 C 、22个 D 、43个
（2008福建省高一数学竞赛5）
（17）设x 、y 为非负整数，使得2x y +是5的倍数，x y +是3的倍数，且299x y +≥，则75x y +的最小值为
（2008福建省高一数学竞赛11） （18）正整数1212a a a ≤≤≤…中，若任意三个都不能成为三角形的三边长，则12
1
a a 的最小值是 （2008福建省高一数学竞赛12）
（19）设{1,2,3,,}S n =…（n 为正整数），若S 得任意含有100个元素的子集中必定有两个数的差能被25整除，求n 的最大值。 （2008福建省高一数学竞赛17）
（20）设[]x 是不超过x 的最大整数，则123500
3333log log log log ????????++++????????…=
（2009福建省高一数学竞赛11）
（21）已知集合M 是集合{1,2,3,,2009}S =…的含有m 个元素的子集，且对集合M 的任意三个元素x,y,z 均有x+y 不能整除z ，求m 的最大值。
（2009福建省高一数学竞赛17）
（22）已知a,b,c 为正整数，且1c b a >>>，1
11()()()a b c c a b
---为整数，则a+b+c=
（2011福建省高一数学竞赛12） （23）正整数500n ≤，具有如下性质：从集合{1,2,,500}…中任取一个元素m ，则m 整除n 的概率是1
100
，则n 的最大值是
（2008福建省预赛12） （24）设()f x 施周期函数，T 和1是()f x 的周期且01T <<，证明：
（1）若T 为有理数，则存在素数P ，使
1
p
是()f x 的周期； （2）若T 为无理数，则存在各项均为无理数的数列{}n a 满足10n m a a >>>，（n=1,2, …）且每个n a 都是()f x 的周期 （2008全国高中联赛加试二）
（25）方程[]
9
2
x x
=
的实数解事 （其中[]x 表示不超过x 的最大整数） （2009福建初赛9）
（26）设}
1,1,2,,2010i x i ∈
=…，令123420092010S x x x x x x =++…
（1）S 能否等于2010？证明你的结论； （2）S 能取到多少个不同的整数值？
（2009福建初赛14）
（27）设,k l 是给定的两个正整数，证明：有无穷多个正整数m k ≥，使得k
m C 与l 互素。 （2009全国高中联赛加试三）
（28）已知集合{}
230123777A x x a a a a ==+?+?+?，其中{}0,1,2,3,4,5,6i a ∈，0,1,2,3i =，且
30a ≠，若正整数,m n A ∈，且2010,m n m n +=>，则符合条件的正整数m 有 个。
（2010福建预赛6）
（29）将方程[]3
34x x -?=的实数解从小到大排列得12,,k x x x …，则3333123k x x x x +++…的值为
（2010福建预赛8）
（30）设k 是给定的正整数，12
r k =+
，记(1)()(1)
()()[],()(())l l f r f r r r f r f f
r -===，2l ≥。证明：存在正整数m ，使得()
()m f r 为一个整数。这里，[]x 表示不小于实数x 的最小整数。
（2010全国高中联赛加试二）
（31）已知正整数x,y,z 满足条件(14)(14)(14)xyz x y z =---，且28x y z ++<，则222
x y z ++的最大值为
（2011福建预赛7）
（32）证明：对任意整数4,n ≥存在一个n 次多项式1
110()n n n f x x a x a x a --=+++…具有如下性质：
（1）011,,,n a a a -…均为正整数；
（2）对任意正整数m ，及任意(2)k k ≥个互不相同的正整数12,,,k r r r …均有12()()()()k f m f r f r f r ≠… （2011全国高中联赛加试二）
（33）证明：存在无穷多个正整数n ，使得2
1n +有一个大于2n +
（2008第49届IMO.3）
（34）设n 是一个正整数，12,,(2)k a a a k ≥…是集合{}1,,n …中互不相同的整数，使得对于1,,1i k =-…都有n 整除1(1)i i a a +-。
证明：n 不整除1(1)k a a - （2009第50届IMO.1）
本资料主要介绍中学代数课程里未能深入谈到的整数的性质及其应用，初等数论的解题过程通常不涉及很多的基础知识，重要的是机智和灵活。本资料除打上“*”的是少数内容外，初二年以上的学生均可学习掌握。
为叙述方便，本资料中的字母均表示整数。交有Z ，N*，Z*分别表示整数集，正整数集和非零整数集。
整数的概念、分类、自然数两种理论（基数理论，序数理论）
基数用于表示“多少”：将所有有限集分类，使所含元素个数一样多的集合成为同一类，对每一类用一个记号来表示它们（这一类的集合）所含元素个数一样多这个共同特征。这个记号就是一个自然数。
公理化的方法：对已有的知识进行深入的分析，选择其中一些基本关系作为不定义的概念，一些基本性质作为不加证明的公理，建立起公理系统。然后由所建立的公理系统出发，应用形式逻辑的方法，来给出其它有关概念的定义，并证明各种命题。
序数表示“第几”*（peano 定理）如果非空集合N*中的某些元素之间有一个基本关系“直接后继”（元素a 的直接后继记为a ’），且N*满足以下条件： 1．*
*
1,N a N ?∈?∈，必有1a '≠ 2．()
**,a b a b a N b N ''=?=∈∈ 3．()
**,a b a b a N b N ''=?=∈∈ 4．N*的子集M 若具有下面的性质
))*1,i M ii a M a M M N '∈∈?∈=则
定理1 带余除法
设a Z ∈，*
b Z ∈则有且只有一对整数q 与r ，使得a bq r =+其中0 定义1、定理1中的q 与r 分别称a 除以b 的不完全商与最小非负余数，简称商和余数。 定义2、定理1中的0r =时（即a bq =时）就称a 为b 的倍数，b 是a 的约数（或因数）a 能被b 整除， b 整除a ，记作b a 性质1、① 0是任何数的倍数（0除外）； ② 1±是任何数的约束； ③ * a Z a a ∈?； ④ b a b a b a b a ?-???-????； ⑤ 0b a b a a ?? ?≤? ≠??； ⑥ b a a b a b ???=±??? ； ⑦ * b a bc ac c Z ????∈?? ； ⑧ b a b ac c Z ?? ??∈??； ⑨ a b a c b c ?? ????； ⑩ 11,2,3,,i n i i i i b a k Z b k a i n =? ?∈???=? ∑L 公式1、1 221()()n n n n n n x y x y x x y xy y -----=-++++L *()n N ∈ 公式2、1 221()()n n n n n n x y x y x x y xy y -----=+-++-L （n 是正偶数） 公式3、1 221()()n n n n n n x y x y x x y xy y ----+=+-+-+L （n 是正奇数） （以上三个公式中的,x y 可以是任意实数） 例1、设9999b =L （31位数）9999a =L (1984位数)，求证b a 。 例2、设a c ab cd -+求证a c ad bc -+。 定义3、能被2整除的数称偶数，不能被2整除的数称奇数。 性质2、用“0”代表偶数，“1”代表奇数，则有 ① 0+0=0,0+1=1，1+0=1,1+1=0 ②0?0=0,0?1=0,1?0=0,1?1=1 ③奇数个奇数的和还是奇数 ④任意个奇数之积是奇数 *例3、设,p q 都是正奇数，且2p q =+，求证q p p q q p ++ 注意：奇偶分类在处理很多问题时有用。求末位数问题： 令()G a 表示a 的末位数，则有 性质3、①[]()()()G a b G G a G b +=+ ②[]()()()G a b G G a G b ?=? ③()()m m G a G G a ??=?? ④任一自然数的正整数次幂的末位数有周期变化的规律。 例4、 求1988 17 的末位数 例5、 ①设,n R 为自然数，求证4()()R n n G a G a +=； ②设n 为自然数，求证44 ()()n G a G a = 例6、67 67(67)G 性质4、①设b 为奇数，c 为偶数，则()()c b G a G a = ②设b 为偶数，c 为奇数（1c >）则4()()c b G a G a = ③设b 为偶数， c 为偶数，则4()()c b G a G a = ④设b 为奇数， c 为奇数，（1c >）则()()c b b G a G a = 例7、求19 19 19 (22 )n G N 个 *例8、求21112 13a =N 的末两位数。 例9、设1237,,,a a a a L 是1,2,3,,7L 这七个自然数的任何一种次序的排列， 求证：1237(1)(2)(3)(7)a a a a ----L 总是一个偶数。 例10、某班有49位同学，坐成七行七列，每个座位的前、后、左、右的座位叫做它的“邻座”，要让这49位同学中的每一位都换到他邻座上去，问这种调换座的方案能否实现？ 作为本节内容的结束，请注意以下两个重要的命题： ① 在(2)m m ≥个相邻整数中，有且只有一个数能被m 整除。 ② 若整数1g >，则任一正整数a 能够唯一表示为1 110n n n n a a g a g a g a --=++++K 这里,0i a Z n ∈≥，且0<,0,1,2,3,,i a g i n ≤=L 习题： 1. 用票面为3分和5分的邮票可以支付任何n （整数7n >）分的邮资。 2. 把十个数码0，1,2,3,4……，9任意两两搭配，组成没有重复数码的5个两位数，求证这样5个两位数 的和是9的倍数。 3. 设10,10p a b p c d --，求证：p ad bc - 4. 设a 是奇数，求证：281a - 5. 证明：各位数码全是1的数中，有且只有一个是平方数。 6. 证明：前n 个自然数和的个位数码不能是2,4,7,9 7. 设a Z ∈，求证(1)(2)(3)1a a a a ++++时奇数的平方。 8. 设10n a k =?，n 为自然数，k 是非负整数，求证：(1)(3)(7)(9)a a a a ++++的末三位数是189。 9. 证明：整数a 能够表示成两个整数平方和的充要条件是2a 也具有相同性质。 10. 设整数,,,,x a b c d 互不相等，且()()()()4x a x b x c x d ----=，求证4x a b c d =+++ 11. 设2n ，求证42 16411n n ++。 12. 设32*()55 51()n n n f n n N =+++∈，证明：当且仅当4n 时，13()f n 。 13. 已知0n ≥，求证：3321n n + 14. 证明：在任意n 个整数中，总可以找到(1)k k n ≤≤个整数，使它们的和是n 的倍数。 15. 能否把1,1,2,2,3,3,,1986,1986L 这些数排成一行，使得两个1之间夹着一个数，两个2之间夹着两 个数，……，两个1986之间夹着1986个数？请证明你的结论 （首届全国数学冬令营竞赛试题五） 16. 设正整数d 不等于2,5,13，证明集合{}2,5,13,d 中可以找到两个不同元素,a b 使1ab -不是完全平方 数 （第27届IMO ） 定义1、若,1,2,,,2i d a i n n =≥L 就称d 是这几个数的公因数； 定义2、(2)n n ≥个不全为零的整数i a 的公因数中的最大数叫做这几个整数的最大公因数，记 12(,,)n a a a L 性质一：12(,,)1n a a a ≥L 定义3、若12(,,)1n a a a =L ，则称12,,n a a a L 互素（互质） 定义4、若,1,2,,,2i a m i n n =≥L ，则称m 是i a 的公倍数； 定义5、非零整数的一切正的公倍数中的最小正数叫最小公倍数，记[]12,,n a a a L 定理1、若,,a b c 不全为零，且a bq c =+则(,)(,)a b b c = 性质二：1212(,,,)(,,)n n a a a a a a =L L 定理2、若(,)c a c a b c b ?? ???? 定理3、若整数,a b 不全为零，则存在整数,x y 使得(,)ax by a b += 性质三：* m N ∈，(,)(,)ma mb m a b = 性质四：若(,)1a c =，则(,)(,)ab c b c = 定理4、若,a k b k ，则[],a b k 定理5、若,a b 是同号整数，则[](),,a b a b ab = 例1、 形如221(0)n n F n =+≥的数称费尔马数，求证(,)1i j F F =，这里,i j 都是非负整数，且i j ≠ 例2、 设**,,a N b N ∈∈且a b ≠，证明(21,21)1(,)1a b a b --=?= 例3、 已知(,)1a b =，求证(,)1ab a b += 例4、 设()f x 使非零整系数多项式，()()6263f f ，，求证()66f 例5、 求证[](,,)(,)a b a b a b += 例6、 设* m N ∈，证明：当且仅当[],m a b =时，,1m m a b ?? = ??? 例7、 已知12,,,n a a a L 是两两互素的正整数，求证：[]12123,,,n n a a a a a a a =L L 例8、 求证平方数的正因数有奇数个，非平方数的正因数有偶数个。 例9、 有一百盏电灯，排成一行，自左向右，编号1,2,3,,99,100L 。每灯由一拉线开关控制，最 初灯全关着。另有一百个学生顺次走过，第k 个学生把凡是编号为k 的倍数的电灯开关拉一下， (1,2,3,,100)k =L 问：100个学生全部过去之后，有哪几个编号的灯还亮着？ 习题： 1、设k a 表示各位数码都是1的k （k N ∈）位数，求证： (,)1m n a a =的充要条件是(,)1m n =，这里*,m n N ∈，且m n ≠ 2、设00ax by +是形如ax by +（,a b 不全为0）的数中最小正数。 求证：（1）00ax by ax by ++； （2）00(,)ax by a b += 3、设(,)1x y =，求证(,)12x y x y +-=或 4、设(,),(,)a b d a b d '''==，求证(,,,)aa ba ab bb dd '''''= 5、已知：,a b 为非零自然数，n N ∈ 求证：（1）(,)(,)n n n a b a b =；（2）[,][,]n n n a b a b = 6、设* a Z ∈，证明：数列,2,3,,a a a na L 中n 的倍数共有(,)n a 个。 7、设a Z ∈，求证6(1)(21)a a a ++ 8、已知：126n x x x +++L ，求证3 3 3 126n x x x +++L 9、设n 是奇数，,n a b n a b +-，求证(,)n a b 10、设(,10)1a =，证明：各位数码全是1的数中有a 的倍数 11、求证(,,)((,),)a b c a b c = 本节的定义、定理、性质较为繁杂，为便于记忆，整理成以下图式： 自然数集的进一步分类：素数、合数、1 定义 如果大于1的整数p 恰有两个正因数1与P ，就说P 是素数，如果正整数N*有多于两个的正因数，就说N*是合数。 例1：证明：对任给的正整数N*，总可找到N*个相邻的合数。 定理一：任一整数N*的最小因数P （P>1）是素数（N*>1） 定理二：素数有无限多个。 定理三：若N*是合数，P （P>1）是N*的最小正因数，则p ≤ 以上的例子和定理分别刻画了素数的某些分布特征和判断素数的方法。 定理四：若,1,2,3,,i a Z i n ∈=L ，P 是素数，12n p a a a L 则P 整除某个i a 定理五：（唯一分解定理）每个大于1的整数，都可唯一地分解成素因数（不计因数的顺序）的积。 推论：任一大于1的整数a 可以唯一分解成1212k k a p p p ααα =L 这里i p 是相异的素数，i α是正整数。有 时为了表述方便，允许0i α=，上式称为a 的标准分解式。 例2、设21()m m N +∈是素数，求证：m 是2的非负整数次幂。 定理六：若,a b 得标准分解式为1212n n a p p p ααα =L ，1212n n b p p p β ββ=L ， 则1212(,)n r r r n a b p p p =?L ，1212[,]n n a b p p p δ δδ =?L 。 这里min(,)i i i r αβ=，max(,)i i i δαβ= ，1,2,,i n =L 、 例3、求证[,,](,,)a b c ab bc ca abc = 定理七：若a 的标准分解式为1212n n a p p p ααα=L ，则a 的一切正因数的个数1 ()(1)n i i a τα == +∏，a 的 一切正因数的和为11 1 ()1i n i i i p a p ασ+=-=-∏。 例4、证明形如41()n n N -∈的素数有无限个。 哥德巴赫于1742年在和欧拉的通信中提出的猜想： 1． 每个大于5的偶数都是两个奇素数之和 2． 每个大于8的奇数都是三个奇素数之和 1973年5月《中国科学》杂志刊出陈景润研究G 氐猜想的结果： “任一充分大的偶数是一个素数和另一个素数的和，后者或为素数，或仅另两个素数的乘积。” 此定理被简称为“1+2”当然离“1+1”还有一段距离，不过这已经是当今最优成果了。 习题： 1、 设p 是异于3的奇素数，求证2241p - 2、 设,p q 是素数，且5p q >>，求证44240p q - 3、 设整数,,a b c 都大于1，证明[(,),(,)]([,],)a c b c a b c = 4、 求证：22 [,,](,)(,)(,)(,,)[,][,][,]a b c a b b c c a a b c a b b c c a = 5、 设,a n 都是大于1，1n a -是素数，求证：2a =，且n 是素数 6、 从1到100这100个自然数中，任意选出51个数，求证其中至少有两个数，它们中的一个是另一个的 倍数。 7、 设,,(,)1a b N a b ∈=，证明(,)()();()()()a b a b ab a b τττσσσ== 8、 证明：形如32n +的素数有无限多个。 9、 设2n >，证明：在n 与!n 之间至少有一个素数。 10、设n p 是表示由小到大排列的第n 个素数，证明2 2n n p < 定义 给定正整数m ，如果用它除任意两个整数a,b ，所得余数相同，就说a,b 对于模m 同余，记作 ()mod a b m ≡。若所得余数不同，就说a,b 对于模m 不同余，记作()mod a b m ≡。 定理与性质 例1 正整数a 能被9整除的充要条件是a 的各个数码之和能被9整除。 例2 设110=n n a a a a a -???，求证：()()0121110mod n n a a a a a n ?-+???+-≡。 例3 求正整数a 能被7正处的充要条件。 例4 设4444 4444 的各个数码之和为a ，a 的各个数码之和为b ，求b 的各个数码之和为c 。 例5 一环形公路上有几个汽车站，海拔高度只有5米和10米两种，若相邻两站的海拔高度相等，则 称连接它们的公路是水平的；如果两相邻汽车站海拔高度不等，则称相连公路是有坡的。有一旅行者坐汽车环行东路一周，发现水平公路的段数与有坡公路的段数相等，求证4整除n 。 例6 设()1234n n n n n P n N =+++∈，问：怎样的n 使得10|n P 。 例7 求证：任何整数1214 ,,,x x x ???都不能满足方程 44412141599 x x x ++???+=。 习题 1. 设()mod a b n ≡，求证：()(),,a m b m =。 2. 设()5mod10a ≡，求证：()2 25mod100a ≡。 3. 设ABCDE 是按逆时针方向排列的五角棋盘，从A 沿逆时针方向移动棋子，第K 次移动K 步，证明无论移动多少次，C 、E 处永远不可能停留棋子。 4. 设a b Z ∈、，P 是素数，求证()()mod p p p a b a b p +≡+。 5. 证明()()()2 2 2140mod360n n n --≡。 6. 设,n a N ∈，2|a ，求证()221mod 2n n a +≡。 7. 已知()4mod9n ≡，求证n 不能表为3个立方数的和。 8. 已知()7mod8n ≡，求证n 不能表为3个平方数的和。 9．求出一个整数能被101（或37）整除的充要条件。 10．求下列各数的末两位数：777和9 99。 11．记07a ≤<，且()10 1010mod7a ≡，求a 。 12．已知792|1345ab c ，求a 、b 、c 。 补充题： 1. （1）有几个住鞥书，其积为n ，其和为零。求证4 | n 。 （2）设4 | n ，求证：可以找出几个整数，使其积为n ，其和为零。 （十八届全苏中学生竞赛） 2. 设a ，b ，c 是三个互不相等的正整数，求证：在3 3 a b ab -，3 3 b c bc -，3 3 c a ca -三个数中，至少有一个数能被10整除。 （86. 全国初中联赛，二试，四） 3. 把19,20，…，79,80诸数连写成数A=192021…7980，试证1980 | A 。 （全苏14届 1980.8.1） 4. 试求所有能被11整除的三位数，且除得之商等于被除数中各数字的平方和。 （二届IMO 1960） 若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类别的数，则称此方程或方程组为不定方程。不定方程常联系到一些有趣的问题。竞赛中也时有所见。 例1 在等式537850x yz ?=中还原数学x, y, z 。（1987年全俄中学生竞赛题） 例2 解方程xyz zyx xzyyx ?=。（1978年广东省中学数学竞赛题） 例3 求方程w 2+2+2+2=20.625x y z 满足条件：>>>w x y z 的整数解。（1979年湖南省中学数学竞赛 题） 定义1 设x 为任一实数，[]x 表示不超过x 的最大整数。 函数 []x 称数论函数，也称高斯函数、阶梯函数等。数论问题是竞赛中的热门课题，而[]x 则是热门 中的热门。 由定义，显然有①[]x Z ∈；②[][]1x x x ≤<+。 定义2 {}[]x x x =-称为x 的小数部分，显然{}01x ≤<。 例1 计算。 例2 求 ,n N ∈ 。 例3 解方程[]2 x x = 。 例4 已知方程[]1 312 2 x x +=- ，求所有根的和。（1987年初中联考） 习题 1. 56157 85 x x +- ?? = ?? ??。 2. 210 x? -+= ?。 3. [] 33 x x -= 。（英斯科第20届奥林匹克数学竞赛题） 有时也常令[][) =,0,1 x xαα -∈ 通过对α的讨论来解题。 例5 方程 [] 2 440510 x x -+= 的实数解的个数是（）。（1985美国数学竞赛题） (A) 0 ; (B) 1 ; (C) 2 ; (D) 3 ; (E) 4 . 例6 记[]x 表示不超过x的最大整数，设n是自然数，且 () 2 2 I=1 n n ++- ，那么（）。（1986年全国初中联考）（A）I > 0 ; （B）I < 0 ; （C）I = 0 ; （D）当n取不同的值时，以上三种情况都有可能出现 例7 求正数x ，使得[]{} 2 x x x =? 。 性质1 []x 是不减函数。 性质2 [][] x m x m +=+ 当且仅当m Z ∈时成立。 性质3 对任意实数x 、y ，有[][][][][] +1 x y x y x y ≤+≤++ 。 性质4 设m 、n为正整数，在数列1，2，…，（n-1），n 中，m的倍数有 n m ?? ?? ??个。 定理 设p 为一素数，在n! 中p 的方次数等于 21r r n n n p p p ∞ =??????=++???????????? ∑L 例8 在1000!的十进制展开中，以多少个0为结尾？ 例9 求证方程[][][][][][]248163212345x x x x x x +++++=无实数解。 例10 设N 为一正整数，问方程[]() 2 22 x x x x ??-=-??在区间1x N ≤≤中有多少个解？（1982年瑞 典数学竞赛题） 例11 试决定1980 的小数点前一位数字和后一位数字。（1980年芬兰等欧洲四国数学竞赛 题） 例12 在整数列 222121980198019801980??????????????? ??????，，，中，含有多少个互不相等的自然数？（1980苏联列宁格勒中学生数学竞赛试题） 习题 1． 设M =N （其中1x ≥）。则一定有（ ） （1985年北京市中学生数学竞赛高一年试题） （A ）M>N ; (B) M=N ; (C) M 2 ．设S =++++L ，那么的值是 3． ①找出一个实数x ，满足{}11x x ?? +=? ???； ②证明，满足上述等式的x 都不是有理数。 4． 设n N ∈，计算和+1=0+22k k k n ∞ ??????∑。（1968第十届IMO ） 5． 设a , b 为互素的正整数，求证：()()()1112+++2b a a b a a b b b ---?????? ???=????????????。 6． 求所有自然数n , 使得22min 1991n k k ????+= ???????，这里 2n k ??????表示不超过2n k 的最大整数，N 是自然数集。（1991年中国数学奥林匹克） 若方程或方程组中未知数的个数多于方程的个数，它们的解又限制为正整数、整数、有理数或其它类别的数，则称此方程或方程组为不定方程。不定方程联系到一些有趣的问题。竞赛中也时有所见。 例1．在等式中还原数字x,y,z.(1987全俄中学生竞赛题) 例2．解方程： 例3．求方程222220.625w x y z +++=满足条件：w x y z >>>的整数解。 （1979年湖南省中学数学竞赛题） 定理1 设,,,(,),','a b c Z a b d a a d b b d ∈===，则线性不定方程+=ax by c 有整数解的充要条件是 d c 。在有整数解的情形下，如果 x x =， y y =是一组整数解，那么该方程的一切整数解（简称通解） 可以写成 00=+',0,1,2,......='x x b t t y y a t ?=±±? -? 例 4 求方程719213x y +=的整数解。 例5 今有物，不知其数（百个以下）。三三数之，剩二；五五数之，剩三；七七数之，剩二。问物几何？（该题目出自 1600年前的《孙子算经》） “三岁孩儿七十稀，五留廿一事尤奇，七度上元重相会，寒食清明便可知。” 注：该诀出自宋朝周密，“上元”指15，“寒食清明”指105，每年冬至至次年清明正好105天。 “三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。” 注：该诀出自明朝程大位《算法统宗》。 定理2 勾股不定方程222 x y z +=满足 ()000,1x y z x y >>>=、、、，|z y 的一切整数解可表示为22 222x a b y ab z a b ?=-?=??=+? ，这里0a b >>，(),1a b =，,a b 中一个为奇数，另一个为偶数。 例6 设n N ∈，证明方程22n x y z +=有正整数解。 例7 证明不定方程444 x y z +=没有正整数解。 费马猜想：整数2n >时，方程n n n x y z += 无正整数解是数论中的一个著名的难题。1760年欧拉证 明了n = 3 的情形。1828年勒让德余狄里赫勒各自证明了n = 5的情形。1840年拉梅证明n = 7的情形。库莫尔于1844年首创“理想数论”，并利用这个工具一举证明了n 是小于100的奇素数但除去n=37,59,67的情形.1892年米利曼诺夫证明了n=37的情形。1978瓦格斯塔夫借助大型电子计算机证明了2 < n < 125000的情形。…………29岁的讲师又对此做出了重大发展，然而至今还无法宣布此猜想是一条定理。 例8 确定（并加以证明）方程22222 a b c a b ++=所有的整数解。（1976年美国竞赛题） 例9 证明方程3 3 3 3990x y z xyz ++-=只有唯一的有理数解。 例10 正整数a 与b 使得1ab +整除2 2 a b +。求证22 1 a b ab ++是某个正整数的平方。（1988年第29届 IMO ） 习题 1. 不定方程2 2 5671987m mn n -+=是否有整数解？ 2. 方程x y z n ++=有多少组正整数解？ 3. 求方程2pq qr rp pqr ++-=的整数解（,,0p q r >）。 4. 求方程3xy xz yz z y x ++=的整数解。 高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 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） 证明：对于同样的整数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年） 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.doczj.com/doc/6c5254668.html,/webhtml/project/liansaigz.shtml 选课中心地址： https://www.doczj.com/doc/6c5254668.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)
数论历届高中数学联赛真题分类汇编含详细答案
高中数学竞赛数论
全国高中数学联赛试题分类汇编-数论(1981年-2019年)
高中数学竞赛专题讲座---竞赛中的数论问题
初等数论中的几个重要定理高中数学竞赛
高中数学竞赛资料-数论部分-(1)
高中数学联赛数论专题
高一年级竞赛数学数论专题讲义：1整除
高中数学竞赛资料-数论部分
数学竞赛中的数论问题
高中竞赛数学辅导：数论重要定理
高中数学竞赛辅导-初等数论(不定方程)
近五年全国高中数学联赛选编数论
相关主题
文本预览