当前位置:文档之家› 竞赛数学中的初等数论(精华版)

竞赛数学中的初等数论(精华版)

竞赛数学中的初等数论(精华版)
竞赛数学中的初等数论(精华版)

《竞赛数学中的初等数论》

贾广素编著

2006-8-21

序 言

数论是竞赛数学中最重要的一部分,特别是在1991年,IMO 在中国举行,国际上戏称那一年为数论年,因为6道IMO 试题中有5道与数论有关。

数论的魅力在于它可以适合小孩到老头,只要有算术基础的人均可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想,当然,这一谣言最终被澄清了。可是这也说明了最难的数论问题,适合于任何人去研究。

初等数论最基础的理论在于整除,由它可以演化出许多数论定理。做数论题,其实只要整除理论即可,然而要很快地解决数论问题,则要我们多见识,以及学习大量的解题技巧。这里我们介绍一下数论中必需的一个内容:对于N r q N b a ∈?∈?,,,,满足r bq a +=,其中b r <≤0。 除了在题目上选择我们努力做到精挑细选,在内容的安排上我们也尽量做到讲解详尽,明白。相信通过对本书学习,您可以对数论有一个大致的了解。希望我们共同学习,相互交流,在学习交流中,共同提高。

编者:贾广素

2006-8-21于山东济宁

第一节 整数的p 进位制及其应用

正整数有无穷多个,为了用有限个数字符号表示出无限多个正整数,人们发明了进位制,

这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系,近几年来,国内与

国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理

数列问题等等。在本节,我们着重介绍进位制及其广泛的应用。

基础知识

给定一个m 位的正整数A ,其各位上的数字分别记为021,,,a a a m m --,则此数可以简记为:021a a a A m m --=(其中01≠-m a )。

由于我们所研究的整数通常是十进制的,因此A 可以表示成10的1-m 次多项式,即

