江蘇夏令營-初等數(shù)論

1、初等數(shù)論（一）,江蘇省南菁高級中學夏建新,2009年江蘇省高中數(shù)學奧林匹克夏令營,一、奇偶性分析,奇數(shù)奇數(shù)偶數(shù)；偶數(shù)偶數(shù)偶數(shù)；奇數(shù)奇數(shù)奇數(shù)；奇數(shù)的平方都可表示為8m1形式；偶數(shù)的平方都可表為8m或8m4的形式任何一個正整數(shù)n，都可以寫成n2ml的形式，其中m為非負整數(shù)，l為奇數(shù)。,將全體整數(shù)分成兩類，凡是2的倍數(shù)稱為偶數(shù)，否則稱為奇數(shù)。有如下性質(zhì)：,這些性質(zhì)既簡單又明顯，然而它卻能解決數(shù)學競賽中的一些難題。,1、在一條直線上相鄰兩點的距離都等于1的4個點上各有一只青蛙，允許任意一只青蛙以其余三只青蛙中的某一只為中心跳到其對稱點上。證明：無論跳動多少次后，四只青蛙所在的點中相鄰兩點之間的距離不能

2、都等于2008。（2008年西部奧林匹克）,如果若干次跳動后，青蛙所在位置中每相鄰兩只之間的距離都是2008，則要求它們處于具有相同奇偶性的位置上，不可能。,證明：將青蛙放在數(shù)軸上討論。,不妨設最初四只青蛙所在的位置為1、2、3、4。,注意到，處于奇數(shù)位置上的青蛙每次跳動后仍處于奇數(shù)位置上，處于偶數(shù)位置上的青蛙每次跳動后仍處于偶數(shù)位置上。,因此，任意多次跳動后，四只青蛙中總有兩只處于奇數(shù)位置上，另兩只處于偶數(shù)位置上。,2、如果可以將正整數(shù)1,2,3,n填在圓周上，使得依順時針方向任何兩個相鄰的數(shù)之和，都能夠被它們的下一個數(shù)整除。求n的所有可能值。（1999年環(huán)球城市競賽）,解：考慮n3情形,當

3、n3時，如果圓周上有二個連續(xù)偶數(shù)，則造成這個圓周上的每一個整數(shù)都是偶數(shù)(不合)。,所以n最多是3，1,2,3這個數(shù)任意排在圓周上都可以，所以n3。,因為圓周上必有一個整數(shù)是偶數(shù)，而它的逆時針方向的下二個數(shù)及順時針方向的下個數(shù)，都必須是奇數(shù)。,由于1n中，奇數(shù)的個數(shù)最多比偶數(shù)的個數(shù)多1個，所以圓周上最多只有一個偶數(shù)，這樣奇數(shù)有2個，,3、已知t為正整數(shù)，若2t可以表示成ab1(其中a,b是大于1的整數(shù))，請找出滿足上述條件所有可能的t值。（2008年青少年數(shù)學國際城市邀請賽）,解：設正整數(shù)t，使得2tab1，顯然a為奇數(shù)。,(1)若b為奇數(shù)，則2t(a1)(ab1ab2a1),由于a，b均為奇數(shù)

4、，而奇數(shù)個奇數(shù)相加或相減的結果一定是奇數(shù)，所以ab1ab2a1也是奇數(shù)，,得知2tab1a1，故b=1，,這與b2矛盾。,從而只可能ab1ab2a11，,綜上可知，滿足題設的2的正整數(shù)次冪是23，即t3。,(2)若b為偶數(shù)，令b2m，,則ab1(mod4)。,若2t=ab+1，,則2t=ab+12(mod4)，,從而t=1，故ab=211=1，矛盾。,若2t=ab1=(am1)(am+1)，,兩個連續(xù)偶數(shù)之乘積為2的方冪只能是am1=2，am+1=4，,從而a3，b2m2。2t=ab1=321=8。,二、質(zhì)數(shù)與合數(shù),大于1的整數(shù)按它具有因數(shù)的情況又可分為質(zhì)數(shù)與合數(shù)兩類。,即對任一整數(shù)a1，有a

