江苏夏令营-初等数论

初等数论（一）江苏省南菁高级中学夏建新2009年江苏省高中数学奥林匹克夏令营一、奇偶性分析⑴奇数±奇数＝偶数；偶数±偶数＝偶数；奇数×奇数＝奇数；……⑵奇数的平方都可表示为8m＋1形式；偶数的平方都可表为8m或8m＋4的形式⑶任何一个正整数n，都可以写成n＝2ml的形式，其中m为非负整数，l为奇数。将全体整数分成两类，凡是2的倍数称为偶数，否则称为奇数。有如下性质：这些性质既简单又明显，然而它却能解决数学竞赛中的一些难题。1、在一条直线上相邻两点的距离都等于1的4个点上各有一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一只为中心跳到其对称点上。证明：无论跳动多少次后，四只青蛙所在的点中相邻两点之间的距离不能都等于2008。（2008年西部奥林匹克）如果若干次跳动后，青蛙所在位置中每相邻两只之间的距离都是2008，则要求它们处于具有相同奇偶性的位置上，不可能。证明：将青蛙放在数轴上讨论。不妨设最初四只青蛙所在的位置为1、2、3、4。注意到，处于奇数位置上的青蛙每次跳动后仍处于奇数位置上，处于偶数位置上的青蛙每次跳动后仍处于偶数位置上。因此，任意多次跳动后，四只青蛙中总有两只处于奇数位置上，另两只处于偶数位置上。2、如果可以将正整数1,2,3,…,n填在圆周上，使得依顺时针方向任何两个相邻的数之和，都能够被它们的下一个数整除。求n的所有可能值。（1999年环球城市竞赛）解：考虑n≥3情形当n≥3时，如果圆周上有二个连续偶数，则造成这个圆周上的每一个整数都是偶数(不合)。所以n最多是3，1,2,3这个数任意排在圆周上都可以，所以n＝3。因为圆周上必有一个整数是偶数，而它的逆时针方向的下二个数及顺时针方向的下个数，都必须是奇数。由于1～n中，奇数的个数最多比偶数的个数多1个，所以圆周上最多只有一个偶数，这样奇数有2个，3、已知t为正整数，若2t可以表示成ab±1(其中a,b是大于1的整数)，请找出满足上述条件所有可能的t值。（2008年青少年数学国际城市邀请赛）解：设正整数t，使得2t＝ab±1，显然a为奇数。(1)若b为奇数，则2t＝(a±1)(ab－1ab－2…a＋1)由于a，b均为奇数，而奇数个奇数相加或相减的结果一定是奇数，所以ab－1ab－2…a＋1也是奇数，得知2t＝ab±1＝a±1，故b=1，这与b≥2矛盾。从而只可能ab－1ab－2…a＋1＝1，综上可知，满足题设的2的正整数次幂是23，即t＝3。(2)若b为偶数，令b＝2m，则ab≡1(mod4)。若2t=ab+1，则2t=ab+1≡2(mod4)，从而t=1，故ab=21－1=1，矛盾。若2t=ab－1=(am－1)(am+1)，两个连续偶数之乘积为2的方幂只能是am－1=2，am+1=4，从而a＝3，b＝2m＝2。2t=ab－1=32－1=8。二、质数与合数大于1的整数按它具有因数的情况又可分为质数与合数两类。即对任一整数a＞1，有a＝，其中p1＜p2＜…＜pn均为质数，1、2、…、n都是正整数。nnppp2121另可得：a的正约数的个数为（1＋1）（2＋1）…（n＋1）⑴算术基本定理：任何一个大于1的整数都可以分解成质数的乘积。如果不考虑这些质因子的次序，则这种分解法是唯一的。⑵设n是大于2的整数，如果不大于的质数都不是n的因子，则n是质数。n4、设S＝{1,2,…,2005}.若S中任意n个两两互质的数组成的集合中都至少有一个质数，试求n的最小值.（2005年西部奥林匹克）解:首先,我们有n≥16。事实上,取集合A0＝{1,22,32,52,…,412,432}，SA0则,|A0|＝15,A0中任意两数互质,但其中无质数,这表明n≥16.SA其次,我们证明:对任意，n＝|A|＝16，A中任两数互质,则A中必存在一个质数.利用反证法,假设A中无质数.记A＝{a1,a2,…,a16}，分两种情况讨论.则a1≥p12≥22，a2≥p22≥32，…，a15≥p152≥472＞2005,矛盾.A1⑴若,则a1,a2,…,a16均为合数,又因为(ai,aj)＝1(1≤i＜j≤16),所以ai与aj的质因数均不相同,设ai的最小质因数为pi,不妨设p1＜p2＜…＜p16,由(1),(2)知,反设不成立,从而A中必有质数,即n＝|A|＝16时结论成立.⑵若1∈A,则不妨设a16＝1，a1,a2,…,a15均为合数,同(1)所设,同理有a1≥p12≥22，a2≥p22≥32，…，a15≥p152≥472＞2005,矛盾.综上,所求的n最小值为16.5、证明：对所有的非负整数n，＋1至少是2n＋3个质数（不一定互不相同）的乘积。（2007第36届美国数学奥林匹克）n77证明：⑴当n＝0时，＋1＝8＝23，结论成立n77⑵假设当n＝k时结论成立，即＋1至少是2k＋3个质数的乘积，k77当n＝k＋1时，只需证明，对m∈N*，记x＝72m－1，是一个合数117xx177k（这样，＋1至少是2k＋3＋2＝2(k＋1)＋3个质数的乘积）即是一个合数。结论成立。117xx117xx1)]1()1[()1(777xxxx＝(x＋1)6－1)13553(72345xxxxxxx＝(x＋1)6－7x(x4＋2x3＋3x2＋2x＋1)＝(x＋1)6－72m(x2＋x＋1)2＝[(x＋1)3－7m(x2＋x＋1)][(x＋1)3＋7m(x2＋x＋1)]要使上式两个因子都大于1，只需对较小的一个进行检验。注意到≤x，x7则(x＋1)3－7m(x2＋x＋1)＝(x＋1)3－(x2＋x＋1)x7≥x3＋3x2＋3x＋1－x(x2＋x＋1)＝2x2＋2x＋1＞1三、整除⑴带余除法：对于任一整数a和任一非零整数b，必有惟一的一对整数q和r，使得a＝bq＋r，0≤r＜b，且q和r由上述条件惟一确定。若r＝0，则称b|a。⑵部分性质：①若c|b，b|a，则c|a②若c|a，d|b，则cd|ab③若ma|mb，则a|b④若a＞0，b＞0，b|a，则b≤a⑤任意n个连续正整数的乘积必能被n！整除。⑶当（a，b）＝1时，称a、b互素（互质）。有：若另上条件（a，p）＝1，则p|ap－1－1①已知（a，c）＝1，若a|bc，则a|b；若a|b，c|b，则ac|b②p为质数，若p|ab，则p|a或p|b③[a，b]·（a，b）＝ab④（a，b）＝（a，b－ac）＝（a－bc，b）⑤（裴蜀定理）存在整数x、y，使ax＋by＝（a，b）⑥m（a，b）＝（ma，mb）⑦若（a，b）＝d，则（）＝1dbda,⑧若a|m，b|m，则[a，b]|m⑨费尔马小定理：p是素数，则p|ap－a定理：在n4k＋r（k，r为非负整数）中，0≤r＜4，则当r＝0（k≠0）时，n4k＋r的个位数字与n4的个位数字相同；当r≠0时，n4k＋r的个位数字与nr的个位数字相同。①个位数字只能是：0，1，4，5，6，9②末两位数字不可能同时为奇数。③偶数的平方是偶数，且被4整除；奇数的平方是奇数，且被4除余1。④在n2与（n＋1）2之间不存在平方数。⑷个位数⑸平方数性质：7、求所有的正整数n，使n能被所有不大于的正整数整除。n得k＝3或4或5∴n＜36。解：设k2≤n＜(k＋1)2,当k≥3时,1|n,2|n,…,k|n∵(k－2，k－1)＝1，(k－1，k)＝1，(k－2，k)≤2，即k3―5k2―2k―2＜0，(k2－2)(k－5)＜12，综上，本题的解为1,2,3,4,6,8,12,24当1≤n＜4时，有1|n，n＝1,2,3都满足条件当4≤n＜9时，有1|n，2|n，n＝4,6,8都满足条件当9≤n＜16时，有1|n，2|n，3|n，∴n＝12同理，当16≤n＜25时，n＝24，当25≤n＜36时，无n满足条件故k(k－1)(k－2)≤n＜(k＋1)221∴k(k－1)(k－2)|n，218、已知2009|[]＋1(a∈N)，求a的值。a22009解：当a＝2010时，＝2008＋，a2200920101∴[]＋1＝2009，成立a22009当a≥2011时，≤a22009201120092＝2008－20112007＜2008∴[]＋1≤2008a22009故2009|[]＋1不成立a22009∴a＝2010当a≤2009时，设[]＋1＝2009k，a22009则[]＝2009k－1，a22009∴2009k－1≤＜2009ka22009一方面，＜2009k得2009＜ka，a22009即ka≥2010，k≥a2010∴2009k－1≥·2009－1a2010aa200920092≥a22009但2009k－1≤a22009∴2009k－1＝·2009－1a2010aa200920092＝a22009故a＝2009但此时[]＋1＝2010，2009|[]＋1不成立a22009a220099、设a,b为正整数。证明：若4ab－1整除(4a2－1)2，则a＝b.（07年IMO－48）即a－b≥(a＋b)(4ab－1)＞a＋b,矛盾.证明：(4a2－1)2b2＝(a(4ab－1)＋a－b)2＝a2(4ab－1)2＋2a(a－b)(4ab－1)＋(a－b)2故由(4ab－1)|(4a2－1)2推出(4ab－1)|(a－b)2.反设有正整数a≠b满足(4ab－1)|(a－b)2,则必有一组这样的(a,b)使a＋b为最小。令(a－b)2＝k(4ab－1)不妨设a＞b.二次方程x2－(4k＋2)bx＋b2＋k＝0的一个根x1＝a另一根x2＝(4k＋2)b－a＝也是正整数akb2故(x2,b)也满足条件。由所设a＋b最小得到x2≥a，即k≥a2－b2。于是(a－b)2≥(a2－b2)(4ab－1),10、求所有的素数对（p，q），使得pq｜5p＋5q．(09CMO)故q｜626．由于q为奇素数，而626的奇素因子只有313，所以q＝313．解：若2｜pq，不妨设p＝2，则2q｜5p＋5q，故q｜5q＋25．由Fermat小定理，q｜5q－5，得q｜30，即q＝2，3，5．易验证素数对（2,2）不合要求，（2,3），（2,5）合乎要求．若pq为奇数且5｜pq，不妨设p＝5，则5q｜55＋5q，故q｜5q－1＋625．当q＝5时素数对（5,5）合乎要求，当q≠5时，由Fermat小定理有q｜5q－1－1，经检验素数对（5,313）合乎要求．综上所述，所有满足题目要求的素数对（p，q）为（2,3），（3,2），（2,5），（5,2）（5,5），（5,313）及（313,5）．若p，q都不等于2和5，则有pq｜5p－1＋5q－1，故5p－1＋5q－1≡0（modp）①由Fermat小定理，得5p－1≡1（modp）②故由①，②得5q－1≡－1（modp）③设p－1＝2k(2r－1)，q－1＝2l(2s－1)，其中k，l，r，s为正整数．若k≤l，则由②，③易知≡－1（modp）1≡)12(21skl≡(5q－1)2r－1)12(21)5(spkl)12)(12(25srl这与p≠2矛盾！所以k＞l．≡(－1)2r－1同理有k＜l，矛盾！即此时不存在合乎要求的(p,q)11、设n是一个正整数，定义(n)＝＝，例如（1）＝1，（2）＝11，（3）＝111．(1)设m是一个非负数．证明：(3m)可以被3m整除，而不能被3m＋1整除．(2)证明n能被27整除当且仅当（n）能被27整除（2008年日本东京大学入学考试题）9110n1111111个n结合归纳假设，得3k＋1||（3k＋1）。综上，原命题成立。(1)m＝0时，（30）＝（1）＝1，30||（30）；m＝1时，（31）＝111，31||（31）。假设m＝k时，3k||（3k）。则m＝k＋1时，(3k＋1)＝（3k）×（＋1）kk3321010其中＋1≡3(mod9)，kk3321010故27|（27）。从而27|(n)。（2）首先证明：若27|n，则27|(n)。设n