012211101010a a a a A m m m m +?++?+?=---- ,其中1,,2,1},9,,2,1,0{-=∈m i a i 且

01≠-m a ,像这种10的多项式表示的数常常简记为10021)(a a a A m m --=。在我们的日常

生活中,通常将下标10省略不写,并且连括号也不用,记作021a a a A m m --=,以后我们

所讲述的数字,若没有指明记数式的基,我们都认为它是十进制的数字。但是随着计算机的

普及,整数的表示除了用十进制外,还常常用二进制、八进制甚至十六进制来表示。特别是

现代社会人们越来越显示出对二进制的兴趣,究其原因,主要是二进制只使用0与1这两种

数学符号,可以分别表示两种对立状态、或对立的性质、或对立的判断,所以二进制除了是

一种记数方法以外,它还是一种十分有效的数学工具,可以用来解决许多数学问题。

为了具备一般性,我们给出正整数A 的p 进制表示:

012211a p a p a p a A m m m m +?++?+?=---- ,其中1,,2,1},1,,2,1,0{-=-∈m i p a i 且

01≠-m a 。而m 仍然为十进制数字,简记为p m m a a a A )(021 --=。

典例分析

例1.将一个十进制数字2004(若没有指明,我们也认为是十进制的数字)转化成二进制与

八进制,并将其表示成多项式形式。

分析与解答

分析:用2作为除数(若化为p 进位制就以p 作为除数),除2004商1002,余数为0;再

用2作为除数,除1002商501余数为0;如此继续下去,起到商为0为止。所得的各次余

数按从左到右的顺序排列出来,便得到所化出的二进位制的数。

解:

故210)01111101010()2004(=,246789104212121212121214102?+?+?+?+?+?+?=+?;

同理,有810)3274()2004(=,48782834102234+?+?+?=+?。

处理与数字有关的问题,通常利用定义建立不定方程来求解。

例2.求满足3

)(c b a abc ++=的所有三位数abc 。 (1988年上海市竞赛试题) 解:由于999100≤≤abc ,则999)(1003≤++≤c b a ,从而95≤++≤c b a ;

当5=++c b a 时,33)521(1255++≠=;

当6=++c b a 时,33)612(2166++≠=;

当7=++c b a 时,33)343(3437++≠=;

当8=++c b a 时,33)215(5128++==;

当9=++c b a 时,33)927(7299++≠=;

于是所求的三位数只有512。

例3.一个四位数,它的个位数字与百位数字相同。如果将这个四位数的数字顺序颠倒过来

(即个位数字与千位数字互换,十位数字与百位数字互换),所得的新数减去原数,所得的

差为7812,求原来的四位数。

(1979年云南省竞赛题)

解:设该数的千位数字、百位数字、十位数字分别为z y x ,,,则

原数y z y x +++=10101023 ①

颠倒后的新数x y z y +++=10101023 ②

由②-①得7812=)(90)(999y z x y -+-

即)()(10)(10)(10)(1118682x y y z x y y z x y -+-+-=-+-= ③

比较③式两端百位、十位、个位数字得6,8=-=-x z x y

由于原四位数的千位数字x 不能为0,所以1≥x ,从而98≥+=x y ,又显然百位数字9≤y ,所以76,1,9=+===x z x y 。所以所求的原四位数为1979。

例4.递增数列1,3,4,9,10,12,13,……是由一些正整数组成,它们或是3的幂,或是若

个不同的3的幂之和,求该数列的第100项。 (第4届美国数学邀请赛试题)

解:将已知数列写成3的方幂形式:

,333,33,33,3,33,3,30127126025240131201++=+=+==+===a a a a a a a

易发现其项数恰好是自然数列对应形式的二进制表示:

即 ,2227,226,225,24,223,22,2101220220110++=+=+==+===

由于100=2562222)1100100(++=

所以原数列的第100项为981333256=++。

例5.1987可以在b 进制中写成三位数xyz ,如果7891+++=++z y x ,试确定所有可

能的z y x ,,,和b 。 (1987年加拿大数学竞赛试题)

解:易知25,19872=++=z y x xb ,从而162)1()1(2=-+-b y b x ,

即109321962])1)[(1(2??==++-y x b b ,

由10>b 知91>-b 。由119622-≥b 知451963<≤b 故4519<-

又因为1093219622??=有12个正约数,分别为1,2,3,6,

9,18,109,218,327,654,981,1962,所以181=-b ,从而19=b 。

又由1119919519872+?+?=知.11,9,5===z y x

例6.设n 是五位数(第一个数码不是零),m 是由n 取消它的中间一个数码后所成的四位

数,试确定一切n 使得m

n 是整数。 (第3届加拿大数学竞赛试题) 解:设v u z y x xyzuv n +?+?+?+?==10101010234,其中}9,,2,1,0{,,,, ∈v u z y x 且

1≥x ;v u y x xyuv m +?+?+?==10101023; 而m

n k =是整数,可证n m <9,即<+?+?+?)101010(923v u y x v u z y x +?+?+?+?10101010234 即z y x v u 223101010880++<+,这显然是成立的;

又可证m n 11<,即v u z y x +?+?+?+?10101010234<)101010(1123v u y x +?+?+?

即v u y x z 10101010102232+++<,这显然也是正确的。

于是m n m 119<<,即119<

于是m n 10=,即v u z y x +?+?+?+?10101010234=)101010(1023v u y x +?+?+?

即)10(9990102

v v u z +=+=?,而z 210|9但3 102知t t z (9=为正整数) 从而v u t +=?10102,显然0===v u t ,因而推得31000?==N xyz n 其中9910≤≤N 。

例7.若}100,,2,1{ ∈n 且n 是其各位数字和的倍数,这样的n 有多少个?

(2004年南昌竞赛试题)

解:(1)若n 为个位数字时,显然适合,这种情况共有9种;

(2)若n 为100时,也适合;

(3)若n 为二位数时,不妨设ab n =,则b a n +=10,由题意得)10(|)(b b a ++ 即

Z b a b a ∈++10即Z b

a a ∈+9也就是a

b a 9|)(+; 若0=b 显然适合,此种情况共有9种; 若0≠b ,则由a b a >+,故)(|3b a +

若9|)(b a +,则显然可以,此时共有2+8=10个;

若(b a +)9,则6=+b a 或12=+b a ,这样的数共有24,42,48,84共4个;

综上所述,共有9+1+9+10+4=33个。

例8.如果一个正整数n 在三进制下表示的各数字之和可以被3整除,那么我们称n 为“好

的”,则前2005个“好的”正整数之和是多少?(2005年中国奥林匹克协作体夏令营试题)

解:首先考虑“好的”非负整数,考察如下两个引理:

引理1.在3个连续非负整数23,13,3++n n n (n 是非负整数)中,有且仅有1个是“好的”。

证明:在这三个非负整数的三进制表示中,0,1,2各在最后一位出现一次,其作各位数字

相同,于是三个数各位数字之和是三个连续的正整数,其中有且仅有一个能被3整除(即“好

的”),引理1得证。

引理2.在9个连续非负整数89,19,9++n n n (n 是非负整数)中,有且仅有3个是“好

的”。把这3个“好的”非负整数化成三进制,0,1,2恰好在这三个三进制数的最后一位各

出现一次。

证明:由引理1不难得知在9个连续非负整数89,19,9++n n n (n 是非负整数)中,有

且仅有3个是“好的”。

另一方面,在这三个“好的”非负整数的三进制表示中,最高位与倒数第三位完全相同,倒

数第二位分别取0,1,2。若它使它们成为“好的”非负整数,则最后一位不相同,引理2

得证。

将所有“好的”非负整数按从小到大的顺序排成一列,设第2004个“好的”非负整数为m ,

根据引理1,得3200432003?<≤?m ,即60126009<≤m 。

设前m 个“好的”正整数之和为m S ,由于前2003个“好的”正整数之和等于前2004个“好

的”非负整数之和。因此602302220043)2003210(2003=+?+++= S ;

又因为310)22020201()6013(=和310)22020210()6015(=都是“好的”正整数。因此前

2005年“好的”正整数之和是:

60350506015601320032005=++=S S 。

第二节 整数的性质及其应用(1)

基础知识

整数的性质有很多,这里我们着重讨论整数的整除性、整数的奇偶性,质数与合数、完

全平方数及整数的尾数等几个方面的应用。

1.整除的概念及其性质

在高中数学竞赛中如果不加特殊说明,我们所涉及的数都是整数,所采用的字母也表示整数。

定义:设b a ,是给定的数,0≠b ,若存在整数c ,使得bc a =则称b 整除a ,记作a b |,

并称b 是a 的一个约数(因子),称a 是b 的一个倍数,如果不存在上述c ,则称b 不能整除a

记作b a 。

由整除的定义,容易推出以下性质:

(1)若c b |且a c |,则a b |(传递性质);

(2)若a b |且c b |,则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。若

反复运用这一性质,易知a b |及c b |,则对于任意的整数v u ,有)(|cv au b ±。更一般,若

n a a a ,,,21 都是b 的倍数,则)(|21n a a a b +++ 。或着i b a |,则∑=n

i i i b c a 1|其中

n i Z c i ,,2,1, =∈;

(3)若a b |,则或者0=a ,或者||||b a ≥,因此若a b |且b a |,则b a ±=;

(4)b a ,互质,若c b c a |,|,则c ab |;

(5)p 是质数,若n a a a p 21|,则p 能整除n a a a ,,,21 中的某一个;特别地,若p 是

质数,若n

a p |,则a p |;

(6)(带余除法)设b a ,为整数,0>b ,则存在整数q 和r ,使得r bq a +=,其中b r <≤0,并且q 和r 由上述条件唯一确定;整数q 被称为a 被b 除得的(不完全)商,数r

称为a 被b 除得的余数。注意:r 共有b 种可能的取值:0,1,……,1-b 。若0=r ,即为

a 被

b 整除的情形;

易知,带余除法中的商实际上为??????b a (不超过b

a

的最大整数),而带余除法的核心是关于余数r 的不等式:b r <≤0。证明a b |的基本手法是将a 分解为b 与一个整数之积,在

较为初级的问题中,这种数的分解常通过在一些代数式的分解中取特殊值而产生,下面两个

分解式在这类论证中应用很多,见例1、例2。

若n 是正整数,则))((1221----++++-=-n n n n n n y xy y x x

y x y x ; 若n 是正奇数,则))((1221----+-+-+=+n n n n n n y xy y x x

y x y x ;(在上式中用y -代y )

(7)如果在等式∑∑===m k k n i i

b a 11中取去某一项外,其余各项均为

c 的倍数,则这一项也是c 的

倍数;

(8)n 个连续整数中,有且只有一个是n 的倍数;

(9)任何n 个连续的整数之积一定是n!的倍数,特别地,三个连续的正整数之积能被6

整除;

2.奇数、偶数有如下性质:

(1)奇数±奇数=偶数,偶数±偶数=偶数,奇数±偶数=奇数,偶数?偶数=偶数,奇数?

偶数=偶数,奇数?奇数=奇数;即任意多个偶数的和、差、积仍为偶数,奇数个奇数的和、

差仍为奇数,偶数个奇数的和、差为偶数,奇数与偶数的和为奇数,和为偶数;

(2)奇数的平方都可以表示成18+m 的形式,偶数的平方可以表示为m 8或48+m 的形式;

(3)任何一个正整数n ,都可以写成l n m

2=的形式,其中m 为负整数,l 为奇数。

(4)若有限个整数之积为奇数,则其中每个整数都是奇数;若有限个整数之积为偶数,则

这些整数中至少有一个是偶数;两个整数的和与差具有相同的奇偶性;偶数的平方根若是整

数,它必为偶数。

3.完全平方数及其性质

能表示为某整数的平方的数称为完全平方数,简称平方数。平方数有以下性质与结论:

(1)平方数的个位数字只可能是0,1,4,5,6,9;

(2)偶数的平方数是4的倍数,奇数的平方数被8除余1,即任何平方数被4除的余数

只有可能是0或1;

(3)奇数平方的十位数字是偶数;

(4)十位数字是奇数的平方数的个位数一定是6;

(5)不能被3整除的数的平方被3除余1,能被3整数的数的平方能被3整除。因而,

平方数被9也合乎的余数为0,1,4,7,且此平方数的各位数字的和被9除的余数也只能是0,1,

4,7;

(6)平方数的约数的个数为奇数;

(7)任何四个连续整数的乘积加1,必定是一个平方数。

(8)设正整数b a ,之积是一个正整数的k 次方幂(2≥k ),若(b a ,)=1,则b a ,都

是整数的k 次方幂。一般地,设正整数c b a ,,, 之积是一个正整数的k 次方幂(2≥k ),

若c b a ,,, 两两互素,则c b a ,,, 都是正整数的k 次方幂。

4.整数的尾数及其性质

整数a 的个位数也称为整数a 的尾数,并记为)(a G 。)(a G 也称为尾数函数,尾数函数

具有以下性质:

(1)=))((a G G )(a G ;(2))(21n a a a G +++ =)]()()([21n a G a G a G G +++ ;

(3)=???)(21n a a a G )]()()([21n a G a G a G G ??? ;(4)0)10(=a G ;

)()10(b G b a G =+;

(5)若c b a 10=-,则)()(b G a G =;(6)+∈=N k a a G a

G k ,),()(44; (7)++∈<<≥=N r k a r k a G a G r r k ,,,40,0),()(4;

(8)?????=同为奇数时当同时为偶数时为奇数或为偶数,当是偶数为奇数,当212121421,),(,),(),()(121b b a G b b b b a G b b a G a G b b n b b

5.整数整除性的一些数码特征(即常见结论)

(1)若一个整数的未位数字能被2(或5)整除,则这个数能被2(或5)整除,否则不能;

(2)一个整数的数码之和能被3(或9)整除,则这个数能被3(或9)整除,否则不能;

(3)若一个整数的未两位数字能被4(或25)整除,则这个数能被4(或25)整除,否则

不能;

(4)若一个整数的未三位数字能被8(或125)整除,则这个数能被8(或125)整除,否则

不能;

(5)若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数,则这个数能被

11整除,否则不能。

6.质数与合数及其性质

1.正整数分为三类:(1)单位数1;(2)质数(素数):一个大于1的正整数,如果它

的因数只有1和它本身,则称为质(素)数;(3)如果一个自然数包含有大于1而小于其本

身的因子,则称这个自然数为合数。

2.有关质(素)数的一些性质

(1)若1,>∈a Z a ,则a 的除1以外的最小正因数q 是一个质(素)数。如果a q ≠,则a q ≤

(2)若p 是质(素)数,a 为任一整数,则必有a p |或(p a ,)=1;

(3)设n a a a ,,,21 为n 个整数,p 为质(素)数,且n a a a p 21|,则p 必整除某个i a (n i ≤≤1);

(4)(算术基本定理)任何一个大于1的正整数a ,能唯一地表示成质(素)因数的乘积(不

计较因数的排列顺序);

(5)任何大于1的整数a 能唯一地写成k i p p p a k a k a a ,,,2,1,2121 == ① 的形式,其中i p 为质(素)数()(j i p p j i <<)。上式叫做整数a 的标准分解式;

(6)若a 的标准分解式为①,a 的正因数的个数记为)(a f ,则)1()1)(1()(21+++=k a a a a f 。 典例分析

例1.证明:10010

2000

个被1001整除。 证明:]110)10()10)[(110(1)10(11010013665366633667320010

2000+-+-+=+=+=

个 所以)1001(1103

=+整除100102000

个。 例2.对正整数n ,记)(n S 为n 的十进制表示中数码之和。证明:n |9的充要条件是)(|9n S 。

证明:设011010a a a n k k +?++?= (这里90≤≤i a ,且0≠k a ),则n a a a n S +++= 10)(,

于是有=-)(n S n )110()110(1-?++-?a a k k ①

对于k i ≤≤1,知)110(|9-i

,故①式右端k 个加项中的每一个都是9的倍数,从而由整

除的性质可知它们的和也能被9整除,即))((|9n S n -。由此可易推出结论的两个方面。

例3.设1≥k 是一个奇数,证明L 对于任意正整数n ,数k k k n +++ 21不能被2+n 整除。

证明:1=n 时,结论显然成立。设2≥n ,记所说的和为A ,则: )2())1(3()2(22k k k k k k n n n A +++-++++= 。

由k 是正奇数,从而结于每一个2≥i ,数k k i n i )2(-++被2)2(+=-++n i n i 整除,

故A 2被2+n 除得余数为2,从而A 不可能被2+n 整除(注意22>+n )。

例4.设n m ,是正整数,2>m ,证明:(12-m )(12+n )。

证明:首先,当m n ≤时,易知结论成立。事实上,n m =时,结论平凡;当m n <时,结

果可由1212121-≤+≤+-m m n 推出来(注意2>m )

。 最后,m n >的情形可化为上述特殊情形:由带余除法m r r mp n <≤+=0,而0>q ,由

于122)12(12++-=+r r mq n ,从而由若n 是正整数,则))((1221----++++-=-n n n n n n y xy y x x y x y x 知

)12(|)12(--mq m ;而m r <≤0,故由上面证明了的结论知)12(-m )12(+r (注意

0=r 时结论平凡)

,从而当m n >时,也有(12-m )(12+n )。这就证明了本题的结论。 例5.设正整数d c b a ,,,满足cd ab =,证明:d c b a +++不是质(素)数。

证法一:由cd ab =,可设

n m b d c a ==其中1),(=n m 。由n m c a =意味着有理数c

a 的分子、分母约去了某个正整数u 后得既约分数n m ,因此,nu c mu a ==, ① 同理,存在正整数v 使得mv d nv

b ==, ②

因此,d c b a +++=))((v u n m ++是两个大于1的整数之积,从而不是素数。

注:若正整数d c b a ,,,适合cd ab =,则d c b a ,,,可分解为①及②的形式,这一结果在某些

问题的解决中很有作用。

证法二:由cd ab =,得a cd b =,因此a

d a c a d c a cd a d c b a ))((++=+++=+++,因为d c b a +++是整数,故a d a c a ))((++也是整数。 若它是一个素数,设为p ,则由ap d a c a =++))(( ③

可见p 整除))((d a c a ++,从而素数p 整除c a +或d a +。不妨设p |c a +,则

p c a ≥+,结合③推出a d a ≤+,而这是不可能的(因为1≥d )

。 例6.求出有序整数对(n m ,)的个数,其中991≤≤m ,991≤≤n ,n

m n m +++3)(2

是完全平方数。 (1999年美国数学邀请赛试题)

解:由于991≤≤m ,991≤≤n 可得: n m n m +++3)(2<4)(4)(2++++n m n m 2)2(++=n m 。

又<+2)(n m n m n m +++3)(2,于是<+2)(n m n m n m +++3)(22

)2(++

若n m n m +++3)(2是完全平方数,则必有n m n m +++3)(2=2)1(++n m 。

然而n m n m +++3)(2=2)1(++n m 1+-+m n ,于是必有01=+-m n ,即1-=n m ,

此时99,,3,2 =n ,98,,2,1 =m 。所以所求的有序整数对(n m ,)共有98对: )99,98(,),4,3(),3,2(),2,1(),( =n m 。

例7.证明:若正整数b a ,满足b b a a +=+2

232,则b a -和122++b a 都是完全平方数。

(2006年山东省第二届夏令营试题)

证法一:已知关系式即为b b a a +=+2232?222)()(2b b a b a =-+- ?(b a -)

(122++b a )=2b ① 若0==b a (或者说b a ,中有一个为0时),结论显然。

不妨设b a ≠且0≠ab ,令d b a =),(,则d b b d a a 11,==,1),(11=b a

从而b a -=d b a )(11-,将其代入①得d b b a d a 2

1112132=-+ ②

因为|d d a 2

12,所以|d )(11b a -,从而≤d 11b a -;

而②式又可写成)(11b a -2111)122(d b b a =++;

因为d b a =),(且1),(11=b a ,所以==-1),(111b b a )(11b a -

所以)(11b a -d |,从而d b a ≤-11。

所以11b a d -=,所以b a -=211)(d d b a =-,从而b a -为完全平方数。 所以222)(122d b d

b b a ==++也是完全平方数。 证法二:已知关系式即为b b a a +=+2232?2

22)()(2b b a b a =-+- ?(b a -)

(122++b a )=2b ① 论证的关键是证明正整数b a -与122++b a 互素。

记=d (b a -,122++b a )。若1>d ,则d 有素因子p ,从而由①知2

|b p 。因为p 是

素数,故b p |,结合)(|b a p -知a p |,从而由|p 122++b a 得|p 1,这是不可能的。

故1=d ,从而由①推知正整数b a -与122++b a 都是完全平方数。

例8.证明不存在正整数n ,使2n 2+1,3n 2+1,6n 2+1都是完全平方数。

证明:假设存在这样的正整数n ,使2n 2+1,3n 2+1,6n 2+1都是完全平方数,那么

(2n 2+1)(3n 2+1)(6n 2+1)也必定是完全平方数。

而(2n 2+1)(3n 2+1)(6n 2+1)=36n 6+36n 4+11n 2+1;

=+23)36(n n 36n 6+36n 4+9n 2;=++23)136(n n 36n 6+36n 4+12n 3+9n 2+6n +1;

所以<+23)36(n n (2n 2+1)(3n 2+1)(6n 2+1)<23)136(++n n 与(2n 2+1)(3n 2+1)(6n 2+1)为完全平方数矛盾。

例9.数列{}n f 的通项公式为

n n n f ????=-????????

,n ∈+Z . 记1212C +C +C n n n n n n S f f f =,求所有的正整数n ,使得n S 能被8整除.(2005年上海竞赛试题)

解:记αβ==则

(

)(

)

()(

)

10

00

S

11

33

22

n n

i i i i i i

n n n

i i

n n

n n

i i i i

n n

i i

n n

C C

C C

αβαβ

αβαβ

==

==

=--

???

=-=+-+

???

?

??

???

?

=-

?

??

?????

∑∑

注意到

55

31

==,可得

()

11

2

1

333333

S

222222

3S S

n n n n n

n n

++

+

+

??

????

??

????????

+++-?????=-+--

??

? ? ?

? ?

????

??

?????????????

??

?????=-*

因此,S n+2除以8的余数,完全由S n+1、S n除以8的余数确定

112

11122122

,3

S C f S C f C f

==+=,故由(*)式可以算出{}n S各项除以8的余数依次是1,3,

0,5,7,0,1,3,……,它是一个以6为周期的数列,从而83

n

S n

?

故当且仅当38

n

n S

时,

练习题

1.证明:如果p和2

+

p都是大于3的素数,则6是1

+

p的因子。

证明:因为p是奇数,所以2是1

+

p的因子。又因为p,1

+

p,2

+

p除以3的余数各

不相同,而p与2

+

p都不能被3整数。于是6是1

+

p的因子。

2.设0

>n

m,证明:)1

2(|)1

2(2

2-

+m

n

解:由=

-1

22m]1

2

)

2

)[(

1

2(1

1

1

12

2

2

2+

+

+

-+

-

-

+

+n

n

m

n

n

,故)1

2(12-

+

n

|(1

22-

m

)。

又因为=

-

+1

212n)1

2(2-

n)1

2(2+

n

,从而)1

2(2+

n

|)1

2(12-

+

n

,于是由整除的性质知

)1

2(|)1

2(2

2-

+m

n

3.证明:对于任意正整数n,数2005

2005

20052

1n

+

+

+ 不能被2

+

n整除。

证明:只需证2(2

+

n)2(2005

2005

20052

1n+

+

+ )即可。

因为若n是正整数,则)

)(

(1

2

2

1-

-

-

-+

+

+

+

-

=

-n

n

n

n

n

n y

xy

y

x

x

y

x

y

x ;

若n 是正奇数,则))((1221----+-+-+=+n n n n n n y xy y x x

y x y x ; 故2+n |200520052n +;2+n |20052005)1(3-+n ,……, 2+n |200520052+n

所以2+n |2(200520052n ++ )。

又因为232>≥+n ,所以2+n 2,所以2+n 2(200520052n ++ )+2

即(2+n )2(20052005200521n +++ )命题得证。

4.已知n 为正奇数,求证:1236|60---n n n 。

证明:因为若n 是正整数,则))((1221----++++-=-n n n n n n y xy y x x

y x y x ; 若n 是正奇数,则))((1221----+-+-+=+n n n n n n y xy y x x

y x y x ; 所以n n 36|3-,12|3+n ,从而1236|3---n n

n ; n n 26|4-,13|4+n ,从而1236|4---n

n n ;

16|5-n ,n n 23|5+,从而1236|5---n n n ; 又1)5,4,3(=且60543=??,所以1236|60---n

n n 。 5.设a 、b 、c 为满足不等式1<a <b <c 的整数,且(ab-1)(bc-1)(ca-1)能被abc

整除,求所有可能数组(a ,b ,c ). (1989年上海竞赛试题)

解 ∵(ab-1)(bc-1)(ca-1)

=a 2b 2c 2

-abc (a+b+c )+ab+ac+bc-1,①

∵abc|(ab-1)(bc-1)(ca-1).

∴存在正整数k,使ab+ac+bc-1=kabc, ② k=<<<< ∴k=1.

若a≥3,此时1=-<矛盾.

已知a >1. ∴只有a=2.

当a=2时,代入②中得2b+2c-1=bc ,即 1=<

∴0<b <4,知b=3,从而易得c=5. 说明:在此例中通过对因数k 的范围讨论,从而逐步确定a 、b 、c 是一项重要解题技巧.

第三节 整数的性质及其应用(2)

基础知识

最大公约数与最小公倍数是数论中的一个重要的概念,这里我们主要讨论两个整数互

素、最大公约数、最小公倍数等基本概念与性质。

定义1.(最大公约数)设b a ,不全为零,同时整除b a ,的整数(如1±)称为它们的公约数。

因为b a ,不全为零,故b a ,只有有限多个,我们将其中最大一个称为b a ,的最大公约数,用

符号(b a ,)表示。显然,最大公约数是一个正整数。

当(b a ,)=1(即b a ,的公约数只有1±)时,我们称a 与b 互素(互质)。这是数论

中的非常重要的一个概念。

同样,如果对于多个(不全为零)的整数c b a ,,, ,可类似地定义它们的最大公约

数(c b a ,,, )。若(c b a ,,, )=1,则称c b a ,,, 互素。请注意,此时不能推出c

b a ,,, 两两互素;但反过来,若(

c b a ,,, )两两互素,则显然有(c b a ,,, )=1。

由最大公约数的定义,我们不难得出最大公约数的一些简单性质:例如任意改变b a ,的

符号,不改变(b a ,)的值,即),(),(b a b a =±±;(b a ,)可以交换,(b a ,)=(a b ,);

(b a ,)作为b 的函数,以a 为周期,即对于任意的实数x ,有(ax b a +,)=(b a ,)等

等。为了更详细地介绍最大公约数,我们给出一些常用的一些性质:

(1)设b a ,是不全为0的整数,则存在整数y x ,,使得),(b a by ax =+;

(2)(裴蜀定理)两个整数b a ,互素的充要条件是存在整数y x ,,使得1=+by ax ;

事实上,条件的必要性是性质(1)的一个特例。反过来,若有y x ,使等式成立,不妨

设d b a =),(,则b d a d |,|,故ax d |及by d |,于是)(|by ax d +,即1|d ,从而1=d 。

(3)若b m a m |,|,则),(|b a m ,即b a ,的任何一个公约数都是它们的最大公约数的约数;

(4)若0>m ,则),(),(b a m mb ma =;

(5)若d b a =),(,则1,=??

?

??d b d a ,因此两个不互素的整数,可以自然地产生一对互素的整数; (6)若1),(,1),(==m b m a ,则1),(=m ab ,也就是说,与一个固定整数互素的整数集关

于乘法封闭。并由此可以推出:若1),(=b a ,对于0>?k 有1),(=b a k

,进而有对0

>?l 有1),(=l k b a 。

(7)设ac b |,若1),(=c b ,则a b |;

(8)设正整数b a ,之积是一个正整数的k 次方幂(2≥k ),若(b a ,)=1,则b a ,都是整

数的k 次方幂。一般地,设正整数c b a ,,, 之积是一个正整数的k 次方幂(2≥k ),若c b a ,,, 两两互素,则c b a ,,, 都是正整数的k 次方幂。

定义2.设b a ,是两个非零整数,一个同时为b a ,倍数的数称为它们的公倍数,b a ,的公倍数

有无穷多个,这其中最小的一个称为b a ,的最小公倍数,记作[]b a ,,对于多个非零实数

c b a ,,, ,可类似地定义它们的最小公倍数[c b a ,,, ]。

最小公倍数主要有以下几条性质:

(1)a 与b 的任一公倍数都是[]b a ,的倍数,对于多于两个数的情形,类似结论也成立;

(2)两个整数b a ,的最大公约数与最小公倍满足:[]||,),(ab b a b a =(但请注意,这只限

于两个整数的情形,对于多于两个整数的情形,类似结论不成立);

(3)若c b a ,,, 两两互素,则[c b a ,,, ]=|c b a ,,, |;

(4)若d c d b d a |,,|,| ,且c b a ,,, 两两互素,则c b a ,,, |d 。

典例分析

例1. 设y x ,是正整数,y x <且667=+y x ,它们的最小公倍数是最大公约数的120倍,

求y x ,。

解:设d y x =),(,则nd y md x ==,,其中1),(=n m 且n m <,于是mnd y x =],[。

所以?????==+120667d

mnd nd md

即?????=?=+5322923)(3mn d n m )2()1( 由n m <及(2)可得:

?

?????====;602;1201n m n m ??????====;304;403n m n m ??????====;206;245n m n m ??????====1210;158n m n m 。 由(1)可知只能取??????====;15

8;245n m n m

从而23=d 或29,故552,115==y x 或435,232==y x 。

例2.设0,>n m ,)(|22n m mn +,则n m =。

证明:设d n m =),(,则d m m 1=,d n n 1=,其中1),(11=n m 。于是,已知条件转化为

)(|212111n m n m +,故更有)(|21211n m m +,从而转化为211|n m ,但是1),(11=n m ,故

1),(211=n m ,结合211|n m ,知必有11=m ,同时11=n ,因此n m =。

例3.设正整数c b a ,,的最大公约数是1,并且c b

a a

b =-,证明b a -是一个完全平方数。 证明:设d b a =),(,则d a a 1=,d b b 1=,其中1),(11=b a ,由于1),,(=

c b a ,故1),(=c b ,

现在问题中的等式可以转化为1111cb ca b da -= ①

由此可见1a 整除1cb 。因为1),(11=b a ,故c a |1,同样可得c b |1,再由1),(11=b a 便可以

推出c b a |11。设k b a c 11=,其中k 是一个正整数。一方面,显然k 整除c ;另一方面,结

合①式,得=d )(11b a k -,故d k |,从而),(|d c k ,但1),(=d c ,故1=k 。

因此,11b a d -=,故211)(d b a d b a =-=-,这样就证明了b a -是一个完全平方数。

例4. b a ,都是正整数,是否存在整数q p ,使得对任意的正整数n ,na p +与nb q +互质?

解:令],[b a L =,b

L s a L r ==,,则1),(=s r ,于是存在整数y x ,使得1=+sy rx , 令y q x p -==,,则对任意的正整数n ,设),(nb q na p dn ++=,有))()((|nb q s na p r dn +-+

即))((|sb ra n sq rp dn -+-,而1=+=-sy rx sq rp ,sb L ra ==,所以11|=?dn dn ,

即对任意的正整数n ,(na p +,nb q +)=1。

例5. 已知1)(20012002+-=x x x f ,证明:对于任意的正整数m ,都有

)),((),(,m f f m f m ))),(((m f f f 两两互素。

(2002年克罗地亚竞赛试题) 证明:设))))(((()( x f f f x p n =(其中f 出现n 次)。由1)1(,1)0(==f f ,故对于

N n ∈?有1)0(=n p ,

则)(x p k 是含有0次项1)0(=k p 的多项式。因此,)(m p n 除以1>m 的余数为1。设整数1>d 可整除)(m p k 和)(m p l k +,又)(m p l k +=))((m p p k l ,则当))

((m p p k l 除以)(m p k 时余数为1,即)(m p l k +=?Q )(m p k +1。所以1|d ,矛盾!

从而可知)),((),(,m f f m f m ))),(((m f f f 两两互素。

例6.求出所有的正整数对),(n m ,使得1

13-+mn n 是一个整数。 (2006年山东省第二届夏令营试题)

解:由于1)1,(3=-mn m 且)1(|11|1333+-?+-n m mn n mn 11|13

33++--?m n m mn 1|13+-?m mn ,所以n m ,是对称的。不妨设n m ≥。

当n m =时,则211111

1*223=?∈-+=-+-=-+n N n n n n n n n ,从而n m ==2; 当n m >时,若1=n 时,则有2|1-m ,所以2=m 或3;

若2≥n 时,由于1

13-+mn n 是一个整数,从而*N k ∈?使得)1)(1(13--=+mn kn n 即=-1kn <-+113mn n 111123-+=-+n n n n ,所以1-kn <1

11-+n 。 又由于2≥n ,*N k ∈,所以1=k 。

所以1)1)(1(133+--=--=+mn n mn mn n n ,从而

*21

2111N n n n n m ∈-++=-+=得2=n 或3,所以5=m ; 综上知所有的),(n m 为(2,2),(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).

例7.已知*,,,N n m b a ∈,且2,1),(>=a b a ,试问m

m n n b a b a ++|的充要条件是m n |吗?

(2006年山东省第二届夏令营试题)

分析:因为)()(n k n k n n n n k k k b a b b a a

b a -----+=+,所以?++k k n n b a b a |n k n k n n b a b a --++|; 又)()(n r n r n n n n r r r b a b b a a b a ---+-+=-,所以?++r r n n b a b a |n r n r n n b a b a --++|;

令)0(n r r nq m <≤+=,则有?++++r nq r nq n n b a b a |r n q r n q n n b a b a +-+--+)1()1(|

???+++-+- r n q r n q n n b a b a )2()2(|r q r n n b a b a )1(|-++

又因为r n >,所以<-+r q r b a )1(n n b a +

从而上式0=?r 且q 为奇数,即m m n n b a b a ++|的充要条件是m n |且

n m 为奇数。 例8.我们知道9123=+有1个质因子,且12|332+;

19351312332?==+有2个质因子,且|331223+

………………

如此下去,我们可以猜想:,*N k ∈ 123+k 至少有k 个质因子,且|31+k 123+k

。试证明之。 (2006年山东省第二届夏令营试题)

证明:令k a =123+k ,则k a =k k b 13+,即要证k b 是整数且有1-k 个质因子。下用数学归

纳法证明k b 是整数。

1=k 时,结论显然;

假设k n =时,成立;

当k n =+1时,因为=+1k a (k a -1)3+1=k a 3-3k a 2+3k a ;

因为|31+k k a ,所以|32+k 1+k a ,即1+k b 是整数。

下证1+k b 至少有k 个质因子。

=+1k a 23+k 1+k b =k a 3-3k a 2+3k a =(13+k k b )3-3(13+k k b )2+3(13+k k b ).

因为1+k b =k b (1331212+-++k k k k b b ),令=k c 1331212+-++k k k k b b ,则1+k b =k b k c

由于(k c ,3)=1,所以(k c ,k b )=1,从而k c 必有异于k b 质因子的质因子,

所以1+k b 至少有k 个质因子。 证毕!

练习

1.若m N n ,∈是奇数,则1)12,12(=+-n

m 。

分析:要证明12-m 与12+n 互质,我们只需要证明它们的公因子为1即可,但是这对于n m ,不好处理,由m 为奇数这一条件,我们可以想到12

|2+mn m 从而找到思路。 证明:由于m 为奇数,故12+n 12

|+mn ,又12-m 12|+mn ,从而(12-m ,12+n )≤(,12+mn 12-mn ),而(,12+mn 12-mn )=(,12+mn 2)=1,故1)12,12(=+-n m 。

2.若17|(2a +3b ),试证:17|(9a +5b ).

证明:注意到2(9a +5b )=9(2a +3b )-17b ,于是17|2(9a +5b ).但是(17,2)=1,即得17|(9a +5b ).

3.设a n ,是正整数,若n a 不是整数,则必为无理数。

证明:设n

a 是非整数的有理数,则可设1),(,1,=>=c

b b b

c a n ,于是n n b c a =。因为1),(=c b 故可知1),(=n n c b 。但1>n b ,因而n

n c b |。这与a b c n n

=是整数矛盾!证毕。 4.设a,b 是不全为0的整数,一切形如ax+by ),(N y x ∈的数中,最小的正数是d ,试证:d =(a,b ).

5.记F n =n

22+1,试证:(F n ,F m )=1,这里n m ≠. 第四节 同余

同余式性质应用非常广泛,在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能,与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。

基础知识

三个数论函数

对于任何正整数均有定义的函数,称为数论函数。在初等数论中,所能用到的无非也就有三个,分别为:高斯(Gauss)取整函数[x ]及其性质,除数函数d (n )和欧拉(Euler)函数)(x ?和它的计算公式。

1. 高斯(Gauss)取整函数[x ]

设x 是实数,不大于x 的最大整数称为x 的整数部分,记为[x ];][x x -称为x 的小数部分,记为{x }。例如:[0.5]=0,7.0}3.0{,1415.0}{,4][,3]3[,7]50[=-=-=--=-= ππ等等。 由}{],[x x 的定义可得如下性质:

性质1.1}{0};{][<≤=-x x x x ;

历年全国高中数学联赛试题及答案

历年全国高中数学联赛试题及答案 1.全卷满分120分,考试时间120分钟.试题卷共6页,有三大题,共24小题。 2.全卷答案必须做在答题纸卷Ⅰ、卷Ⅱ的相应位置上,做在试题卷上无效,考试时不 能使用计算器。 参考公式:二次函数图象的顶点坐标是。 温馨提示:请仔细审题,细心答题,答题前仔细阅读答题纸上的“注意事项”。 卷Ⅰ(选择题) 一、选择题(本大题有10小题,每小题3分,共30分.请选出各题中唯一的正确选项,不选、多选、错选,均不得分) 1.2的相反数是(▲) A.-2 B.2 C.- D. 2.下列计算正确的是(▲)A.B.9 =3 C.3-1= -3 D.2 +3= 5 3.据交通运输部统计,2013年春运期间,全国道路、水路、民航、铁路运送旅客总量超过了3400000000人次,该数用科学记数法可表示为(▲) A.B.C. D. 4.如图是由个相同的正方体搭成的几何体,则其俯视图是(▲) 5.使分式无意义的的值是(▲) A. B. C. D. 6.如图,已知,若, ,则等于(▲) A.B.C.D. 7.市委、市政府打算在2015年底前,完成国家森林城市创建.这是小明随机抽取我市10个小区所得到的绿化率情况,结果如下表: 小区绿化率(%) 20 25 30 32 小区个数 2 4 3 1 则关于这10个小区的绿化率情况,下列说法错误的是(▲) A.中位数是25% B.众数是25% C.极差是13% D.平均数是26.2% 8.将一个半径为R,圆心角为90°的扇形围成一个圆锥的侧面(无重叠),设圆锥底面半径为r,则R与r的关系正确的是(▲) A.R=8r B.R=6r C.R=4r D.R=2r 9.甲、乙两车分别从相距的两地同时出发,它们离A地的路程随时间变化的图象如图所示,则下列结论不正确的是( ▲) A.甲车的平均速度为; B.乙车行驶小时到达地,稍作停留后返回地; C.经小时后,两车在途中相遇; D.乙车返回地的平均速度比去地的平均速度小。 10.如图,为等边三角形,点的坐标为,过点作直线交于点,交于,点在反比例函数<的图象上,若和(即图中两阴影部分)的面积相等,则值为(▲)A.B.C.D. 卷Ⅱ(非选择题) 二、填空题(本大题有6小题,每题4分,共24分) 11.分解因式:= ▲。 12.一个不透明的袋中装有除颜色外其他均相同的2个红球和3个黄球,从中随机摸出一个

初等数论练习题及答案

初等数论练习题一 一、填空题 1、τ(2420)=27;?(2420)=_880_ 2、设a ,n 是大于1的整数,若a n -1是质数,则a=_2. 3、模9的绝对最小完全剩余系是_{-4,-3,-2,-1,0,1,2,3,4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ,y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数,则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程:3x 2+11x -20≡0 (mod 105)。 解:因105 = 3?5?7, 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3), 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0,3 (mod 5), 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2,6 (mod 7), 故原同余方程有4解。 作同余方程组:x ≡b 1 (mod 3),x ≡b 2 (mod 5),x ≡b 3 (mod 7), 其中b 1 = 1,b 2 = 0,3,b 3 = 2,6, 由孙子定理得原同余方程的解为x ≡13,55,58,100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解? 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-)()()()(),()()()(),()())()(( )(解: 故同余方程x 2≡42(mod 107)有解。 3、求(127156+34)28除以111的最小非负余数。

高中数学竞赛辅导初等数论不定方程

不定方程 不定方程是指未知数的个数多于方程的个数,且未知数的取值范围是受某些限制(如整数、正整数或有理数)的方程.不定方程是数论的一个重要课题,也是一个非常困难和复杂的课题. 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、(2009一试8)某车站每天8 00~900∶∶,900~1000∶∶都恰有一辆客车到站,但到站的时刻是随机的,且两者到站的时间是相互独立的,其规律为 一旅客820∶【答案】27 【解析】旅客候车的分布列为 候车时间的数学期望为10305070902723361218 ?+?+?+?+?= 2、(2010一试6)两人轮流投掷骰子,每人每次投掷两颗,第一个使两颗骰子点数和大于6者为胜,否则轮由另一人投掷.先投掷人的获胜概率是 . 【答案】 12 17 3、(2012一试8)某情报站有,,,A B C D 四种互不相同的密码,每周使用其中的一种密码,且每周都是从上周未使用的三种密码中等可能地随机选用一种.设第1周使用A种密码,那么第7周也使用A种密码的概率是.(用最简分数表示) 【答案】 61 243 【解析】用k P 表示第k 周用 A 种密码的概率,则第k 周末用A 种密码的概率为 1k P -.于是,有11(1),3k k P P k N *+=-∈,即1111()434k k P P +-=--由11P =知,14k P ? ?-???? 是首项为34,公

比为13-的等比数列.所以1131()443k k P --=-,即1311()434k k P -=-+,故761243 P = 4、(2014一试8)设D C B A ,,,是空间四个不共面的点,以 2 1 的概率在每对点之间连一条边,任意两点之间是否连边是相互独立的,则B A ,可用(一条边或者若干条边组成的)空间折线连接的概率是__________. 【答案】 3 4 2221219B C D -?-=点相连,且与,中至少一点相连,这样的情况数为()() 22(3)AB AD DB 无边,也无CD 边,此时AC,CB 相连有2种情况,,相连也有2种情况, ,,,,AC CB AD DB A B 但是其中均相连的情况被重复了一次,故可用折线连接的情况数为 222+2-1=7. 483++==.644以上三类情况数的总和为329748,故A,B 可用折线连接的概率为 5、(2015一试5)在正方体中随机取三条棱,它们两两异面的概率为. 【答案】 2 55 【解析】设正方体为ABCD-EFGH ,它共有12条棱,从中任意选出3条棱的方法共有3 12C =220种. 下面考虑使3条棱两两异面的取法数,由于正方体的棱共确定3个互不平行的方向(即AB 、AD 、AE 的方向),具有相同方向的4条棱两两共面,因此取出的3条棱必属于3个不同的方向.可先取定AB 方向的棱,这有4种取法.不妨设取的棱就是AB ,则AD 方向只能取棱EH 或棱FG ,共2种可能,当AD 方向取棱是EH 或FG 时,AE 方向取棱分别只能是CG 或DH. 由上可知,3条棱两两异面的取法数为4×2=8,故所求的概率为82 22055 =.

初等数论作业

《初等数论》作业 第一次作业: 一、单项选择题 1、=),0(b ( ). A b B b - C b D 0 2、如果a b ,b a ,则( ). A b a = B b a -= C b a ≤ D b a ±= 3、如果1),(=b a ,则),(b a ab +=( ). A a B b C 1 D b a + 4、小于30的素数的个数( ). A 10 B 9 C 8 D 7 5、大于10且小于30的素数有( ). A 4个 B 5个 C 6个 D 7个 6、如果n 3,n 5,则15()n . A 整除 B 不整除 C 等于 D 不一定 7、在整数中正素数的个数( ). A 有1个 B 有限多 C 无限多 D 不一定 二、计算题 1、求24871与3468的最大公因数? 2、求[24871,3468]=? 3、求[136,221,391]=? 三、证明题 1、如果b a ,是两个整数,0 b ,则存在唯一的整数对r q ,,使得r bq a +=,其中b r ≤0. 2、证明对于任意整数n ,数6 233 2n n n + +是整数. 3、任意一个n 位数121a a a a n n -与其按逆字码排列得到的数n n a a a a 121- 的差必是9的倍数. 4、证明相邻两个偶数的乘积是8的倍数. 第二次作业 一、单项选择题 1、如果( A ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 2、不定方程210231525=+y x (A ). A 有解 B 无解 C 有正数解 D 有负数解 二、求解不定方程 1、144219=+y x . 解:因为(9,21)=3,1443,所以有解; 化简得4873=+y x ;

竞赛数学中的初等数论(精华版)

《竞赛数学中的初等数论》 贾广素编著 2006-8-21

序 言 数论是竞赛数学中最重要的一部分,特别是在1991年,IMO 在中国举行,国际上戏称那一年为数论年,因为6道IMO 试题中有5道与数论有关。 数论的魅力在于它可以适合小孩到老头,只要有算术基础的人均可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想,当然,这一谣言最终被澄清了。可是这也说明了最难的数论问题,适合于任何人去研究。 初等数论最基础的理论在于整除,由它可以演化出许多数论定理。做数论题,其实只要整除理论即可,然而要很快地解决数论问题,则要我们多见识,以及学习大量的解题技巧。这里我们介绍一下数论中必需的一个内容:对于N r q N b a ∈?∈?,,,,满足r bq a +=,其中b r <≤0。 除了在题目上选择我们努力做到精挑细选,在内容的安排上我们也尽量做到讲解详尽,明白。相信通过对本书学习,您可以对数论有一个大致的了解。希望我们共同学习,相互交流,在学习交流中,共同提高。 编者:贾广素 2006-8-21于山东济宁

第一节 整数的p 进位制及其应用 正整数有无穷多个,为了用有限个数字符号表示出无限多个正整数,人们发明了进位制, 这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系,近几年来,国内与 国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理 数列问题等等。在本节,我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ,其各位上的数字分别记为021,,,a a a m m --,则此数可以简记为:021a a a A m m --=(其中01≠-m a )。 由于我们所研究的整数通常是十进制的,因此A 可以表示成10的1-m 次多项式,即 012211101010a a a a A m m m m +?++?+?=---- ,其中1,,2,1},9,,2,1,0{-=∈m i a i 且 01≠-m a ,像这种10的多项式表示的数常常简记为10021)(a a a A m m --=。在我们的日常 生活中,通常将下标10省略不写,并且连括号也不用,记作021a a a A m m --=,以后我们 所讲述的数字,若没有指明记数式的基,我们都认为它是十进制的数字。但是随着计算机的 普及,整数的表示除了用十进制外,还常常用二进制、八进制甚至十六进制来表示。特别是 现代社会人们越来越显示出对二进制的兴趣,究其原因,主要是二进制只使用0与1这两种 数学符号,可以分别表示两种对立状态、或对立的性质、或对立的判断,所以二进制除了是 一种记数方法以外,它还是一种十分有效的数学工具,可以用来解决许多数学问题。 为了具备一般性,我们给出正整数A 的p 进制表示: 012211a p a p a p a A m m m m +?++?+?=---- ,其中1,,2,1},1,,2,1,0{-=-∈m i p a i 且 01≠-m a 。而m 仍然为十进制数字,简记为p m m a a a A )(021 --=。 典例分析 例1.将一个十进制数字2004(若没有指明,我们也认为是十进制的数字)转化成二进制与 八进制,并将其表示成多项式形式。 分析与解答 分析:用2作为除数(若化为p 进位制就以p 作为除数),除2004商1002,余数为0;再 用2作为除数,除1002商501余数为0;如此继续下去,起到商为0为止。所得的各次余 数按从左到右的顺序排列出来,便得到所化出的二进位制的数。 解:

历年全国高中数学联赛二试几何题汇总汇总

历年全国高中数学联赛二试几何题汇总 2007 联赛二试 类似九点圆 如图,在锐角?ABC 中,AB

2013年春_西南大学《初等数论》作业及答案(共4次_已整理)

2013年春西南大学《初等数论》作业及答案(共4次,已整理) 第一次作业 1、设n,m为整数,如果3整除n,3整除m,则9()mn。 A:整除 B:不整除 C:等于 D:小于 正确答案:A 得分:10 2、整数6的正约数的个数是()。 A:1 B:2 C:3 D:4 正确答案:D 得分:10 3、如果5|n ,7|n,则35()n 。 A:不整除 B:等于 C:不一定 D:整除 正确答案:D 得分:10 4、如果a|b,b|a ,则()。 A:a=b B:a=-b C:a=b或a=-b D:a,b的关系无法确定 正确答案:C 得分:10 5、360与200的最大公约数是()。 A:10 B:20 C:30 D:40 正确答案:D 得分:10 6、如果a|b,b|c,则()。 A:a=c B:a=-c C:a|c D:c|a

正确答案:C 得分:10 7、1到20之间的素数是()。 A:1,2,3,5,7,11,13,17,19 B:2,3,5,7,11,13,17,19 C:1,2,4,5,10,20 D:2,3,5,7,12,13,15,17 正确答案:B 得分:10 8、若a,b均为偶数,则a + b为()。 A:偶数 B:奇数 C:正整数 D:负整数 正确答案:A 得分:10 9、下面的()是模12的一个简化剩余系。 A:0,1,5,11 B:25,27,13,-1 C:1,5,7,11 D:1,-1,2,-2 正确答案:C 得分:10 10、下面的()是模4的一个完全剩余系。 A:9,17,-5,-1 B:25,27,13,-1 C:0,1,6,7 D:1,-1,2,-2 正确答案:C 得分:10 11、下面的()是不定方程3x + 7y = 20的一个整数解。 A:x=0,y=3 B:x=2,y=1 C:x=4,y=2 D:x=2,y=2 正确答案:D 得分:10 12、设a,b,c,d是模5的一个简化剩余系,则a+b+c+d对模5同余于()。 A:0 B:1 C:2 D:3 正确答案:A 得分:10 13、使3的n次方对模7同余于1的最小的正整数n等于()。 A:6 B:2

欧拉定理

欧拉定理 认识欧拉 欧拉,瑞士数学家,13岁进巴塞尔大学读书,得到著名数学家贝努利的精心指导.欧拉是科学史上最多产的一位杰出的数学家,他从19岁开始发表论文,直到76岁,他那不倦的一生,共写下了886本书籍和论文,其中在世时发表了700多篇论文。彼得堡科学院为了整理他的著作,整整用了47年。欧拉著作惊人的高产并不是偶然的。他那顽强的毅力和孜孜不倦的治学精神,可以使他在任何不良的环境中工作:他常常抱着孩子在膝盖上完成论文。即使在他双目失明后的17年间,也没有停止对数学的研究,口述了好几本书和400余篇的论文。当他写出了计算天王星轨道的计算要领后离开了人世。欧拉永远是我们可敬的老师。欧拉研究论著几乎涉及到所有数学分支,对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究!有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯(Gauss,1777-1855)曾说过“研究欧拉的著作永远是了解数学的最好方法”。欧拉还是数学符号发明者,他创设的许多数学符号,例如π,i,e,sin,cos,tg,Σ,f (x)等等,至今沿用。欧拉不仅解决了彗星轨迹的计算问题,还解决了使牛顿头痛的月离问题。对著名的“哥尼斯堡七桥问题”的完美解答开创了“图论”的研究。欧拉发现,不论什么形状的凸多面体,其顶点数V、棱数E、面数F之间总有关系V+F-E=2,此式称为欧拉公式。V+F-E 即欧拉示性数,已成为“拓扑学”的基础概念。那么什么是“拓扑学”?欧拉是如何发现这个关系的?他是用什么方法研究的?今天让我们沿着欧拉的足迹,怀着崇敬的心情和欣赏的态度探索这个公式...... 初等数论中的欧拉定理

数学高中竞赛之初等数论2

1 4 7 10 13 … 4 9 14 19 24 … 7 14 21 28 35 … 10 19 28 37 46 … … … … … … … 定理2:不定方程x 2+y 2=z 2满足(x ,y )=1,x ,y ,z >0,2|x 的全部整数解可表示为 x=2ab ,y=a 2-b 2,z=a 2+b 2。其中a >b >0,a 、b 一奇一偶,(a ,b )=1为任意整数。 四、例题与练习 1、右表的结构为:第一行是以1为首项,3为 公差的无穷等差数列;第一列中的数与第一行 中的数对应相等;第n (n ≥2)行是公差为2n+1 的无穷等差数列。证明:⑴若N 在表中,则2N+7 不是素数;⑵若N 不在表中,则2N+7是素数。 2、证明:若正整数x 、y 使得2xy | x 2+y 2-x ,则x 是完全平方数。 3、证明:存在一个1997的整倍数,它不超过11位,且各位数字不含2,3,4,5,6,7。 4、设c 为奇自然数,且存在自然数a ≤ 13-c ,使(2a -1)2+8c 为平方数,求证:c 为合数。 5、求最大的正整数x ,使得对任意y ∈N ,有x|(1127-+y y ) 6、证明:方程3 25y x =+无整数解。 7、求方程235=-y x 的全部整数解。 8、给数集M={1,2,…,n -1}(n ≥3)中的数染色,满足⑴i 与n -i 同色;⑵有一个k ∈M ,(k ,n )=1,使得当i ≠k 时i 与|k -i|同色,求证:M 中有一色。

9、在一个圆周上标记了4个整数,规定一个方向,使每个整数都有相邻的下一个数,每一步操作是指对每一个数,同时用该数与下一个数之差来替换,即对于a 、b 、c 、d 依次用a -b 、b -c 、c -d 、d -a 来替换。问经过1996步这样的替换之后,是否可以得到4个数a 、b 、c 、d ,使得|bc -ad|、|ac -bd|、|ab -cd|都是素数。(IMO -37预选题) 10、求所有大于3的自然数n ,使得1+321n n n C C C ++整除20002(CMO - 1998) 11、有多少个正整数对x 、y ,x ≤y ,使得(x ,y )=5!和[x ,y]=50!成立?(1997年加拿大) 12、设w (n )表示自然数n 的素因数的个数,n >1。证明:存在无穷多个n ,使得w (n )<w (n+1)<w (n+2)。 13、求最小的整数n (n ≥4),满足从任意n 个不同的整数中能选出四个不同的数a 、b 、c 、d ,使a+b -c -d 可以被20整数。 14、求所有实数对(a ,b ),使对所有的正整数n 满足a[bn]=b[an],其中[x]表示不超过x 的最大整数。(IMO -39预选题)

高中数学竞赛历届IMO竞赛试题届完整中文版

第1届I M O 1.求证(21n+4)/(14n+3)对每个自然数n都是最简分数。 2.设√(x+√(2x-1))+√(x-√(2x-1))=A,试在以下3种情况下分别求出x的实数解: (a)A=√2;(b)A=1;(c)A=2。 3.a、b、c都是实数,已知cosx的二次方程 acos2x+bcosx+c=0, 试用a,b,c作出一个关于cos2x的二次方程,使它的根与原来的方程一样。当a=4,b=2,c=-1时比较cosx和cos2x的方程式。 4.试作一直角三角形使其斜边为已知的c,斜边上的中线是两直角边的几何平均值。 5.在线段AB上任意选取一点M,在AB的同一侧分别以AM、MB为底作正方形AMCD、MBEF,这两个正方形的外接圆的圆心分别是P、Q,设这两个外接圆又交于M、N, (a.)求证AF、BC相交于N点; (b.)求证不论点M如何选取直线MN都通过一定点S; (c.)当M在A与B之间变动时,求线断PQ的中点的轨迹。 6.两个平面P、Q交于一线p,A为p上给定一点,C为Q上给定一点,并且这两点都不在直线p上。试作一等腰梯形ABCD(AB平行于CD),使得它有一个内切圆,并且顶点B、D分别落在平面P和Q 上。 第2届IMO 1.找出所有具有下列性质的三位数N:N能被11整除且N/11等于N的各位数字的平方和。 2.寻找使下式成立的实数x: 4x2/(1-√(1+2x))2<2x+9 3.直角三角形ABC的斜边BC的长为a,将它分成n等份(n为奇数),令为从A点向中间的那一小段线段所张的锐角,从A到BC边的高长为h,求证: tan=4nh/(an2-a).

初等数论定理

初等数论 1. 整除性质 a) 若a|b,a|c,则a|(b±c)。 b) 若a|b,则对任意c,a|bc。 c) 对任意非零整数a,±1|a,±a|a。 d) 若a|b,b|a,则|a|=|b|。 e) 如果a能被b整除,c是任意整数,那么积ac也能被b整除。 f) 如果a同时被b与c整除,并且b与c互质,那么a一定能被积bc整除,反 过来也成立。 g) 如果a∣b且b∣c,则a∣c。 h) 如果c∣a且c∣b,则c∣ua+vb,其中u,v是整数。 i) 对任意整数a,b,b>0,存在唯一的数对q,r,使a=bq+r,其中0≤r0是两个不全为零的整数a,b的公因子,如果a,b的任何公因子都整除c,则c称为a,b的最大公因子,记为c= (a,b). a) (a,b)=(-a,b)=(a,-b)=(-a,-b) b) (0,a)=a c) 设a,b是两个不全为零的整数,则存在两个整数u,v,使 (a,b)= ua+vb. 4. 欧几里德除法(辗转相除法): 已知整数a,b,记r0=a,r1=b, r0=q1r1+r2,0 ≤r2<r1=b; r1=q2r2+r3,0 ≤r3<r2; … r n-2=q n-1r n-1+r n,0 ≤r n<r n-1; r n-1=q n r n

