例9设正整数n ≥2.求全部包含n 个整数的集合A,使得A 的随意非空子集中全部元素的和不能被n+1整除.
解:设A={a 1,a 2,…,a n }是满意条件的集合.),,2,1(1n k a S k
i i k ==∑=,依题意知,对
随意k=1,2,…,n 都有n+1∤S k ,且随意S k , S j (k ≠j)都有S k ≢S j (modn+1),所以,{S k }包含了modn+1的全部非零剩余,因对1≤i ≤n,整数a i ,S 2,S 3,…,S n 也包含了mod(n+1)的全部非零剩余,所以, a 1=S 1≡a i (modn+1),即A 中随意a i ≡a 1(modn+1).所以,对随意1≤k ≤n, a 1+a 2+…+a k ≡k a 1(modn+1).且k a 1≢0(modn+1),从而(a 1,n+1)=1.
取a 1=a 得集合A={a +k i (n+1)|k i ∈Z, 1≤i ≤n,a ∈Z,且(a ,n+1)=1}为所求. 例10对随意正整数n,用S(n)表示集合{1,2,…,n}中全部及n 互质的元素之和. 证明: 2S(n)不是完全平方数;
例11求全部的奇质数p ,使得.
例12求全部质数p ,使得212221
3)()()(|-+++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)=.证明:存在两个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!≡(modn!) ①, 另一方面,我们有
∑a a S )(=)!(mod 02)1(!])!1[(1
1111n k n n j n k a k a k n i i n i n j i
n i a i i a n i i i ≡+=-==∑∑∑∑∑∑∑===== ②. 由①∑a a S )(≡2
!n (modn!)及②∑a a S )(≡0(modn!)(因n 为奇数)冲突!故原命题成立.
例14m,n 为正整数,且m 为奇数,(m,2n -1)=1.证明:m|.
证明:因1,2,…,m 构成modm 的完系,(m,2)=1,所以2,4,…,2m 也构成 modm 的完系,所以)(mod )2(11m k k m k n m k n ∑∑==≡即)(mod 0)12(1m k m
k n n
≡-∑=. 因(m,2n -1)=1,所以.得证.
例15x ∈(0,1),设y ∈(0,1)且对随意正整数n ，y 的小数点后第n 位数字是x 的小数点后第2n 位数字.证明:假设x 是有理数,那么y 也是有理数.
例16设A={a 1,a 2,…,a φ(n)}是模n 2≡1(modn)在A 中解的个数为N,求证:
a 1a 2…a φ(n)≡2
)1(N -(modn).
同余方程及同余方程组
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)叫做①的一个解.
假设a 1(modm),a 2(modm)均为方程①的解,且a 1,a 2对模m 不同余,就称它们是方程①的不同解.由此可见,只需在模m 的任一组完系中解方程①即可.
例1解方程2x 2+x -1≡0(mod 7).
解:取mod7的完系:-3, -2,-1,0,1,2,3,干脆验算知x ≡-3(modm)是解. 例2求方程4x 2+27x -12≡0(mod 15).
解:取mod15的完系:-7, -6,…,-1,0,1,…,7,干脆验算知x ≡-6,3(modm)是解.
设m ∤a ,那么a x ≡b(modm),叫模m 的一次同余方程.
定理1当(a ,m)=1时,方程a x ≡b(modm)必有解,且解数为1.
证明:因当(a ,m)=1时,x 及a x 同时遍历模m 的完系,所以,有且仅有一个x 使得 a x ≡b(modm).即x ≡a -1b(modm).
定理2方程a x ≡b(modm)有解⇔(a ,m)|b,且有解时其解数为(a ,m),及假设x 0是
一个特解,那么它的(a ,m)个解是1),(,,1,0),(m od )
,(0-=+
≡m a t m t m a m x x . 例3解方程6x ≡10(mod8). 解:因(6,8)=2,且-1是一个特解,所以,方程6x ≡10(mod8)的解为:
1,0),8(mod 41=+-≡t t x 即)8(mod 3,1-≡x .
例4解方程12x ≡6(mod9).
因(12,9)=3,且-1是一个特解,所以,方程12x ≡6(mod9)的解为:
2,1,0),8(mod 31=+-≡t t x 即)8(mod 5,2,1，-≡x .
3.同余方程组
定义3给定正整数m 1,m 2,…,m k 和整系数多项式f 1(x),f 2(x),…,f k (x),那么同余式组
②,叫做同余方程组.假设x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,
那么x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.其中m =[m 1,m 2,…,m k ].
例5解方程组.
解:由例3知6x ≡10(mod8)的解是)8(mod 3,1-≡x .所以,原解方程组⇔ 或或)56(mod 3,31)56(mod 3≡⇔≡x x .
中国剩余定理:设K ≥2,而m 1,m 2,…,m k 是K 个两两互质的正整数，令 M=m 1m 2…m k =m 1M 1=m 2M 2=…=m k M k ，那么对随意整数a 1,a 2,…,a k 以下同余式组： ③的正整数解是x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM).
其中M j -1满意M j M j -1≡1(modm j )(1≤j ≤k),即M j 对模m j 的逆.
证明:(1)对1≤j ≤k ,因m j |M i (i ≠j) ,m j |M ,所以x ≡a j M j M j -1≡a j (modm j ).
(2)设x,y 都是同余式组的解,即x ≡a j (modm j ),y ≡a j (modm j )(1≤j ≤k),
那么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“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何〞.
解:设物数x,那么有,这里m 1=3,m 2=5,m 3=7,M=3×5×7=105,所以,
35×35-1≡2×35-1≡1(mod3)⇔35-1≡2(mod3),
21×21-1≡21-1≡1(mod5)⇔21-1≡1(mod3),
15×15-1≡15-1≡1(mod7)⇔15-1≡1(mod3),所以,同余方程组的解为:
)105(mod 23233115212132352≡=⨯⨯+⨯⨯+⨯⨯≡x ,即x=105k+23(k ∈N). 例7有兵一队,假设分别列5,6,7,11行纵队,那么末行人数分别为1,5,4,10.求兵数.
解:设兵数x,那么,其中m 1=5,m 2=6,m 3=7,m 4=11,M=2310,
462×462-1≡2×462-1≡1(mod5)⇔462-1≡3(mod5),
385×385-1≡385-1≡1(mod6)⇔385-1≡1(mod6),
330×330-1≡330-1≡1(mod7)⇔330-1≡1(mod7),
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 使得,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).
例9证明:对随意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当然也不是素数).
证明∈N *,取两组不同的素
数p 1,p 2,…,p n 及q 1,q 2,…,q n ,那么由剩余定理知存在m ∈N *,使得
同时成立.于是,n 个连续正整数m+1, m+2,…,m+n 中,每一个数都有两个不同的素因子.故结论成立.
例10证明:存在一个含有N(≥2)个正整数的集合A,使得A 中随意两个数都互质,且A 中随意k(k ≥2)个数的和都是合数.
例11证明:存在一个由正整数组成的递增数列{a n },使得对随意k ∈N *,数列 {k +a n }中都至多有有限项为素数.
证明:用p 1,p 2,p 3,…a 1=2,a 2为合适
且大于a 1的最小正整数a 2=8,取a 3合适且大于a 2的最小正整数a 2=38.假定a 1,a 2,…,a n 都已确定,那么取a n+1合适且大于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,合适且r>1,2得r=3). 取这样的r,使得r>t 且r>},,,m ax {21m a a a ,令a m+1=r, a m+2=t,那么这样得到的数列{a n }满意要求.
例13证明:存在一个n ∈N *,使得对随意整数k,整数k 2+k+n 没有小于2021的质因数.
例14证明:存在k ∈N *, 使得对随意n ∈N *,数2n k+1都是合数.
例15设m ∈N *,n ∈Z,证明:数2n 可以表为两个及m 互素的整数之和.
高中数学竞赛中数论问题的常用方法
高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 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为互不相
高中数学竞赛数论
高中数学竞赛 数论 剩余类及剩余系 (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-≤≤= 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里. (ⅲ)对随意a 、b ∈Z ，那么a 、b ∈K r ⇔a ≡b(modm). (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 为奇数时,21,,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),那么有
四川省成都七中高中数学竞赛数论专题讲义及详解：1整除
高一竞赛数论专题 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 的所有可能取值. 6.证明：正整数M 是完全平方数的充要条件是对于任意正整数n ,22(1),(2),,M M M M +-+- 2()M n M +-中至少有一项可以被n 整除.
高中数学竞赛 数论部分
初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894 年首届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明2131n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++L 能整除123n ???L （1956年上海首届数学竞赛第一题） （3） 证明：3231122 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题，占% 。
这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()21 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 的方程22229x 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 的值为
高中数学竞赛——数论
高中数学竞赛 数论 剩余类与剩余系 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的既约剩余系,
高中数学联赛真题分类汇编—初等数论
高中数学联赛真题汇编——初等数论 （1978T7）证明：当n 、k 都是给定的正整数，且n >2，k >2时，n (n －1)k － 1可以写成n 个连续偶数的和． 解：设开始的一个偶数为2m ，则此n 个连续偶数的和为 (2m +…+2m +2n －2)×n ÷2=n (2m +n －1)． 令n (n －1)k － 1= n (2m +n －1)，则(n －1)k － 1－(n －1)=2m ． 无论n 为偶数还是奇数，(n －1)k －1－(n －1)均为偶数，故m=12[(n －1)k － 1－(n －1)]为整数． ∴ 从(n －1)k － 1－(n －1)开始的连续n 个偶数的和等于n (n －1)k － 1．由于n 、k 给定，故(n －1)k － 1－(n －1)确定．故证 （1979二试5）在正整数上定义一个函数f (n )如下：当n 为偶数时，f (n )= n 2 ，当n 为奇数时， f (n )=n +3， 1° 证明：对任何一个正整数m ，数列a 0=m ，a 1=f (a 0)，…，a n =f (a n －1)，…中总有一项为1或3． 2° 在全部正整数中，哪些m 使上述数列必然出现“3”？哪些m 使上述数列必然出现“1”？ 证明：1°，当a n >3时，若a n 为偶数，则a n +1=a n 2高中数学竞赛讲义-高斯函数
§28高斯函数 数论函数][x y =，称为高斯函数，又称取整函数. 它是数学竞赛热点之一. 定义一：对任意实数][,x x 是不超过x 的最大整数，称][x 为x 的整数部分.与它相伴随的是小数部分函数].[}{},{x x x x y -== 由][x 、}{x 的定义不难得到如下性质： （1）][x y =的定义域为R ，值域为Z ；}{x y =的定义域为R ，值域为)1,0[ （2）对任意实数x ，都有1}{0},{][<≤+=x x x x 且. （3）对任意实数x ，都有x x x x x x ≤<-+<≤][1,1][][. （4）][x y =是不减函数，即若21x x ≤则][][21x x ≤，其图像如图I －4－5－1； }{x y =是以1为周期的周期函数，如图I －4－5－2. 图Ⅰ—4—5—1 图Ⅰ—4—5—2 （5）}{}{];[][x n x x n n x =++=+.其中* ∈∈N n R x ,. （6）∑∑==∈≥+≥++≥+n i i i n i i R x x x y x y x x y x y x 1 1 ],[][ };{}{}{{];[][][；特别地， ].[][ b a n b na ≥ （7）][][][y x xy ⋅≥，其中+∈R y x ,；一般有∑∏=+=∈≥n i i i n i i R x x x 1 1 ],[][ ；特别地， *∈+∈≤N n R x x x n n ,],[][. （8）]] [[ ][n x n x =，其中*∈+∈N n R x ,.
例题讲解 1．求证：,2!211 --=⇔k n n n 其中k 为某一自然数. 2．对任意的∑∞ =+* +=∈0 1].22[,K k k n S N n 计算和 3．计算和式.]503 305[ 502 的值∑==n n S 4．设M 为一正整数，问方程2 2 2 }{][x x x =-，在[1，M]中有多少个解？ 5．求方程.051][4042 的实数解=+-x x 6．.][3]3[2]2[1][][:,,n nx x x x nx N n R x ++++≥∈+∈* 证明
全国高中数学联赛数论真题整理
数论真题 1.（2003）设三角形的三边分别是整数l ，m ，n ，且l ＞m ＞n ，已知}103{}103{}103{n m l ==， 其中{x }＝x －[x ]，而[x ]表示不超过x 的最大整数．求这种三角形周长的最小值． 2.（2004）对于整数n ≥4，求出最小的整数f (n )，使得对于任何正整数m ，集合{m ，m +1，…，m+n －1}的任一个f (n )元子集中，均至少有3个两两互素的元素． 3.（2005）对每个正整数n ，定义函数⎪⎩ ⎪⎨⎧=.]}{1[,0)(不为平方数当为平方数当n n n n f （其中[x ]表示不超过x 的最大整数，]).[}{x x x -= 试求：∑=240 1)(k k f 的值. 4.（2007）设集合P ={1，2，3，4，5}，对任意k ∈P 和正整数m ，记 f (m ，k )=∑=⎥⎦⎤⎢⎣⎡++5 111i i k m ，其中[a ]表示不大于a 的最大整数。求证：对任意正整数n ，存在k ∈P 和正整数m ，使得f (m ，k )=n 。 5.（2008）已知无穷数列｛a n ｝满足，，n ＝4，5，…，求证：对任何正常数m ，存在某个正整数n ，使得m|。 6.（2009）设k ，l 是给定的两个正整数．证明：有无穷多个正整数m k ≥，使得C k m 与l 互 素． 7.(2010)设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=⎡⎤⎢⎥． 8.(2011)证明：对任意整数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 ，均有 9.(2012)试证明：集合{} 22,2,,2,n A = 满足 （１）对每个a A ∈，及b N *∈，若21b a <-，则(1)b b +一定不是2a 的倍数； （２）对每个a A ∈（其中A 表示A 在Ｎ 中的补集），且1a ≠，必存在b N *∈， 21b a <-，使(1)b b +是2a 的倍数 1231,1,3a a a ===1232n n n n a a a a ---=++n a
全国高中数学联赛数论历年真题精选
全国高中数学联赛数论历年真题精选(2014.09.01) （2013年全国高中数学联赛试题） 二、（本题满分40分）给定正整数,u v .数列{}n a 定义如下：1a u v =+，对整数1m ≥， 221 ,.m m m m a a u a a v +=+⎧⎨=+⎩ 记12m m S a a a =+++（1,2,m =）.证明：数列{}n S 中有无穷多项是完全平方数. 提示：由对称性和和谐性，求21m S +，发现21m S +和m S 之间的递推关系，为了拉近21m S +和m S 间的关系，最好是某个数列的相邻两项，于是想到212(1)1(1)1,m m m m S S S S ++-+-==，故考虑令 12n m +=，就有了21{}n S -的通项公式121()2n n S u v n --=+.于是令2*2()r ,.n u v r N =+∈ 参考答案没有给出思维过程，需要大家深入思考，去领悟问题的本质，做二试题一定要达到 看答案觉得那是自然的解答过程才算理解了。
下面给出（2）的几种证法. 证法一:令1,12,k b mx b y +=+=消去b 得12 1.k y mx +-= 由于1(2,)1,k m +=这方程必有整数解;1 02k x x t y y mt +⎧=+⎪⎨=+⎪⎩其中00,(,)t z x y ∈为方程的特解. 把最小的正整数解记为(,),x y **则12k x *+<,故21,b mx a *=<-使(1)b b +是2a 的倍数．……40分 证法二:由于1 (2 ,)1,k m +=由中国剩余定理知,同余方程组 10(mod 2) 1(mod ) k x x m m +⎧=⎨ =-⎩在区间1(0,2)k m +上有解,x b =即存在21,b a <-使(1)b b +是2a 的倍数．…………40分 证法三:由于(2,)1,m =总存在(,1),r r N r m * ∈≤-使21(mod )r m =取,t N * ∈使 1,tr k >+则21(mod )tr m = 存在1 (21)(2)0,,tr k b q m q N +=--⋅>∈使021,b a <<- 此时1,21,k m b m ++因而(1)b b +是2a 的倍数．……………40分
高中竞赛数学辅导：数论专题
数论 数论素有“数学皇后”的美称。由于其形式简单，意义明确，所用知识不多而又富于技巧性，千姿百态，灵活多样。有人曾说：“用以发现数学天才，在初等数学中再也没有比数论更好的课程了。”因此在理念的国内外数学竞赛中，几乎都离不开数论问题，使之成为竞赛数学的一大重要内容。 1. 基本内容 竞赛数学中的数论问题主要有： （1）整除性问题； （2）数性的判断（如奇偶性、互质性、质数、合数、完全平方数等）； （3）余数问题； （4）整数的分解与分拆； （5）不定方程问题； （6）与高斯函数[]x有关的问题。 有关的基本知识： 关于奇数和偶数有如下性质： 奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数. 两个数之和是奇（偶）数，则这两个数的奇偶性相反（同）. 若干个整数之和为奇数，则这些数中必有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，则这些数中若有奇数，奇数的个数必为偶数个. 奇数g奇数=奇数；奇数g偶数=偶数；偶数g偶数=偶数. 若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中至少有一个偶数. 若a是整数，则a与a有相同的奇偶性；若a、b是整数，则a b -奇偶性 +与a b 相同。 关于整数的整除性： 设,, a b c是整数，则○1a a；○2若, a b b c，则a c；○3若, a b b c，则对任意整数,m n， +. 有a bm cn
若在等式11m n i i i i a b ===∑∑中，除某一项外，其余各项都能被c 整除，则这一项也能被c 整除. 若(,)1a b =，且a bc ，则a c .若(,)1a b =，且,a b b c ，则ab c . 设p 是素数，若p ab ，则p a 或p b . 关于同余： 若0(mod )a m ≡，则m a . (mod )a b m ≡⇔,a b 分别被m 除，余数相同. 同余具有反身性:(mod )a a m ≡、对称性:若(mod )a b m ≡，则(mod )b a m ≡、传递性：若,(mod )a b b c m ≡≡，则(mod )a c m ≡. 2. 方法评析 数论问题综合性强，以极少的知识就可生出无穷的变化。因此数论问题的方法多样，技巧性高，富于创造性和灵活性。在竞赛数学中，解决数论问题的常用方法有因式分解法、估值法、调整法、构造法、反证法、奇偶分析法等等。 2.1 因式（数）分解 例1 证明无穷数列10001，100010001，……中没有素数。 证明：设1 1000100011n n a =L 1442443个，则 4484(1)41011101010=101 n n n a --=++++-L 当n 为偶数，设2n k =， 888484101(10)1101=101101101 k k n a ---=---g 所以n a 为合数。 当n 为奇数，设2+1n k =， 42+1221221422101101101==101101101 k k k n a ++--+--+g （）（）（）
高中奥林匹克数学竞赛讲座--初等数论奇数、偶数、质数、合数
高中奥林匹克数学竞赛讲座 初等数论奇数、偶数、质数、合数 知识、方法、技能 Ⅰ.整数的奇偶性 将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m （m ∈Z ），任一奇数可表为2m+1或2m －1的形式.奇、偶数具有如下性质： （1）奇数±奇数=偶数；偶数±偶数=偶数； 奇数±偶数=奇数；偶数×偶数=偶数； 奇数×偶数=偶数；奇数×奇数=奇数； （2）奇数的平方都可表为8m +1形式，偶数的平方都可表为8m 或8m +4的形式（m ∈Z ）. （3）任何一个正整数n ，都可以写成l n m 2=的形式，其中m 为非负整数，l 为奇数. 这些性质既简单又明显，然而它却能解决数学竞赛中一些难题. Ⅱ.质数与合数、算术基本定理 大于1的整数按它具有因数的情况又可分为质数与合数两类. 一个大于1的整数，如果除了1和它自身以外没有其他正因子，则称此数为质数或素数，否则，称为合数. 显然，1既不是质数也不是合数；2是最小的且是惟一的偶质数. 定理：（正整数的惟一分解定理，又叫算术基本定理）任何大于1的整数A 都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而A 可以写成标准分解式： n a n a a p p p A 2121⋅= （*）. 其中i n p p p p ,21<<< 为质数，i α为非负整数，i =1，2，…，n . 【略证】由于A 为一有限正整数，显然A 经过有限次分解可分解成若干个质数的乘积，把相同的质因子归类整理可得如（*）的形式（严格论证可由归纳法证明）.余下只需证惟一性. 设另有j m n q q q q q q q A m ,,212121<<<⋅= 其中β ββ为质数，i β为非负整数，j=1，2，…，m .由于任何一i p 必为j q 中之一，而任一j q 也必居i p 中之一，故n=m .又因 ),,2,1(,,2121n i q p q q q p p p i i n n ==<<<<<则有，再者，若对某个i ，i i βα≠（不妨设 i i βα>） ，用i i p β除等式n n n a n a a p p p p p p βββ 21122121⋅=两端得： .11111111n i i n i i n i i n i p p p p p p p ββββεβαα +-+--⋅= 此式显然不成立（因左端是i p 的倍数，而右端不是）.故i i βα=对一切i =1，2，…，n 均成立.惟一性得证.
高中数学竞赛专题讲座竞赛中的数论问题
竞赛中的数论问题的思索方法 一. 条件的增设 对于一道数论命题，我们往往要首先解除字母取零值或字母取相等值等“平凡〞的状况，这样，利用字母的对称性等条件，往往可以就字母间的大小依次、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。 1. 大小依次条件 及实数范围不同，假设整数x ，y 有大小依次x m ,而令1，n >u 1≥ 1，得-2(m -1mu 1)(22112=--u mu m 。同理，又可令 u 1+ u 2，m >u 2≥1。如此接着下去 将得1= 1，而11+-+=i i i u u u ，i ≤k 。故n m u u u u k k ,,,,,, 121 +是不大于 1981的裴波那契数，故987，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 b a ，从而只有1，2，1。 2. 整除性条件 对于整数x ，y 而言，我们可以讨论其整除关系：假设，那么可令；假设x ∤y ，那么可令，0高中数学竞赛资料
高中数学竞赛资料 初等数论简介绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。1．请看下面的例子：证明：对于同样的整数x和y，表达式2x+3y 和9x+5y能同时被整除。(1894年首届匈牙利数学竞赛第一题) ①设n?Z，证明132n?1是168的倍数。 ②具有什么性质的自然数n，能使1?2?3???n能整除1?2?3??n？证明：n?3321n?n?1对于任何正整数n都是整数，且用3除时余2。14n?3届数学竞赛第一题）证明：对任何自然数n，分数令(a,b,?,g)和[a,b,?,g]分别表示正整数a,b,?,g的最大公因数和最小公倍数，试证：2a,b,c???a,b,c?? a,b?b,c?c,aa,bb,cc,a????????????2这些例子说明历来数论题在命题者心目中首当其冲。2.再看以下统计数字：世界
上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占%。世界上规模最大、规格最高的IMO的前20届120道试题中有数论13题，占% 。这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题：(1)方程x3?6x2?5x?y3?y?2的整数解(x,y)的个数是A、0 B、1C、3D、无穷多已知a,b都是正整数，试问关于x的方程x?abx?如果有，请把它们求出来；如果没有，请给出证明。21?a?b??0是否有两个整数解？ 2 1 ①是否存在正整数m,n，使得m(m?2)?n(n?1)？②设k(k?3)是给定的正整数，是否存在正整数m,n，使得m(m?k)?n(n?1)？关于x,y的方程x2?xy?2y2?29的整数解(x,y)得组数为A、2B、3C、4
高中数学联赛初等数论专题练习(带答案详解版)-
高中数学联赛初等数论专题练习（详解版)学校 :___________姓名： ___________班级： ___________考号： ___________ 一、单选题 1．高斯是德国著名的数学家，近代数学奠基者之一，享有“数学王子”的称号，用其名字命名的“高斯函数”为：设 x R ，用 x 表示不超过x 的最大整数，则y x 称为高斯函数，例如：0.51， 1.5 1 ，已知函数 f ( x)14x 3 2x4（0x 2）， 2 则函数 y f ( x)的值域为（） A ．－ 13 B ．1,0,1C．{- 1,0,1,2} D ．0,1,2 2 ， 2 2．设 [ x] 表示不超过x的最大整数（如[2] 2 ， [ 5 ]1），对于给定的 n N *，定义 4 C n x n(n1)(n[ x]1)， x1,；当 x3,4 时，函数C8x的值域是（） x( x1)( x[ x]1) A ．12,58B．14,56 C．12,58D．14,56 3．用x表示x的整数部分，即x表示不超过 x 的最大整数，例如： 22, 2.32, 2.3，设函数 h x ln x x21，则函数3 f (x)h(x)h( x)的值域为（） A ．0 B ．1,0,1C．1,0 D ．2,0 4．已知n是正整数，则下列数中一定能整除2n32 25的是（） A ．6 B ．3C． 4 D ． 5 5．已知直角三角形的三边长都是整数，且其面积与周长在数值上相等. 那么，这样的直角三角形有（）个 . A ．0 B ．1C． 2 D ． 3 6．十八世纪，函数y [ x] （[ x]表示不超过 x 的最大整数）被“” 数学王子高斯采用，因 此得名为高斯函数，结合定义的表述，人们习惯称为“” 取整函数，根据上述定义，则方 程 2019x2[ x]20200 的所有实数根的个数为（）
高中数学联赛之历年真题汇编(1981-2020)专题29初等数论(解析版)
备战2021年高中数学联赛之历年真题汇编(1981-2020) 专题29初等数论 1.【2020高中数学联赛E卷(第02试)】设Gb为不超过12的正整数,满足:存在常数C,使得α∏+b∏+9≡C( modl3)对任意正整数H成立-求所有满足条件的有序数对(α, b). 【答案】(1,1),(4,4),(10,10),(12,12) 【解析】解法1：由条件知,对任虑正整数几有沪+ b n+9≡ a n+2 + b n÷12(modl3). ① 注意到13为素数,α上均与13互素,由费马小定理知H ≡b2≡I(ZnOdI3). 因此在①中取沪12,化简得1 + b9≡a2+ l(modl3),故b° ≡ α3(modl3). 代入①,得N + a3b n≡απ÷3 + &π+12≡ απ÷3 + ∂π(modl3), 即(刃一∂n)(l 一α3) ≡ 0(modl3). ② 分两种情况讨论. (i )若疋≡ 1 (modi3),则沪≡ a3b3≡ b l2≡l(modl3), 又{12∙∙∙J2},经检验可知a f bE{1Λ9}. 此时“ + b n+9≡ a n+∂n(modl3).由条件知α + b ≡ a2 + b3≡2(mod 13), 从而只能是π=δ=l. 经检验,当(α, b) =(1,1)时,对任总正整数n, J +沪+9模U余2为常数,满足条件• (ii)‰3N l(modl3),则由②知,对任意正整数n,Wαn≡ ∂n(modl3). 特别地，α ≡ &(modl3),故a=b.所以a? ≡ b9=α9(modl3), 即左(“ 一l)(α3+ 1) ≡ 0(mod 13), ‰3≡ -I(modl3).通过检验α ≡ ±‰±2,-j±6(modl3),可知α = 4,10,12. 经检验,当(α,b) = (4M(IO40),(12J2)时,对任盘正整数”， 有"+ b n^9= a n +αn÷9= a n(l + (α3)3) ≡ 0(modi3), 满足条件. 综上,所求的有序数对(α, b)为(1,1), (4,4), (10,10), (12,12). 解法2:由条件知,对任盘正整数",有("+ ∂n+9)(αn+2+ fa n÷11) ≡ (αn÷1 + ∂n+10)≡(modl3), 化简得αn∂π÷11 + aπ÷2b n+9≡ 2a n÷1 + ∂π÷10(modl3), 即a n b n^(a一b)2≡0(modl3). 由于13 为素数,a,b∈ {12…,12},故13Ka 一b)：,进而a = b.
【高中数学竞赛专题大全】 竞赛专题15 初等数论(50题竞赛真题强化训练)解析版+原卷版
【高中数学竞赛专题大全】 竞赛专题15 初等数论 （50题竞赛真题强化训练） 一、填空题 1．（2020·浙江·高三竞赛）将1~2020的数字按顺时针方向围成一个圆圈，然后从1开始，按顺时针依次隔一个数拿走，即拿走1，3，5，…，这个过程一直进行下去，直到剩下最后一个数字，则最后剩下的数字是___________. 【答案】1992. 【解析】 【详解】 在第一轮中，从1开始到拿走1991，共取走996个数，此时余下1024个数， 1991后一项偶数为1992，此后共取10次，余下的数为1992， 故答案为:1992. 2．（2021·全国·高三竞赛）关于x 、y 的方程1111 2007 x 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 =≥，则2 11513133n n a a ---+， 故()2 1512n a -++，这不可能，因为()2 12n a ++除以5的余数为1,3， 所以5P A ∈-．集合P A -的最小元素为5． 故答案为：5. 4．（2021·全国·高三竞赛）质数p 和正整数m 满足32(2)1p m p m p ++=++，则 p m +=___________. 【答案】7 【解析】 【详解】 由()22 1(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 有______种可能的取值情况.
