江苏夏令营初等数论课件.ppt

1、初等数论（一）初等数论（一）江苏省南菁高级中学夏建新江苏省南菁高级中学夏建新 20092009年江苏省高中数学奥林匹克夏令营年江苏省高中数学奥林匹克夏令营-一、奇偶性分析一、奇偶性分析 奇数奇数奇数偶数；偶数奇数偶数；偶数偶数偶数；奇数偶数偶数；奇数奇数奇数；奇数奇数；奇数的平方都可表示为奇数的平方都可表示为8m1形式；偶数的平形式；偶数的平方都可表为方都可表为8m或或8m4的形式的形式任何一个正整数任何一个正整数n，都可以写成，都可以写成n2ml的形式，的形式，其中其中m为非负整数，为非负整数，l为奇数。为奇数。将全体整数分成两类，凡是将全体整数分成两类，凡是2的倍数称为偶数，的倍数称为偶数

2、，否则称为奇数。有如下性质：否则称为奇数。有如下性质：这些性质既简单又明显，然而它却能解决数学竞这些性质既简单又明显，然而它却能解决数学竞赛中的一些难题。赛中的一些难题。-1、在一条直线上相邻两点的距离都等于、在一条直线上相邻两点的距离都等于1的的4个点上各有个点上各有一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一只为中心跳到其对称点上。证明：无论跳动多少次后，只为中心跳到其对称点上。证明：无论跳动多少次后，四只青蛙所在的点中相邻两点之间的距离不能都等于四只青蛙所在的点中相邻两点之间的距离不能都等于2008。（。（2008年西部奥林匹克）年西部

3、奥林匹克）如果若干次跳动后，青蛙所在位置中每相邻两只如果若干次跳动后，青蛙所在位置中每相邻两只之间的距离都是之间的距离都是2008，则要求它们处于具有相同，则要求它们处于具有相同奇偶性的位置上，不可能。奇偶性的位置上，不可能。证明：将青蛙放在数轴上讨论。证明：将青蛙放在数轴上讨论。不妨设最初四只青蛙所在的位置为不妨设最初四只青蛙所在的位置为1、2、3、4。注意到，处于奇数位置上的青蛙每次跳动后仍处注意到，处于奇数位置上的青蛙每次跳动后仍处于奇数位置上，处于偶数位置上的青蛙每次跳动于奇数位置上，处于偶数位置上的青蛙每次跳动后仍处于偶数位置上。后仍处于偶数位置上。因此，任意多次跳动后，四只青蛙中总

4、有两只处因此，任意多次跳动后，四只青蛙中总有两只处于奇数位置上，另两只处于偶数位置上。于奇数位置上，另两只处于偶数位置上。-2、如果可以将正整数、如果可以将正整数1,2,3,n填在圆周上，使得依顺填在圆周上，使得依顺时针方向任何两个相邻的数之和，都能够被它们的下一个时针方向任何两个相邻的数之和，都能够被它们的下一个数整除。求数整除。求n的所有可能值。（的所有可能值。（1999年环球城市竞赛）年环球城市竞赛）解：考虑解：考虑n 3情形情形 当当n3时，如果圆周上有二个连续偶数，则造时，如果圆周上有二个连续偶数，则造成这个圆周上的每一个整数都是偶数成这个圆周上的每一个整数都是偶数(不合不合)。所以

5、所以n最多是最多是3，1,2,3这个数任意排在圆周上都可这个数任意排在圆周上都可以，所以以，所以n3。因为圆周上必有一个整数是偶数，而它的逆时针因为圆周上必有一个整数是偶数，而它的逆时针方向的下二个数及顺时针方向的下个数，都必须方向的下二个数及顺时针方向的下个数，都必须是奇数。是奇数。由于由于1n中，奇数的个数最多比偶数的个数多中，奇数的个数最多比偶数的个数多1个，个，所以圆周上最多只有一个偶数，这样奇数有所以圆周上最多只有一个偶数，这样奇数有2个，个，-3、已知、已知t 为正整数，若为正整数，若2t可以表示成可以表示成ab1(其中其中a,b 是大是大于于1 的整数的整数)，请找出满足上述条件

6、所有可能的，请找出满足上述条件所有可能的t 值。值。（2008年青少年数学国际城市邀请赛）年青少年数学国际城市邀请赛）解：设正整数解：设正整数t，使得，使得2tab1，显然，显然a为奇数。为奇数。(1)若若b为奇数，则为奇数，则2t(a1)(ab1ab2a1)由于由于a，b均为奇数，而奇数个奇数相加或相减的均为奇数，而奇数个奇数相加或相减的结果一定是奇数，所以结果一定是奇数，所以ab1ab2a1也是也是奇数，奇数，得知得知2t ab1a1，故，故b=1，这与这与b2矛盾。矛盾。从而只可能从而只可能ab1ab2a11，-综上可知，满足题设的综上可知，满足题设的2 的正整数次幂是的正整数次幂是23