5、，其中p1p2pn均為質(zhì)數(shù)，1、2、n都是正整數(shù)。,另可得：a的正約數(shù)的個數(shù)為（11）（21）（n1）,算術基本定理：任何一個大于1的整數(shù)都可以分解成質(zhì)數(shù)的乘積。如果不考慮這些質(zhì)因子的次序，則這種分解法是唯一的。,設n是大于2的整數(shù)，如果不大于的質(zhì)數(shù)都不是n的因子，則n是質(zhì)數(shù)。,4、設S1,2,2005.若S中任意n個兩兩互質(zhì)的數(shù)組成的集合中都至少有一個質(zhì)數(shù)，試求n的最小值.（2005年西部奧林匹克）,解:首先,我們有n16。,事實上,取集合A01,22,32,52,412,432，,則,|A0|15,A0中任意兩數(shù)互質(zhì),但其中無質(zhì)數(shù),這表明n16.,其次,我們證明:對任意，n|A|16，A中

6、任兩數(shù)互質(zhì),則A中必存在一個質(zhì)數(shù).,利用反證法,假設A中無質(zhì)數(shù).記Aa1,a2,a16，分兩種情況討論.,則a1p1222，a2p2232，a15p1524722005,矛盾.,若,則a1,a2,a16均為合數(shù),又因為(ai,aj)1(1ij16),所以ai與aj的質(zhì)因數(shù)均不相同,設ai的最小質(zhì)因數(shù)為pi,不妨設p1p2p16,由(1),(2)知,反設不成立,從而A中必有質(zhì)數(shù),即n|A|16時結論成立.,若1A,則不妨設a161，a1,a2,a15均為合數(shù),同(1)所設,同理有a1p1222，a2p2232，a15p1524722005,矛盾.,綜上,所求的n最小值為16.,5、證明：對所有的

7、非負整數(shù)n，1至少是2n3個質(zhì)數(shù)（不一定互不相同）的乘積。（2007第36屆美國數(shù)學奧林匹克）,證明：當n0時，1823，結論成立,假設當nk時結論成立，即1至少是2k3個質(zhì)數(shù)的乘積，,當nk1時，只需證明，對mN*，記x72m1，是一個合數(shù),（這樣，1至少是2k322(k1)3個質(zhì)數(shù)的乘積）,即是一個合數(shù)。結論成立。,(x1)6,(x1)67x(x42x33x22x1),(x1)672m(x2x1)2,(x1)37m(x2x1)(x1)37m(x2x1),要使上式兩個因子都大于1，只需對較小的一個進行檢驗。,注意到x，,則(x1)37m(x2x1),(x1)3(x2x1),x33x23x1x

8、(x2x1),2x22x1,1,三、整除,帶余除法：對于任一整數(shù)a和任一非零整數(shù)b，必有惟一的一對整數(shù)q和r，使得abqr，0rb，且q和r由上述條件惟一確定。若r0，則稱b|a。,部分性質(zhì)：,若c|b，b|a，則c|a若c|a，d|b，則cd|ab若ma|mb，則a|b若a0，b0，b|a，則ba任意n個連續(xù)正整數(shù)的乘積必能被n！整除。,當（a，b）1時，稱a、b互素（互質(zhì)）。有：,若另上條件（a，p）1，則p|ap11,已知（a，c）1，若a|bc，則a|b；若a|b，c|b，則ac|b,p為質(zhì)數(shù)，若p|ab，則p|a或p|b,a，b（a，b）ab,（a，b）（a，bac）（abc，b）,

