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

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

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

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

4、，而奇數(shù)個(gè)奇數(shù)相加或相減的結(jié)果一定是奇數(shù)，所以ab1ab2a1也是奇數(shù)，,得知2tab1a1，故b=1，,這與b2矛盾。,從而只可能ab1ab2a11，,綜上可知，滿足題設(shè)的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)，,兩個(gè)連續(xù)偶數(shù)之乘積為2的方冪只能是am1=2，am+1=4，,從而a3，b2m2。2t=ab1=321=8。,二、質(zhì)數(shù)與合數(shù),大于1的整數(shù)按它具有因數(shù)的情況又可分為質(zhì)數(shù)與合數(shù)兩類。,即對(duì)任一整數(shù)a1，有a

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

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

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

8、(x2x1),2x22x1,1,三、整除,帶余除法：對(duì)于任一整數(shù)a和任一非零整數(shù)b，必有惟一的一對(duì)整數(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個(gè)連續(xù)正整數(shù)的乘積必能被n！整除。,當(dāng)（a，b）1時(shí)，稱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,費(fèi)爾馬小定理：p是素?cái)?shù)，則p|apa,定理：在n4kr（k，r為非負(fù)整數(shù)）中，0r4，則當(dāng)r0（k0）時(shí)，n4kr的個(gè)位數(shù)字與n4的個(gè)位數(shù)字相同；當(dāng)r0時(shí)，n4kr的個(gè)位數(shù)字與nr的個(gè)位數(shù)字相同。,個(gè)位數(shù)字只能是：0，1，4，5，6，9末兩位數(shù)字不可能同時(shí)為奇數(shù)。偶數(shù)的平方是偶數(shù)，且被4整除；奇數(shù)的平方是奇數(shù)，且被4除余1。在n2與（n1）2之間不存在平方數(shù)。,個(gè)位數(shù),平方數(shù)性質(zhì)：,7、求所有的正整數(shù)n，使n能被所有不大于的正整數(shù)整除。,得k3或4或5n36。

10、,解：設(shè)k2n(k1)2,當(dāng)k3時(shí),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,當(dāng)1n4時(shí)，有1|n，n1,2,3都滿足條件,當(dāng)4n9時(shí)，有1|n，2|n，n4,6,8都滿足條件,當(dāng)9n16時(shí)，有1|n，2|n，3|n，n12,同理，當(dāng)16n25時(shí)，n24，當(dāng)25n36時(shí)，無n滿足條件,故k(k1)(k2)n(k1)2,k(k1)(k2)|n，,8、已知2009|1(aN)，求a的值。,解：當(dāng)a2010時(shí)，2008，,12009，成立,當(dāng)a2011時(shí)，,2008,

11、2008,12008,故2009|1不成立,a2010,當(dāng)a2009時(shí)，設(shè)12009k，,則2009k1，,2009k12009k,一方面，2009k得2009ka，,即ka2010，,k,2009k120091,但2009k1,2009k120091,故a2009,但此時(shí)12010，2009|1不成立,9、設(shè)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è)有正整數(shù)ab滿足(4ab1)|(ab)2,則必有一組這樣的(a,b)使ab為最小。,令(ab)2k(4ab1),不妨設(shè)ab.,二次方程x2(4k2)bxb2k0的一個(gè)根x1a,另一根x2(4k2)ba也是正整數(shù),故(x2,b)也滿足條件。,由所設(shè)ab最小得到x2a，即ka2b2。,于是(ab)2(a2b2)(4ab1),10、求所有的素?cái)?shù)對(duì)（p，q），使得pq5p5q(09CMO),故q626由于q為奇素?cái)?shù)，而626的奇素因子只有313，所以q313,解：若2pq，不妨設(shè)p2，則2q5p5q，故q5q25,由Fermat小定理，q5q5，得q30，,即q2，3，5,易驗(yàn)證素?cái)?shù)對(duì)（2,2

13、）不合要求，（2,3），（2,5）合乎要求,若pq為奇數(shù)且5pq，不妨設(shè)p5，,則5q555q，故q5q1625,當(dāng)q5時(shí)素?cái)?shù)對(duì)（5,5）合乎要求，,當(dāng)q5時(shí)，由Fermat小定理有q5q11，,經(jīng)檢驗(yàn)素?cái)?shù)對(duì)（5,313）合乎要求,綜上所述，所有滿足題目要求的素?cái)?shù)對(duì)（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）,設(shè)p12k(2r1)，q12l(2s1)，其中k，l，r，s為正整數(shù),若kl，

14、則由，易知,1（modp）,1,(5q1)2r1,這與p2矛盾！所以kl,(1)2r1,同理有kl，矛盾！即此時(shí)不存在合乎要求的(p,q),11、設(shè)n是一個(gè)正整數(shù)，定義(n)，例如（1）1，（2）11，（3）111(1)設(shè)m是一個(gè)非負(fù)數(shù)證明：(3m)可以被3m整除，而不能被3m1整除(2)證明n能被27整除當(dāng)且僅當(dāng)（n）能被27整除（2008年日本東京大學(xué)入學(xué)考試題）,結(jié)合歸納假設(shè)，得3k1|（3k1）。綜上，原命題成立。,(1)m0時(shí)，（30）（1）1，30|（30）；,m1時(shí)，（31）111，31|（31）。,假設(shè)mk時(shí)，3k|（3k）。,則mk1時(shí)，(3k1)（3k）（1）,其中13(m

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