7、，即，即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。-二、质数与合数二、质数与合数 大于大于1 1的整数按它具有因数的情况又可分为质数的整数按它具有因数的情况又可分为质数与合数两类。与合数两类。即对任一整数即对任一整数a1，有，有a，其中，其中p1p2pn均为质数，均为质数，1

8、、2、n都是都是正整数。正整数。nnppp2121另可得：另可得：a的正约数的个数为（的正约数的个数为（11）（21）（n1）算术基本定理：任何一个大于算术基本定理：任何一个大于1的整数都可以分的整数都可以分解成质数的乘积。如果不考虑这些质因子的次序，解成质数的乘积。如果不考虑这些质因子的次序，则这种分解法是唯一的。则这种分解法是唯一的。设设n是大于是大于2的整数，如果不大于的质数都的整数，如果不大于的质数都不是不是n的因子，则的因子，则n是质数。是质数。n-4、设设S1,2,2005.若若S中任意中任意n个两两互质的数组成的个两两互质的数组成的集合中都至少有一个质数，试求集合中都至少有一个质

9、数，试求 n的最小值的最小值.（2005年西部年西部奥林匹克）奥林匹克）解解:首先首先,我们有我们有n16。事实上事实上,取集合取集合A01,22,32,52,412,432，SA 0则则,|A0|15,A0中任意两数互质中任意两数互质,但其中但其中无质数无质数,这表明这表明n16.SA 其次其次,我们证明我们证明:对任意对任意 ，n|A|16，A中中任两数互质任两数互质,则则A中必存在一个质数中必存在一个质数.利用反证法利用反证法,假设假设A中无质数中无质数.记记Aa1,a2,a16，分两种情况讨论分两种情况讨论.-则则a1p1222，a2p2232，a15p1524722005,矛盾矛盾.

10、A1若若 ,则则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.-5、证明：对所有的非负整数、证明：对所有

11、的非负整数n，1至少是至少是2n3个质数个质数（不一定互不相同）的乘积。（不一定互不相同）的乘积。（2007第第36届美国数学奥林届美国数学奥林匹克）匹克）n77证明：证明：当当n0时，时，1823，结论成立，结论成立n77假设当假设当nk时结论成立，即时结论成立，即 1至少是至少是2k3个质数的乘积，个质数的乘积，k77当当nk1时，只需证明，对时，只需证明，对mN*，记，记x72m1，是一个合数是一个合数117xx177k（这样，（这样，1至少是至少是2k322(k1)3个个质数的乘积）质数的乘积）-即是一个合数。结论成立。即是一个合数。结论成立。117xx117xx1)1()1()1(7

12、77xxxx(x1)61)13553(72345xxxxxxx(x1)67x(x42x33x22x1)(x1)672m(x2x1)2(x1)37m(x2x1)(x1)37m(x2x1)要使上式两个因子都大于要使上式两个因子都大于1，只需对较小的一个，只需对较小的一个进行检验。进行检验。注意到注意到x，x7则则(x1)37m(x2x1)(x1)3 (x2x1)x7x33x23x1x(x2x1)2x22x11-三、整除三、整除 带余除法带余除法：对于任一整数：对于任一整数a和任一非零整数和任一非零整数b，必有惟一的一对整数必有惟一的一对整数q和和r，使得，使得abqr，0rb，且，且q和和r由上述

13、条件惟一确定。由上述条件惟一确定。若若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）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）（）（

14、a，bac）（）（abc，b）（裴蜀定理）存在整数（裴蜀定理）存在整数x、y，使，使axby（a，b）m（a，b）（）（ma，mb）若（若（a，b）d，则（），则（）1dbda,若若a|m，b|m，则，则a，b|m费尔马小定理：费尔马小定理：p是素数，则是素数，则p|a pa-定理：在定理：在n4kr（k，r为非负整数）中，为非负整数）中，0r4，则当则当r0（k0）时，）时，n4kr的个位数字与的个位数字与n4的个的个位数字相同；当位数字相同；当r0时，时，n4kr的个位数字与的个位数字与nr的的个位数字相同。个位数字相同。个位数字只能是：个位数字只能是：0，1，4，5，6，9末两位数字不可

15、能同时为奇数。末两位数字不可能同时为奇数。偶数的平方是偶数，且被偶数的平方是偶数，且被4整除；奇数的平方是整除；奇数的平方是奇数，且被奇数，且被4除余除余1。在在n2与（与（n1）2之间不存在平方数。之间不存在平方数。个位数个位数平方数性质：平方数性质：-7、求所有的正整数求所有的正整数n，使，使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,

16、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)221 k(k1)(k2)|n，21-8、已知已知2009|1(aN)，求，求a的值。的值。a22009解：当解：当a2010时，时，2008 ，a2200920101 12009，成立，成立 a22009当当a2011时，时，a2200920112009220082011