9、（裴蜀定理）存在整數(shù)x、y，使axby（a，b）,m（a，b）（ma，mb）,若（a，b）d，則（）1,若a|m，b|m，則a，b|m,費爾馬小定理：p是素數(shù)，則p|apa,定理：在n4kr（k，r為非負整數(shù)）中，0r4，則當r0（k0）時，n4kr的個位數(shù)字與n4的個位數(shù)字相同；當r0時，n4kr的個位數(shù)字與nr的個位數(shù)字相同。,個位數(shù)字只能是：0，1，4，5，6，9末兩位數(shù)字不可能同時為奇數(shù)。偶數(shù)的平方是偶數(shù)，且被4整除；奇數(shù)的平方是奇數(shù)，且被4除余1。在n2與（n1）2之間不存在平方數(shù)。,個位數(shù),平方數(shù)性質(zhì)：,7、求所有的正整數(shù)n，使n能被所有不大于的正整數(shù)整除。,得k3或4或5n36。

10、,解：設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，,8、已知2009|1(aN)，求a的值。,解：當a2010時，2008，,12009，成立,當a2011時，,2008,

11、2008,12008,故2009|1不成立,a2010,當a2009時，設12009k，,則2009k1，,2009k12009k,一方面，2009k得2009ka，,即ka2010，,k,2009k120091,但2009k1,2009k120091,故a2009,但此時12010，2009|1不成立,9、設a,b為正整數(shù)。證明：若4ab1整除(4a21)2，則ab.（07年IMO48）,即ab(ab)(4ab1)ab,矛盾.,證明：(4a21)2b2,(a(4ab1)ab)2,a2(4ab1)22a(ab)(4ab1)(ab)2,故由(4ab1)|(4a21)2推出(4ab1)|(ab)2

12、.,反設有正整數(shù)ab滿足(4ab1)|(ab)2,則必有一組這樣的(a,b)使ab為最小。,令(ab)2k(4ab1),不妨設ab.,二次方程x2(4k2)bxb2k0的一個根x1a,另一根x2(4k2)ba也是正整數(shù),故(x2,b)也滿足條件。,由所設ab最小得到x2a，即ka2b2。,于是(ab)2(a2b2)(4ab1),10、求所有的素數(shù)對（p，q），使得pq5p5q(09CMO),故q626由于q為奇素數(shù)，而626的奇素因子只有313，所以q313,解：若2pq，不妨設p2，則2q5p5q，故q5q25,由Fermat小定理，q5q5，得q30，,即q2，3，5,易驗證素數(shù)對（2,2

13、）不合要求，（2,3），（2,5）合乎要求,若pq為奇數(shù)且5pq，不妨設p5，,則5q555q，故q5q1625,當q5時素數(shù)對（5,5）合乎要求，,當q5時，由Fermat小定理有q5q11，,經(jīng)檢驗素數(shù)對（5,313）合乎要求,綜上所述，所有滿足題目要求的素數(shù)對（p，q）為（2,3），（3,2），（2,5），（5,2）（5,5），（5,313）及（313,5）,若p，q都不等于2和5，則有pq5p15q1，,故5p15q10（modp）,由Fermat小定理，得5p11（modp）,故由，得5q11（modp）,設p12k(2r1)，q12l(2s1)，其中k，l，r，s為正整數(shù),若kl，

14、則由，易知,1（modp）,1,(5q1)2r1,這與p2矛盾！所以kl,(1)2r1,同理有kl，矛盾！即此時不存在合乎要求的(p,q),11、設n是一個正整數(shù)，定義(n)，例如（1）1，（2）11，（3）111(1)設m是一個非負數(shù)證明：(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(m

15、od9)，,故27|（27）。從而27|(n)。,（2）首先證明：若27|n，則27|(n)。,設n27k，,則(n)（27）,而（27）（3）,其中0(mod9),再證明：若27|(n)，則27|n,9|3k，得27|9kn。證畢。,得n0(mod9),設n9k，,則由35|109k1(103k1)(106k103k1)，及106k103k13(mod9)，,得34|103k19,12、對哪些nN*,存在a,bQZ使得ab和anbn都是整數(shù)?(克羅地亞),但xnznMy2nkxn-1y2xn,故必y|2xn.,解.當n為奇數(shù)時，,取a,b,由于1n(3n1)n被1(3n1)3n整除.故a,b滿足條件.即n可為任何大于0的奇數(shù).,當n為偶數(shù),若有滿足條件的a,b(x,y,z,wZ,y,w1,(x,y)(z,w)