初等数论中的几个重要定理高中数学竞赛

初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数称为是模的既约剩余系,如果对任意的,且对于任意的,若=1,则有且仅有一个是对模 的剩余,即。并定义中和互质的数的个数, 称为欧拉(Euler)函数。 这是数论中的非常重要的一个函数,显然,而对于,就是1,2,…,中与互素的数的个数,比如说是素数,则有。 引理:;可用容斥定理来证(证明略)。 定理1:(欧拉(Euler)定理)设=1,则。 分析与解答:要证,我们得设法找出个相乘,由个数我们想到中与互质的的个数:,由于=1,从而 也是与互质的个数,且两两余数不一样,故 (),而()=1,故。 证明:取模的一个既约剩余系,考虑,由于与互质,故仍与互质,且有,于是对每个都能找到唯一的一个,使得,这种对应关系 是一一的,从而,。

,,故。证毕。 这是数论证明题中常用的一种方法,使用一组剩余系,然后乘一个数组组成另外一组剩余系来解决问题。 定理2:(费尔马(Fermat)小定理)对于质数及任意整数有。 设为质数,若是的倍数,则。若不是的倍数,则 由引理及欧拉定理得,,由此即得。 定理推论:设为质数,是与互质的任一整数,则。 定理3:(威尔逊(Wilson)定理)设为质数,则。 分析与解答:受欧拉定理的影响,我们也找个数,然后来对应乘法。 证明:对于,在中,必然有一个数除以余1,这是因为则好是的一个剩余系去0。 从而对,使得; 若,,则,,故对于,有。即对于不同的对应于不同的,即中数可两两配对,其积除以余1,然后有,使,即与它自己配对,这时,,或,或。 除外,别的数可两两配对,积除以余1。故。

