江苏夏令营初等数论课件

初等数论（一）初等数论（一）江苏省南菁高级中学夏建新江苏省南菁高级中学夏建新 2009年江年江苏省高中数学奥林匹克夏令省高中数学奥林匹克夏令营-初等数论（一）江苏省南菁高级中学夏建新 2009年江苏省1一、奇偶性分析一、奇偶性分析 奇奇数数奇奇数数偶偶数数；偶偶数数偶偶数数偶偶数数；奇奇数数奇数奇数；奇数奇数；奇奇数数的的平平方方都都可可表表示示为为8m1形形式式；偶偶数数的的平平方都可表为方都可表为8m或或8m4的形式的形式任任何何一一个个正正整整数数n，都都可可以以写写成成n2ml的的形形式式，其中其中m为非负整数，为非负整数，l为奇数。为奇数。将全体整数分成两类，凡是将全体整数分成两类，凡是2的倍数称为偶数，的倍数称为偶数，否则称为奇数。有如下性质：否则称为奇数。有如下性质：这些性质既简单又明显，然而它却能解决数学竞这些性质既简单又明显，然而它却能解决数学竞赛中的一些难题。赛中的一些难题。-一、奇偶性分析 奇数奇数偶数；偶数偶数偶数；奇数21、在一条直线上相邻两点的距离都等于、在一条直线上相邻两点的距离都等于1的的4个点上各有个点上各有一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一只为中心跳到其对称点上。证明：无论跳动多少次后，只为中心跳到其对称点上。证明：无论跳动多少次后，四只青蛙所在的点中相邻两点之间的距离不能都等于四只青蛙所在的点中相邻两点之间的距离不能都等于2008。（。（2008年西部奥林匹克）年西部奥林匹克）如如果果若若干干次次跳跳动动后后，青青蛙蛙所所在在位位置置中中每每相相邻邻两两只只之之间间的的距距离离都都是是2008，则则要要求求它它们们处处于于具具有有相相同同奇偶性的位置上，不可能。奇偶性的位置上，不可能。证明：将青蛙放在数轴上讨论。证明：将青蛙放在数轴上讨论。不妨设最初四只青蛙所在的位置为不妨设最初四只青蛙所在的位置为1、2、3、4。注意到，处于奇数位置上的青蛙每次跳动后仍处注意到，处于奇数位置上的青蛙每次跳动后仍处于奇数位置上，处于偶数位置上的青蛙每次跳动于奇数位置上，处于偶数位置上的青蛙每次跳动后仍处于偶数位置上。后仍处于偶数位置上。因此，任意多次跳动后，四只青蛙中总有两只处因此，任意多次跳动后，四只青蛙中总有两只处于奇数位置上，另两只处于偶数位置上。于奇数位置上，另两只处于偶数位置上。-1、在一条直线上相邻两点的距离都等于1的4个点上各有一只青蛙32、如果可以将正整数、如果可以将正整数1,2,3,n填在圆周上，使得依顺填在圆周上，使得依顺时针方向任何两个相邻的数之和，都能够被它们的下一个时针方向任何两个相邻的数之和，都能够被它们的下一个数整除。求数整除。求n的所有可能值。（的所有可能值。（1999年环球城市竞赛）年环球城市竞赛）解：考虑解：考虑n 3情形情形 当当n3时，如果圆周上有二个连续偶数，则造成时，如果圆周上有二个连续偶数，则造成这个圆周上的每一个整数都是偶数这个圆周上的每一个整数都是偶数(不合不合)。所以所以n最多是最多是3，1,2,3这个数任意排在圆周上都可这个数任意排在圆周上都可以，所以以，所以n3。因为圆周上必有一个整数是偶数，而它的逆时针因为圆周上必有一个整数是偶数，而它的逆时针方向的下二个数及顺时针方向的下个数，都必须方向的下二个数及顺时针方向的下个数，都必须是奇数。是奇数。由于由于1n中，奇数的个数最多比偶数的个数多中，奇数的个数最多比偶数的个数多1个，个，所以圆周上最多只有一个偶数，这样奇数有所以圆周上最多只有一个偶数，这样奇数有2个，个，-2、如果可以将正整数1,2,3,n填在圆周上，43、已知、已知t 为正整数，若为正整数，若2t可以表示成可以表示成ab1(其中其中a,b 是大是大于于1 的整数的整数)，请找出满足上述条件所有可能的，请找出满足上述条件所有可能的t 值。值。（2008年青少年数学国际城市邀请赛）年青少年数学国际城市邀请赛）解：设正整数解：设正整数t，使得，使得2tab1，显然，显然a为奇数。为奇数。(1)若若b为奇数，则为奇数，则2t(a1)(ab1ab2a1)由于由于a，b均为奇数，而奇数个奇数相加或相减的均为奇数，而奇数个奇数相加或相减的结果一定是奇数，所以结果一定是奇数，所以ab1ab2a1也是也是奇数，奇数，得知得知2t ab1a1，故，故b=1，这与这与b2矛盾。矛盾。从而只可能从而只可能ab1ab2a11，-3、已知t 为正整数，若2t可以表示成ab1(其中a,b5综综上上可可知知，满满足足题题设设的的2 的的正正整整数数次次幂幂是是23，即即t3。(2)若若b为偶数，令为偶数，令b2m，则则ab1(mod 4)。若若2t=ab+1，则则2t=ab+12(mod 4)，从而从而t=1，故，故ab=211=1，矛盾。，矛盾。若若2t=ab1=(am1)(am+1)，两个连续偶数之乘积为两个连续偶数之乘积为2的方幂只能是的方幂只能是am1=2，am+1=4，从而从而a3，b2m2。2t=ab1=321=8。-综上可知，满足题设的2 的正整数次幂是23，即t3。(2)6二、质数与合数二、质数与合数 大于大于1 1的整数按它具有因数的情况又可分为质数的整数按它具有因数的情况又可分为质数与合数两类。与合数两类。即即对对任任一一整整数数a1，有有a，其其中中p1p2pn均均为为质质数数，1、2、n都都是是正正整数。整数。另可得：另可得：a的正约数的个数为（的正约数的个数为（11）（21）（n1）算术基本定理：任何一个大于算术基本定理：任何一个大于1的整数都可以分的整数都可以分解成质数的乘积。如果不考虑这些质因子的次序，解成质数的乘积。如果不考虑这些质因子的次序，则这种分解法是唯一的。则这种分解法是唯一的。设设n是大于是大于2的整数，如果不大于的质数都不的整数，如果不大于的质数都不是是n的因子，则的因子，则n是质数。是质数。-二、质数与合数 大于1的整数按它具有因数的情况又可分为质数与74、设设S1,2,2005.若若S中任意中任意n个两两互质的数组个两两互质的数组成的集合中都至少有一个质数，试求成的集合中都至少有一个质数，试求 n的最小值的最小值.（2005年年西部奥林匹克）西部奥林匹克）解解:首先首先,我们有我们有n16。事实上事实上,取集合取集合A01,22,32,52,412,432，则则,|A0|15,A0中任意两数互质中任意两数互质,但其中但其中无质数无质数,这表明这表明n16.其次其次,我们证明我们证明:对任意对任意 ，n|A|16，A中中任两数互质任两数互质,则则A中必存在一个质数中必存在一个质数.利用反证法利用反证法,假设假设A中无质数中无质数.记记Aa1,a2,a16，分两种情况讨论，分两种情况讨论.-4、设S1,2,2005.若S中任意n个两两互质8则则 a1p1222，a2p2232，a15p1524722005,矛盾矛盾.若若 ,则则a1,a2,a16均为合数均为合数,又因为又因为(ai,aj)1(1ij16),所以所以ai与与aj的质因数的质因数均不相同均不相同,设设ai的最小质因数为的最小质因数为pi,不妨设不妨设p1p2p16,由由(1),(2)知知,反反设设不不成成立立,从从而而A中中必必有有质质数数,即即n|A|16时结论成立时结论成立.若若1A,则不妨设则不妨设a161，a1,a2,a15均为合数均为合数,同同(1)所设所设,同理有同理有a1p1222，a2p2232，a15p1524722005,矛盾矛盾.综上综上,所求的所求的n最小值为最小值为16.-则a1p1222，a2p2232，a15p1595、证证明明：对对所所有有的的非非负负整整数数n，1至至少少是是2n3个个质质数数（不不一一定定互互不不相相同同）的的乘乘积积。（2007第第36届届美美国国数数学学奥奥林林匹克）匹克）证明：证明：当当n0时，时，1823，结论成立，结论成立假设当假设当nk时结论成立，即时结论成立，即 1至少是至少是2k3个质数的乘积，个质数的乘积，当当nk1时，只需证明，对时，只需证明，对mN*，记，记x72m1，是一个合数是一个合数（这样，（这样，1至少是至少是2k322(k1)3个个质数的乘积）质数的乘积）-5、证明：对所有的非负整数n，1至少是2n3个质数（不10即是一个合数。结论成立。即是一个合数。结论成立。(x1)6(x1)67x(x42x33x22x1)(x1)672m(x2x1)2(x1)37m(x2x1)(x1)37m(x2x1)要使上式两个因子都大于要使上式两个因子都大于1，只需对较小的一个，只需对较小的一个进行检验。进行检验。注意到注意到x，则则(x1)37m(x2x1)(x1)3 (x2x1)x33x23x1x(x2x1)2x22x11-即是一个合数。结论成立。(x1)6(x1)11三、整除三、整除 带带余余除除法法：对对于于任任一一整整数数a和和任任一一非非零零整整数数b，必必有有惟惟一一的的一一对对整整数数q和和r，使使得得abqr，0rb，且，且q和和r由上述条件惟一确定。由上述条件惟一确定。若若r0，则称，则称b|a。部分性质部分性质：若若c|b，b|a，则，则c|a 若若c|a，d|b，则，则cd|ab若若ma|mb，则，则a|b 若若a0，b0，b|a，则，则ba任意任意n个连续正整数的乘积必能被个连续正整数的乘积必能被n！整除。！整除。-三、整除 带余除法：对于任一整数a和任一非零整数b，必有惟12当（当（a，b）1时，称时，称a、b互素（互质）互素（互质）。有：。有：若另上条件（若另上条件（a，p）1，则，则p|a p11已知（已知（a，c）1，若，若a|bc，则，则a|b；若；若a|b，c|b，则，则ac|bp为质数，若为质数，若p|ab，则，则p|a或或p|ba，b（a，b）ab（a，b）（）（a，bac）（）（abc，b）（裴蜀定理）存在整数（裴蜀定理）存在整数x、y，使，使axby（a，b）m（a，b）（）（ma，mb）若（若（a，b）d，则（），则（）1若若a|m，b|m，则，则a，b|m费尔马小定理：费尔马小定理：p是素数，则是素数，则p|a pa-当（a，b）1时，称a、b互素（互质）。有：若另上条件13定理：在定理：在n4kr（k，r为非负整数）中，为非负整数）中，0r4，则当则当r0（k0）时，）时，n4kr的个位数字与的个位数字与n4的个的个位数字相同；当位数字相同；当r0时，时，n4kr的个位数字与的个位数字与nr的的个位数字相同。个位数字相同。个位数字只能是：个位数字只能是：0，1，4，5，6，9末两位数字不可能同时为奇数。末两位数字不可能同时为奇数。偶偶数数的的平平方方是是偶偶数数，且且被被4整整除除；奇奇数数的的平平方方是是奇数，且被奇数，且被4除余除余1。在在n2与（与（n1）2之间不存在平方数。之间不存在平方数。个位数个位数平方数性质：平方数性质：-定理：在n4kr（k，r为非负整数）中，0r4，则当r147、求所有的正整数求所有的正整数n，使，使n能被所有不大于的正整数整能被所有不大于的正整数整除。除。得得k3或或4或或5 n36。解：设解：设k2n(k1)2,当当k3时时,1|n,2|n,k|n(k2，k1)1，(k1，k)1，(k2，k)2，即即k35k22k20，(k22)(k5)12，综上，本题的解为综上，本题的解为1,2,3,4,6,8,12,24 当当1n4时，有时，有1|n，n1,2,3都满足条件都满足条件当当4n9时，有时，有1|n，2|n，n4,6,8都满足条件都满足条件当当9n16时，有时，有1|n，2|n，3|n，n12同理，当同理，当16n25时，时，n24，当当25n36时，时，无无n满足条件满足条件故故 k(k1)(k2)n(k1)2 k(k1)(k2)|n，-7、求所有的正整数n，使n能被所有不大于的正整数整除。得158、已知已知2009|1(aN)，求，求a的值。的值。解：当解：当a2010时，时，2008 ，12009，成立，成立 当当a2011时，时，20082008 1 2008 故故2009|1不成立不成立-8、已知2009|1(aN)，求a的值。解：16a2010当当a2009时，设时，设 12009k，则则 2009k1，2009k1 2009k一方面，一方面，2009k得得2009ka，即即ka2010，k2009k1 20091但但2009k1 2009k1 20091故故a2009但此时但此时12010，2009|1不成立不成立-a2010当a2009时，设 1179、设、设a,b为正整数为正整数。证明证明：若若4ab1整除整除(4a21)2，则则ab.（07年年IMO48）即即ab(ab)(4ab1)ab,矛盾矛盾.证明：证明：(4a21)2b2(a(4ab1)ab)2a2(4ab1)22a(ab)(4ab1)(ab)2故由故由(4ab1)|(4a21)2 推出推出(4ab1)|(ab)2.反设有正整数反设有正整数ab 满足满足(4ab1)|(ab)2,则必有一组这样的则必有一组这样的(a,b)使使ab为最小。为最小。令令(ab)2k(4ab1)不妨设不妨设ab.二次方程二次方程x2(4k2)bxb2k0的一个根的一个根x1a另一根另一根x2(4k2)ba 也是正整数也是正整数故故(x2,b)也满足条件。也满足条件。由所设由所设ab最小得到最小得到x2a，即，即ka2b2。于是于是(ab)2(a2b2)(4ab1),-9、设a,b为正整数。证明：若4ab1整除(4a21)21810、求所有的素数对（、求所有的素数对（p，q），使得），使得pq5p5q(09CMO)故故q626由由于于q为为奇奇素素数数，而而626的的奇奇素素因因子子只只有有313，所以，所以q313解：若解：若2pq，不妨设，不妨设p2，则，则2q5p5q，故，故q5q25由由Fermat小定理，小定理，q5q5，得，得q30，即即q2，3，5易验证素数对（易验证素数对（2,2）不合要求，（）不合要求，（2,3），），（2,5）合乎要求）合乎要求若若pq为奇数且为奇数且5pq，不妨设，不妨设p5，则则5q555q，故，故q5q1625当当q5时素数对（时素数对（5,5）合乎要求，）合乎要求，当当q5时，由时，由Fermat小定理有小定理有q5q11，经检验素数对（经检验素数对（5,313）合乎要求）合乎要求-10、求所有的素数对（p，q），使得pq5p5q(0919综综上上所所述述，所所有有满满足足题题目目要要求求的的素素数数对对（p，q）为为（2,3），（3,2），（2,5），（5,2）（5,5），（5,313）及（）及（313,5）若若p，q都不等于都不等于2和和5，则有，则有pq5p15q1，故故5p15q10（mod p）由由Fermat小定理，得小定理，得5p11（mod p）故由故由，得得5q11（mod p）设设p12k(2r1)，q12l(2s1)，其中其中k，l，r，s为正整数为正整数若若kl，则由，则由，易知易知1（mod p）1(5q1)2r1这与这与p2矛盾！所以矛盾！所以kl(1)2r1同理有同理有kl，矛盾！即此时不存在合乎要求的，矛盾！即此时不存在合乎要求的(p,q)-综上所述，所有满足题目要求的素数对（p，q）为（2,3），（2011、设设n是是一一个个正正整整数数，定定义义(n)，例例如（如（1）1，（，（2）11，（，（3）111(1)设设m是是一一个个非非负负数数证证明明：(3m)可可以以被被3m整整除除，而而不不能被能被3m1整除整除(2)证明证明n能被能被27整除当且仅当（整除当且仅当（n）能被）能被27整除（整除（2008年年日本东京大学入学考试题）日本东京大学入学考试题）结结合合归归纳纳假假设设，得得3k1|（3k1）。综综上上，原原命命题题成立。成立。(1)m0时，（时，（30）（）（1）1，30|（30）；）；m1时，（时，（31）111，31|（31）。）。假设假设mk时，时，3k|（3k）。）。则则mk1时，时，(3k1)（3k）（1）其中其中 13(mod 9)，-11、设n是一个正整数，定义(n)21故故27|（27）。从而）。从而27|(n)。（2）首先证明：若）首先证明：若27|n，则，则27|(n)。设设n27k，则则(n)（27）而（而（27）（）（3）其中其中 0(mod 9)再证明：若再证明：若27|(n)，则，则27|n 9|3k，得，得27|9kn。证毕。证毕。27|得得n0(mod 9)设设n9k，则由则由35|109k1(103k1)(106k103k1)，及，及106k103k13(mod 9)，得得34|103k19 9-故27|（27）。从而27|(n)。（2）首先证明：若272212、对哪些、对哪些nN*,存在存在a,bQZ使得使得ab和和anbn都是整都是整数数?(克罗地亚克罗地亚)但但xnznMy2nkxn-1y2xn,故必故必y|2xn.解解.当当n为奇数时，为奇数时，取取a,b由于由于1n(3n1)n被被1(3n1)3n整除整除.故故a,b满足条件满足条件.即即n可为任何大于可为任何大于0的奇数的奇数.当当n为偶数为偶数,若有满足条件的若有满足条件的a,b(x,y,z,wZ,y,w1,(x,y)(z,w)1).则由则由ab Z 得到得到yw|(xwyz)但但(x,y)1,故故y|w.同理，同理，w|y.再由再由anbnZ得到得到yn|(xnzn).因此因此yw.zkyx.故故y|xw,所求的所求的n是大于是大于0的一切奇数的一切奇数.由由y1及及(x,y)1得到得到y2且且x为奇数为奇数.由于由于n是偶是偶数数,4|(My2nkxn-1y),从而从而4|2,矛盾矛盾.-12、对哪些nN*,存在a,bQZ使得ab和anb2314、存在。、存在。15、n1006009为其最大值。为其最大值。1616、略、略.1313、三元组有、三元组有70个。个。-14、存在。15、n1006009为其最大值。16、略.24练习答案：练习答案：1、432、173、m4m2m 4、略、略5、p3、5、13 6、ts11 7、n的最小值为的最小值为9-练习答案：-25