17、20072008 1 2008 a22009故故2009|1不成立不成立a22009-a2010当当a2009时，设时，设 12009k，a22009则则 2009k1，a220092009k1 2009ka22009一方面，一方面，2009k得得2009ka，a22009即即ka2010，ka20102009k1 20091a2010aa200920092a22009但但2009k1 a220092009k1 20091a2010aa200920092a22009故故a2009但此时但此时12010，2009|1不成立不成立a22009a22009-9、设、设a,b为正整数为正整数。证明证明

18、：若若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 也是正整数也是正整数akb2故故(x

19、2,b)也满足条件。也满足条件。由所设由所设ab最小得到最小得到x2a，即，即ka2b2。于是于是(ab)2(a2b2)(4ab1),-10、求所有的素数对（、求所有的素数对（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为奇数且为

20、奇数且5pq，不妨设，不妨设p5，则则5q555q，故，故q5q1625当当q5时素数对（时素数对（5,5）合乎要求，）合乎要求，当当q5时，由时，由Fermat小定理有小定理有q5q11，经检验素数对（经检验素数对（5,313）合乎要求）合乎要求-综上所述，所有满足题目要求的素数对（综上所述，所有满足题目要求的素数对（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（m

21、od p）故由故由，得得5q11（mod p）设设p12k(2r1)，q12l(2s1)，其中其中k，l，r，s为正整数为正整数若若kl，则由，则由，易知易知1（mod p）1)12(21skl(5q1)2r1)12(21)5(spkl)12)(12(25srl这与这与p2矛盾！所以矛盾！所以kl(1)2r1同理有同理有kl，矛盾！即此时不存在合乎要求的，矛盾！即此时不存在合乎要求的(p,q)-11、设、设n是一个正整数，定义是一个正整数，定义(n)，例，例如（如（1）1，（，（2）11，（，（3）111(1)设设m是一个非负数证明：是一个非负数证明：(3m)可以被可以被3m整除，而不整除，而

22、不能被能被3m1整除整除(2)证明证明n能被能被27整除当且仅当（整除当且仅当（n）能被）能被27整除（整除（2008年年日本东京大学入学考试题）日本东京大学入学考试题）9110 n 1111111个n结合归纳假设，得结合归纳假设，得3k1|（3k1）。综上，原命题）。综上，原命题成立。成立。(1)m0时，（时，（30）（）（1）1，30|（30）；）；m1时，（时，（31）111，31|（31）。）。假设假设mk时，时，3k|（3k）。）。则则mk1时，时，(3k1)（3k）（1）kk3321010其中其中 13(mod 9)，kk3321010-故故27|（27）。从而）。从而27|(n)

23、。（2）首先证明：若）首先证明：若27|n，则，则27|(n)。设设n27k，则则(n)（27）102710kii而（而（27）（）（3）80310ii其中其中 0(mod 9)80310ii再证明：若再证明：若27|(n)，则，则27|n 9|3k，得，得27|9kn。证毕。证毕。9110 n 1111111个n27|得得n0(mod 9)设设n9k，则由则由35|109k1(103k1)(106k103k1)，及及106k103k13(mod 9)，得得34|103k19 9 13111111个k-12、对哪些、对哪些nN*,存在存在a,bQZ使得使得ab和和anbn都是都是整数整数?(克

24、罗地亚克罗地亚)但但xnznMy2nkxn-1y2xn,故必故必y|2xn.解解.当当n为奇数时，为奇数时，取取a,b31313 n由于由于1n(3n1)n被被1(3n1)3n整除整除.故故a,b满满足条件足条件.即即n可为任何大于可为任何大于0的奇数的奇数.当当n为偶数为偶数,若有满足条件的若有满足条件的a,b(x,y,z,wZ,y,w1,(x,y)(z,w)1).yxwz则由则由ab Zywyzxw 得到得到yw|(xwyz)但但(x,y)1,故故y|w.同理，同理，w|y.再由再由anbnZ得到得到yn|(xnzn).nnnyzx因此因此yw.zkyx.故故y|xw,所求的所求的n是大于是大于0的一切奇数的一切奇数.由由y1及及(x,y)1得到得到y2且且x为奇数为奇数.由于由于n是偶是偶数数,4|(My2nkxn-1y),从而从而4|2,矛盾矛盾.-14、存在。、存在。15、n1006009为其最大值。为其最大值。1616、略、略.1313、三元组有、三元组有70个。个。-练习答案：练习答案：1、432、173、m4m2m 4、略、略5、p3、5、13 6、ts11 7、n的最小值为的最小值为9-