定义:设为整系数多项式(),我们把含有的一组同余式 ()称为同余方组程。特别地,,当均为的一次整系数多项式时,该同余方程组称为一次同余方程组.若整数同时满足: ,则剩余类(其中)称为同余方程组的一个解,写作 定理4:(中国剩余定理)设是两两互素的正整数,那么对于任意整数,一次同余方程组,必有解,且解可以写为: 这里,,以及满足,(即为对模的逆)。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解,而对于解的形式并不重要。 定理5:(拉格郎日定理)设是质数,是非负整数,多项式 是一个模为次的整系数多项式(即),则同余方程至多有个解(在模有意义的情况下)。 定理6:若为对模的阶,为某一正整数,满足,则必为的倍数。 以上介绍的只是一些系统的知识、方法,经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用,有时也会起到

历年全国高中数学联赛试题及答案

1988年全国高中数学联赛试题 第一试(10月16日上午8∶00——9∶30) 一.选择题(本大题共5小题,每小题有一个正确答案,选对得7分,选错、不选或多选均得0分): 1.设有三个函数,第一个是y=φ(x ),它的反函数是第二个函数,而第三个函数的图象及第二个函数的图象关于x +y=0对称,那么,第三个函数是( ) A .y=-φ(x ) B .y=-φ(-x ) C .y=-φ-1(x ) D .y=-φ- 1(-x ) 2.已知原点在椭圆k 2x 2+y 2-4kx +2ky +k 2-1=0的内部,那么参数k 的取值范围是( ) A .|k |>1 B .|k |≠1 C .-1π 3 ; 命题乙:a 、b 、c 相交于一点. 则 A .甲是乙的充分条件但不必要 B .甲是乙的必要条件但不充分 C .甲是乙的充分必要条件 D .A 、B 、C 都不对 5.在坐标平面上,纵横坐标都是整数的点叫做整点,我们用I 表示所有直线的集合,M 表示恰好通过1个整点的集合,N 表示不通过任何整点的直线的集合,P 表示通过无穷多个整点的直线的集合.那么表达式 ⑴ M ∪N ∪P=I ; ⑵ N ≠?. ⑶ M ≠?. ⑷ P ≠?中,正确的表达式的个数是 A .1 B .2 C .3 D .4 二.填空题(本大题共4小题,每小题10分): 1.设x ≠y ,且两数列x ,a 1,a 2,a 3,y 和b 1,x ,b 2,b 3,y ,b 4均为等差数列,那么b 4-b 3 a 2-a 1= . 2.(x +2)2n +1的展开式中,x 的整数次幂的各项系数之和为 . 3.在△ABC 中,已知∠A=α,CD 、BE 分别是AB 、AC 上的高,则DE BC = . 4.甲乙两队各出7名队员,按事先排好顺序出场参加围棋擂台赛,双方先由1号队员比赛,负者被淘汰,胜者再及负方2号队员比赛,……直至一方队员全部淘汰为止,另一方获得胜利,形成一种比赛过程.那么所有可能出现的比赛过程的种数为 . 三.(15分)长为2,宽为1的矩形,以它的一条对角线所在的直线为轴旋转一周,求得到的旋转体的体积. 四.(15分) 复平面上动点Z 1的轨迹方程为|Z 1-Z 0|=|Z 1|,Z 0为定点,Z 0≠0,另一个动点Z 满足Z 1Z=-1,求点Z 的轨迹,指出它在复平面上的形状和位置. 五.(15分)已知a 、b 为正实数,且1a +1 b =1,试证:对每一个n ∈N *, (a +b )n -a n -b n ≥22n -2n +1.

