夏建新--初等数论

《夏建新--初等数论》由会员分享，可在线阅读，更多相关《夏建新--初等数论（4页珍藏版）》请在装配图网上搜索。

1、2012年江苏省高中数学奥林匹克夏令营初等数论江苏省南菁高级中学 夏建新一、整除带余除法：对于任一整数a和任一非零整数b，必有惟一的一对整数q和r，使得abqr，0rb，且q和r由上述条件惟一确定。若r0，则称b | a。部分性质：若c | b，b | a，则c | a 若c | a，d | b，则cd | ab若c | a，c | b，则c |（kanb）；若c | a，c b，则c （ab）若ma | mb，则a | b 若a0，b0，b | a，则ba若nN*，则（ab）|（anbn）。若n为奇数，则（ab）|（anbn）。若n为偶数，则（ab）|（anbn）任意n个连续正整数的乘积必能

2、被n！整除。当（a，b）1时，称a、b互素（互质）。有：已知（a，c）1，若a | bc，则a | b；若a | b，c | b，则ac | bp为质数，若p | ab，则p | a或p | b a，b（a，b）ab（a，b）（a，bac）（abc，b）对任何整数c成立（裴蜀定理）存在整数x、y，使axby（a，b）m（a，b）（ma，mb） 若（a，b）d，则1若a | m，b | m，则a，b | m ma，bma，mb费尔马小定理：p是素数，则p|apa 若另上条件（a，p）1，则p|ap11例1、求所有的正整数n，使得8nn可以被2nn整除。（2009年日本数学奥林匹克）例2、设nm1

3、，m、n为整数，证明：C为整数。（2000年普特南）例3、求所有的正整数n，使n能被所有不大于的正整数整除。例4、已知a，b，c为两两互质的正整数，且a2|(b3c3)，b2|(a3c3)，c2|(a3b3)，求a，b，c的值（2011年东南数学奥林匹克）例5、求有序三元正整数组（a，b，c）的个数，其中a，b1000，b，c2000，a，c2000。（x，y表示x、y的最小公倍数）例6、证明：对所有的非负整数n，71至少是2n3个质数（不一定互不相同）的乘积。（2007年第36届美国数学奥林匹克）例7、是否存在奇数n（n3）及n个互不相同的质数p1，p2，pn，使得pipi1（i1，2，n，

4、pn1p1）都是完全平方数？请证明你的结论。（2011年中国西部数学奥林匹克）二、同余1、定义：设m是正整数，叫做模，若m|（ab），称a，b对模m同余，记作ab（mod m）2、性质：aa（mod m） 若ab（mod m），则ba（mod m）若ab（mod m），bc（mod m），则ac（mod m）若ab（mod m），cd（mod m），则acbd（mod m），acbd（mod m）若n|m，ab（mod m），则ab（mod n）若（m，n）1，ab（mod m），ab（mod n），则ab（mod mn）若ab（mod m），nN*，则a nb n（mod m）若acbc（m

5、od m），（c，m）d，则ab（mod ）费尔马小定理：p是素数，则a pa（mod p） 若另上条件（a，p）1，则a p11（mod p）3、剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类。 剩余类的结构很简单，设A是余数为r的剩余类，则Aqmr|m是模，r是余数，q0，1，2， 设A1、A2、Am是模m的m个剩余类，从Ai中取一数ai，则a1，a2，am称为模m的一个完全剩余系，简称m的完系。例8、证明：不存在正整数x，y满足x3y322009。（2009年巴西数学奥林匹克）例9、证明：对任意质数p，存在无限多个形如2 nn的数被p整除。例10、已知p是奇素数，证明：（第

6、36届加拿大数学奥林匹克）例11、求所有的素数对（p，q），使得pq|5p5q（2009年CMO）例12、试确定具有下述性质的所有正整数n：集合Mn，n1，n2，n3，n4，n5可以分成两个不相交的非空子集，使得一个子集中所有元素的积等于另一子集的所有元素之积。（第12届IMO）三、不定方程例13、将棱长为某整数的正方体切割成99个小正方体，其中98个是棱长为1的正方体，另一个正方体的棱长也是整数，求原正方体的棱长。例14、求所有满足方程32m1n2的正整数对(m，n)（2009年新加坡数学奥林匹克）例15、求所有的正整数a、b、c，其中1abc，使得(a1)(b1)(c1)是abc1的约数。

7、（第33届IMO）四、其它1、高斯函数定义：x表示不超过x的最大整数，通常称yx为取整函数，也称高斯函数，记xxx，yx称为x的小数部分函数。性质：xxxx1xxx1，0x1 yx是不减函数，即若x1x2，则x1x2 若nZ，则xnxn，xnx xyxyxy1。特别地，n（nN*）若x，y0，则xyxy。特别地，nx（nN*）若nN*，则在n!的素因数分解的标准式中，素因数p的最高次幂的次数为：例16、x表示不超过x的最大整数，xxx。解方程x x2005x（2005年第15届泛非数学奥林匹克）例17、设n是正整数，a（其中，x表示不超过x的最大整数）。求同时满足下列条件的n的最大值：n不是完