西南大学2016《初等数论》网上作业(共4次)

初等数论第一次作业 简答题 1. 叙述整数a被整数b整除的概念。 2. 给出两个整数a,b的最大公因数的概念。 3. 叙述质数的概念,并写出小于14的所有质数。 4. 叙述合数的概念,并判断14是否为合数。 5. 不定方程c +有整数解的充分必要条件是什么? by ax= 6. 列举出一个没有整数解的二元一次不定方程。 7. 写出一组勾股数。 8. 写出两条同余的基本性质。 9. 196是否是3的倍数,为什么? 10. 696是否是9的倍数,为什么? 11. 叙述孙子定理的内容。 12. 叙述算术基本定理的内容。 13.给出模6的一个完全剩余系。 14.给出模8的一个简化剩余系。 15.写出一次同余式) ax≡有解得充要条件。 (mod m b 答: 1.设a,b是任意两个整数,其中b≠0,如果存在一个整数q使得等式a=bq 成立,我们就称b整除a或a被b整除,记做b|a。 2.设a,b是任意两个整数,若整数d是他们之中每一个的因数,那么d就叫做a,b的一个公因数。a,b的公因数中最大的一个叫做最大公因数。 3.一个大于1的整数,如果它的正因数只有1和它本身,就叫作质数(或素数)。14的所有质数为2,3,5,7,11,13 4.一个大于1的整数,如果它的正因数除了1和它本身,还有其他的正因数,则就叫作合数。14的所有正因数为1,2,7,14,除了1和本身14,还有2和7两个正因数,所以14是合数。 5.不定方程c ax= +有整数解的充分必要条件是。 by 6.没有整数解的二元一次不定方程10x+10y=5。 7.一组勾股数为3,4,5。 8.同余的基本性质为: 性质1 m为正整数,a,b,c为任意整数,则 ①a≡a(mod m);

第五节初等数论中的几个重要定理

第五节 初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数s x x x ,,,21 称为是模m 的既约剩余系,如果对任意的s j ≤≤1,1),(=m x j 且对于任意的Z a ∈,若),(m a =1,则有且仅有一个j x 是a 对模m 的剩余,即)(mod m x a j ≡。并定义},,2,1{)(m s m ==?中和m 互质的数的个数,)(m ?称为欧拉(Euler )函数。 这是数论中的非常重要的一个函数,显然1)1(=?,而对于1>m ,)(m ?就是1,2,…,1-m 中与m 互素的数的个数,比如说p 是素数,则有1)(-=p p ?。 引理:∏? =为质数)-(P |P 11)(m P m m ?;可用容斥定理来证(证明略)。 定理1:(欧拉(Euler )定理)设),(m a =1,则)(mod 1)(m a m ≡?。 证明:取模m 的一个既约剩余系))((,,,,21m s b b b s ?= ,考虑s ab ab ab ,,,21 ,由于a 与m 互质,故)1(s j ab j ≤≤仍与m 互质,且有i ab )1(s j i ab j ≤<≤?,于是对每个 s j ≤≤1都能找到唯一的一个s j ≤≤)(1σ, 使得)(mod )(m b ab j j σ≡,这种对应关系σ是一一的,从而)(mod )(mod )(11)(1m b m b ab s j j s j j s j j ∏∏∏===≡≡σ,∴))(mod ()(11m b b a s j j s j j s ∏∏==≡。 1),(1=∏=s j j b m ,)(mod 1m a s ≡∴,故)(mod 1)(m a m ≡?。证毕。 分析与解答:要证)(mod 1)(m a m ≡?,我们得设法找出)(m ?个n 相乘,由)(m ?个数我们想到m ,,2,1 中与m 互质的)(m ?的个数:)(21,,,m a a a ? ,由于),(m a =1,从而)(21,,,m aa aa aa ? 也是与m 互质的)(m ?个数,且两两余数不一样,故)(21m a a a ???? ≡)(21,,,m aa aa aa ? ≡)(m a ?)(21m a a a ???? (m mod ),而 ()(21m a a a ???? m )=1,故)(mod 1)(m a m ≡?。 这是数论证明题中常用的一种方法,使用一组剩余系,然后乘一个数组组成另外一组剩余系来解决问题。

初中数学竞赛专题复习第三篇初等数论第20章同余试题新人教版

第20章 同 余 20.1.1★(1)证明:任意平方数除以4,余数为0或1; (2)证明:任意平方数除以8,余数为0、1或4. 解析 (1)因为 奇数()2 22214411(mod 4)k k k =+=++≡, 偶数()222240(mod4)k k ==≡, 所以,正整数21(mod 4),;0(mod 4),.n n n ?≡??奇偶为数为数 (2)奇数可以表示为21k +,从而 奇数()22441411k k k k =++=++. 因为两个连续整数k 、1k +中必有一个是偶数,所以()41k k +是8的倍数,从而 奇数()2811mod8i =+≡. 又,偶数()2 2224k k ==(k 为整数). 若k =偶数2t =,则()224160mod 8k t ==. 若k =奇数21t =+,则 ()()2 2244211644(mod8)k t t t =+=++≡. 所以,平方数()()()0mod8,1mod8,4mod8. ??≡??? 评注 事实上,我们也可以这样来证:因为对任意整数a ,有0a ≡,±1,2(mod4),所以,0a ≡,1(mod4);又a ≡0,±1,±2,±3,4(mod8),所以,2a ≡0,1,()4mod8. 20.1.2★求证:一个十进制数被9除所得的余数,等于它的各位数字被9除所得的余数. 解析 设这个十进制数1210n n A a a a a a -=. 因10≡1(mod9),故对任何整数k ≥1,有 ()1011mod9k k ≡=. 因此 1210n n A a a a a a -= 1110101010n n n n a a a a --=?+?++?+ ()110mod9n n a a a a -≡++ ++.

高中数学竞赛历届IMO竞赛试题届完整中文版

第1届I M O 1.? 求证(21n+4)/(14n+3) 对每个自然数 n都是最简分数。 2.??设√(x+√(2x-1))+√(x-√(2x-1))=A,试在以下3种情况下分别求出x的实数解:? (a) A=√2;(b)A=1;(c)A=2。 3.?a、b、c都是实数,已知 cos x的二次方程 a cos2x + b cos x + c = 0, 试用a,b,c作出一个关于 cos 2x的二次方程,使它的根与原来的方程一样。当 a=4,b=2,c=-1时比较 cos x和cos 2x的方程式。 4.? 试作一直角三角形使其斜边为已知的 c,斜边上的中线是两直角边的几何平均值。 5.? 在线段AB上任意选取一点M,在AB的同一侧分别以AM、MB为底作正方形AMCD、MBEF,这两个正方形的外接圆的圆心分别是P、Q,设这两个外接圆又交于M、N, ??? (a.) 求证 AF、BC相交于N点; ?? (b.) 求证不论点M如何选取直线MN 都通过一定点 S; ??? (c.) 当M在A与B之间变动时,求线断 PQ的中点的轨迹。 6.? 两个平面P、Q交于一线p,A为p上给定一点,C为Q上给定一点,并且这两点都不在直线p上。试作一等腰梯形ABCD(AB平行于CD),使得它有一个内切圆,并且顶点B、D分别落在平面P和Q上。 第2届IMO 1.? 找出所有具有下列性质的三位数 N:N能被11整除且 N/11等于N的各位数字的平方和。 2.? 寻找使下式成立的实数x: 4x2/(1 - √(1 + 2x))2 ?< ?2x + 9

3.? 直角三角形ABC的斜边BC的长为a,将它分成 n 等份(n为奇数),令?为从A点向中间的那一小段线段所张的锐角,从A到BC边的高长为h,求证: tan ? = 4nh/(an2 - a). 4.? 已知从A、B引出的高线长度以及从A引出的中线长,求作三角形ABC。 5.? 正方体ABCDA'B'C'D'(上底面ABCD,下底面A'B'C'D')。X是对角线AC上任意一点,Y是B'D'上任意一点。 a.求XY中点的轨迹; b.求(a)中轨迹上的、并且还满足 ZY=2XZ的点Z的轨迹。 6.? 一个圆锥内有一内接球,又有一圆柱体外切于此圆球,其底面落在圆锥的底面上。令V1为圆锥的体积,V2为圆柱的体积。 ??? (a).? 求证:V1不等于 V2; ??? (b).? 求V1/V2的最小值;并在此情况下作出圆锥顶角的一般。 7.? 等腰梯形ABCD,AB平行于DC,BC=AD。令AB=a,CD=c,梯形的高为 h。X点在对称轴上并使得角BXC、AXD都是直角。试作出所有这样的X点并计算X到两底的距离;再讨论在什么样的条件下这样的X点确实存在。 第3届IMO 1.? 设a、b是常数,解方程组 x + y + z = a; ? ? x2 + y2 + z2 = b2; ? ? xy=z2 并求出若使x、y、z是互不相同的正数,a、b应满足什么条件? 2.? 设a、b、c是某三角形的边,A 是其面积,求证: a2 + b2 + c2>= 4√3 A. 并求出等号何时成立。 3.? 解方程 cos n x - sin n x = 1, 其中n是一个自然数。 4.? P是三角形ABC内部一点,PA交BC于D,PB交AC于E,PC交AB于F,求证AP/PD,

初等数论习题解答

《初等数论》习题解答 作业3 一.选择题 1,B 2,C 3,D 4,A 二.填空题 1,自反律 2,对称性 3,13 4,十进位 5,3 6, 2 7,1 三.计算题 1, 解:由Euler 定理知:(a,m )=1 则 a φ (m)≡1 (mod m) ∵(3,100)=1. 3φ (100)=340≡1 3360≡1 3364=3360×34≡34 (mod 100) ∴34≡81 (mod 100) 故:3364的末两位数是81. 2, 解:132=169≡4 (mod 5) 134=16≡1 (mod 5) 1316≡1 (mod 5) 1332≡1 (mod 5) 1348≡1 (mod 5) 1350=1348×132 1350≡132≡4 (mod 5) 3, 解: ∵(7,9)=1. ∴只有一个解 7X -5≡9Y (mod 9) 7X -9Y ≡5 (mod 9) 解之得:X=2,Y=1 ∴X=2+9≡11=2 (mod 9) 4, 解: ∵(24,59)=1 ∴只有一个解 24X ≡7 (mod 59) 59Y ≡﹣7 (mod 24) 11Y=﹣7 (mod 24) 24Z=7 (mod 11) 2Z=7 (mod 11) 11W=﹣7 (mod 2) W =﹣7 (mod 2) W=﹣1 (mod 2) Z=2 711+-= -2 Y=11 7242-?-=-5

X=247595+?-=2 288-=-12 =47(mod59) 5 解 ∵(45,132)=3,∴同余式有三个解。 45X ≡21(mod32) 15x ≡7 (mod44) 44y ≡-7 (mod15) 14y ≡-7 (mod15) 15z ≡-7 (mod14) z ≡7 (mod14) y= 14 7715-?=7 x=15 7744+?=21 ∴x=21+3 1322?=109 (mod132) x=21+31321?=65 (mod132) x=21 (mod132) 6、解 ∵(12,45)=3, ∴同余式有三个解。 4x+5≡0 (mod15) 4x ≡15y-5 由观察法:∴x=10, y=3 ∴x=10 (mod45) x=10+ 3 1×45=25 (mod45) x=10+32×45=40 (mod45) 7、解 37x=25 (mod107) 107y=-25 (mod37) 33y=-25 (mod37) 37z= -25 (mod37) 4z= 25 (mod37) 33w= -25 (mod37) w= -25 (mod37) w=3 z= 4 25333+?=31 y=33253137-?=33 1122=34 x=372534107+?=373633=99 ∴x=99 (mod321)

相关主题
相关文档 最新文档