8、全平方数；a3|n2（第三届北方数学奥林匹克）2、数的进位制：给定一个m位正整数A，其各位上的数字分别记为an,an1,a1,a0，此数可简记为A(其中an0)即Aan10nan110n1a110a0，其中ai0,1,2,9，i0,1,2,3,n，an0.A可简记为：A(anan1a1a0)10，对于10进制正整数，通常将下角码10省略不写，括号也不写。整数的表示除十进制外，二进制、八进制等p进位制的记数法已被广泛采用。p进制记数法的基本原则是：“逢p进1”。一般地，正整数A的进位制表示：给定一个自然数p，将任一正整数A唯一地表示成上述形式：Aanpnan1pn1a1pa0，其中ai0,1,2

9、, p1，i0,1,2,3,n，an0.n为十进制数，可简记为：A(anan1a1a0) p.十进制数化为p进制数的方法：除以p将余数倒过来写即可。p（非10）进制数化为十进制数：直接化，(anan1a1a0) panpnan1pn1a1pa0.不同进位制之间相互转化常用十进制进行过渡。例18、记集合T0，1，2，3，4，5，6，M|aiT，i1，2，3，4，将M中的元素按从大到小的顺序排列，则第2005个数是 （2005年全国高中数学联赛）例19、对于正整数n，令fn2n2n求证：数列f1，f2，中有无穷多个奇数和无穷多个偶数(x表示不超过x的最大整数) （2008年第七届中国女子数学奥林匹

10、克）练习1、求正整数n，使得log31log32log33log34log3n2007，其中x表示不超过x的最大整数（2007年上海市TI杯高二年级数学竞赛）2、n为正整数，证明：120n(n21)(n25n26)3、对哪些nN*,存在a,bQZ使得ab和anbn都是整数? (克罗地亚)4、设三角形的三边分别是整数l，m，n，且lmn，已知，其中xxx，而x表示不超过x的最大整数求这种三角形周长的最小值（2003年全国高中数学联合竞赛）5、设n是一个正整数，定义：（n），例如（1）1，（2）11，（3）111(1)设m是一个非负数证明：(3m)可以被3m整除，而不能被3m1整除n个n个n个n个

11、(2)证明n能被27整除当且仅当（n）能被27整除（2008年日本东京大学入学考试题）6、证明存在正整数n使19871119998887777、证明：如果正整数n使方程x33xy2y3n有一组整数解（x，y），则这个方程至少有三组整数解。当n2891时，上述方程无整数解。（23届IMO）8、设n是正整数，记n！12n。求方程2011的所有正整数解（a表示不超过a的最大整数）。（2011年北京市中学生数学竞赛复赛）9、在三进制中，数x的表示是12112211122211112222，则x在9进制中表示式中最左边一位是什么数？10、在1，2，2k+11中，有些数写成二进制时数字和为偶数，求这些数的

12、和。参考答案：1、因log31log320，即log31log320，log33log34log38616，log39log310log32618236，log327log328log380543162，log381log382log32421624648，log3243log3244log3728486524302007所以，243n728。于是，636162648(n242)52007，解得n4732、1202335，n(n21)(n25n26)20 (n1)n(n1)(n3)(n2) (n1)n(n1)3!(n1)n(n1)，12020 (n1)n(n1)5!(n3)(n2) (n1)n

13、(n1)，即120(n3)(n2) (n1)n(n1)120n(n21)(n25n26)3、当n为奇数时,取a,b.由于1n(3n1)n被1(3n1)3n整除.故a,b满足条件.即n可为任何大于1的奇数. 设n为偶数,若有满足条件的a,b (x,y,z,wZ,y,w1,(x,y)(z,w)1).则由abZ得到yw|(xwyz),y|xw,但(x,y)1,故y|w.同理，w|y.因此yw.zkyx.再由anbnZ得到yn|(xnzn).但xnznMy2nkxn-1y2xn,故必y|2xn.由y1及(x,y)1得到y2且x为奇数.由于n是偶数,4|(My2nkxn-1y),从而4|2,矛盾.所求的

14、n是大于1的一切奇数.4、当s1，r2，n501时三角形的周长最小，其值为30035、（2）提示：首先证明：若27|n，则27|(n)。设n27k，则(n)（27）。再证明：若27|(n)，则27|n。27|(n)，即35|（10n1）。6、提示：首先证明存在正整数n，使1987111。（n个1）。另一方面，111999888777111103n9111102n811110n7111111（103n9102n810n7）。由1987111知结论成立。7、因（yx）33（yx）x2(x）3x33xy2y3，（x，y）为方程x33xy2y3n的整数解时，（yx，x）也是解。将yx当作x，x当作y，

15、则由于（x）（yx）y，（yx）xy，故（y，xy）也是方程的解。这三组解互不相同，因任两组相同将导出xy0与n为正整数相矛盾。若x33xy2y32891，则x33xy2y32（mod 9），从而x、y不能都被3整除。若x、y中恰有一个被3整除，用（yx，x）或（y，xy）代替（x，y）。因此可假定x、y都不被3整除，从而x31。y31，3xy23（mod 9），矛盾。8、所求为x1720312032436120111729、329，将x的三进制表示的数一对对地组合，得x(13192318)(13171316)(2312)(132)(32)9(131)(32)8(232)5994988x的九进制的第一个数字是5。10、所求的和为（122k11）2 2k2k1