數(shù)學(xué)奧賽輔導(dǎo)

1、 PAGE 14數(shù)學(xué)奧賽輔導(dǎo)第二講 整除知識(shí)、方法、技能整除是整數(shù)的一個(gè)重要內(nèi)容，這里僅介紹其中的幾個(gè)方面：整數(shù)的整除性、最大公約數(shù)、最小公倍數(shù)、方冪問(wèn)題。.整數(shù)的整除性初等數(shù)論的基本研究對(duì)象是自然數(shù)集合及整數(shù)集合。 我們知道，整數(shù)集合中可以作加、減、乘法運(yùn)算，并且這些運(yùn)算滿足一些規(guī)律（即加法和乘法的結(jié)合律和交換律，加法與乘法的分配律），但一般不能做除法，即，如是整除，則不一定是整數(shù)。 由此引出初等數(shù)論中第一個(gè)基本概念：整數(shù)的整除性。定義一：（帶余除法）對(duì)于任一整數(shù)和任一整數(shù)，必有惟一的一對(duì)整數(shù)，使得，并且整數(shù)和由上述條件惟一確定，則稱為除的不完全商，稱為除的余數(shù)。若，則稱整除，或被整除，或稱

2、的倍數(shù)，或稱的約數(shù)（又叫因子），記為。否則，| 。任何的非的約數(shù)，叫做的真約數(shù)。0是任何整數(shù)的倍數(shù)，1是任何整數(shù)的約數(shù)。任一非零的整數(shù)是其本身的約數(shù)，也是其本身的倍數(shù)。由整除的定義，不難得出整除的如下性質(zhì)：（1）若（2）若（3）若，則反之，亦成立。（4）若。因此，若。（5）、互質(zhì)，若（6）為質(zhì)數(shù)，若則必能整除中的某一個(gè)。特別地，若為質(zhì)數(shù)，（7）如在等式中除開(kāi)某一項(xiàng)外，其余各項(xiàng)都是的倍數(shù)，則這一項(xiàng)也是的倍數(shù)。（8）n個(gè)連續(xù)整數(shù)中有且只有一個(gè)是n的倍數(shù)。（9）任何n個(gè)連續(xù)整數(shù)之積一定是n的倍數(shù)。本講開(kāi)始在整除的定義同時(shí)給出了約數(shù)的概念，又由上一講的算術(shù)基本定理，我們就可以討論整數(shù)的約數(shù)的個(gè)數(shù)了。定

3、理一：設(shè)大于1的整數(shù)的標(biāo)準(zhǔn)分解式為為質(zhì)數(shù)，均為非負(fù)整數(shù)），則a的約數(shù)的個(gè)數(shù)為。所有的約數(shù)和為：。事實(shí)上，由算術(shù)基本定理的推論知，而各約數(shù)的和就是展開(kāi)后的各項(xiàng)之和，所以例如，25200=2432527，所以，。.最大公約數(shù)和最小公倍數(shù)定義二：設(shè)、是兩個(gè)不全為0的整數(shù)。若整數(shù)c滿足：，則稱的公約數(shù)，的所有公約數(shù)中的最大者稱為的最大公約數(shù)，記為。如果=1，則稱互質(zhì)或互素。定義三：如果、的倍數(shù)，則稱、的公倍數(shù)。 的公倍數(shù)中最小的正數(shù)稱為的最小公倍數(shù)，記為。最大公約數(shù)和最小公倍數(shù)的概念可以推廣到有限多個(gè)整數(shù)的情形，并用表示的最大公約數(shù)，表示的最小公倍數(shù)。若，則稱互質(zhì)，若中任何兩個(gè)都互質(zhì)，則稱它們是兩兩互

4、質(zhì)的。注意，n個(gè)整數(shù)互質(zhì)與n個(gè)整數(shù)兩兩互質(zhì)是不同的概念，前者成立時(shí)后者不一定成立（例如，3，15，8互質(zhì)，但不兩兩互質(zhì)）；顯然后者成立時(shí)，前者必成立。因?yàn)槿魏握龜?shù)都不是0的倍數(shù)，所以在討論最小公倍數(shù)時(shí)，一般都假定這些整數(shù)不為0。同時(shí)，由于有相同的公約數(shù)，且（有限多個(gè)亦成立），因此，我們總限于在自然數(shù)集合內(nèi)來(lái)討論數(shù)的最大公約數(shù)和最小公倍數(shù)。顯然，若的標(biāo)準(zhǔn)分解式為為質(zhì)數(shù)，為非負(fù)整數(shù)），則 例如 3960=2332511， 756=22337，則 （3960，756）=2232=36， 3960，756=23335711=83160。求最大公約數(shù)也可以用輾轉(zhuǎn)相除法，其理論依據(jù)是：定理二：設(shè)a、b、c

5、是三個(gè)不全為0的整數(shù)，且有整數(shù)t使得，則a、b與b、c有相同的公約數(shù)，因而，即因?yàn)?，若、b的任一公約數(shù)，則由、c的公約數(shù)；反之，若d是b、c的任一公約數(shù)，d也是a、b的公約數(shù)。輾轉(zhuǎn)相除法：設(shè)、，由帶余除法有 因?yàn)槊窟M(jìn)行一次帶余除法，余數(shù)至少減1，即，而b為有限數(shù)，因此，必有一個(gè)最多不超過(guò)b的正整數(shù)n存在，使得，而，故由定理二得：例如，（3960，756）=（756，180）=（180，36）=36。具體算式如下： 由定義和上述求法不難得出最大公約數(shù)和最小公倍數(shù)的如下性質(zhì)：（1）。（2）設(shè)的公約數(shù)，則特別地，若。（3）設(shè)是任意n個(gè)正整數(shù)，如果，則。因，如此類(lèi)推得出能整除是它們的一個(gè)公約數(shù)。又設(shè)的

6、任一公約數(shù)，則，因而，同理可推出，如此類(lèi)推最后可得。 于是，故是最大公約數(shù)。（4）若，則一定有整數(shù)，使得。特別地，存在。這可由輾轉(zhuǎn)相除法的式逆推而得。（5）若。（6）；的任一公倍數(shù)，則；，特別地，若?？捎芍苯拥玫剑捎勺钚」稊?shù)定義得，根據(jù)、式知，。（7）設(shè)是任意個(gè)正整數(shù)。若mn，則。這是一個(gè)求多個(gè)整數(shù)的最小公倍數(shù)的方法。它可用證明類(lèi)似的方法來(lái)證明。.方冪問(wèn)題一個(gè)正整數(shù)能否表成個(gè)整數(shù)的次方和的問(wèn)題稱為方冪和問(wèn)題。特別地，當(dāng)時(shí)稱為次方問(wèn)題，當(dāng)時(shí)，稱為平方和問(wèn)題。能表為某整數(shù)的平方的數(shù)稱為完全平方數(shù)。簡(jiǎn)稱平方數(shù)，關(guān)于平方數(shù)，明顯有如下一些簡(jiǎn)單的性質(zhì)和結(jié)論：（1）平方數(shù)的個(gè)位數(shù)字只可能是0，1，4，

7、5，6，9。（2）偶數(shù)的平方數(shù)是4的倍數(shù)，奇數(shù)的平方數(shù)被8除余1，即任何平方數(shù)被4除的余數(shù)只能是0或1。（3）奇數(shù)平方的十位數(shù)字是偶數(shù)。（4）十位數(shù)字是奇數(shù)的平方數(shù)的個(gè)位數(shù)一定是6。（5）不能被3整除的數(shù)的平方被3除余1，能被3整除的數(shù)的平方能被3整除。因而，平方數(shù)被9除的余數(shù)為0，1，4，7，且此平方數(shù)的各位數(shù)字的和被9除的余數(shù)也只能為0，1，4，7。（6）平方數(shù)的約數(shù)的個(gè)數(shù)為奇數(shù)。（7）任何四個(gè)連續(xù)整數(shù)的乘積加1，必定是一個(gè)平方數(shù)。進(jìn)一步研究可得到有關(guān)平方和的幾個(gè)結(jié)論:定理三：奇素?cái)?shù)能表示成兩個(gè)正整數(shù)的平方和的充要條件是定理四：設(shè)正整數(shù)，其中不再含平方因數(shù)，能表示成兩個(gè)整數(shù)的平方的充要條件

8、是沒(méi)有形如的質(zhì)因數(shù)。定理五：每個(gè)正整數(shù)都能表示成四個(gè)整數(shù)的平方和。這幾個(gè)定理的證明略。這里重點(diǎn)是介紹有關(guān)方冪的解法技巧。方冪中許多問(wèn)題實(shí)質(zhì)上是不定方程的整數(shù)解問(wèn)題，比如著名的勾股數(shù)問(wèn)題。賽題精講例1：證明：對(duì)于任何自然數(shù)和，數(shù)都不能分解成若干個(gè)連續(xù)的正整數(shù)之積。（1981年全國(guó)高中聯(lián)賽試題）【證明】由性質(zhì)9知，只需證明數(shù)不能被一個(gè)很小的自然數(shù)整除。因3 1，故3 ，因而不能分解成三個(gè)或三個(gè)以上的連續(xù)自然數(shù)的積。再證不能分解成兩個(gè)連續(xù)正整數(shù)的積。由上知，因而只需證方程：無(wú)正整數(shù)解。而這一點(diǎn)可分別具體驗(yàn)算時(shí)，均不是形的數(shù)來(lái)說(shuō)明。故對(duì)任何正整數(shù)、都不能分解成若干個(gè)連續(xù)正整數(shù)之積。例2： 設(shè)和均為自然

9、數(shù),使得證明：可被1979整除。 (第21屆IMO試題)【證明】=1979兩端同乘以1319！得1319！ 此式說(shuō)明1979|1319！由于1979為質(zhì)數(shù)，且1979 1319！，故1979 | p?！驹u(píng)述】把1979換成形如的質(zhì)數(shù)，1319換成，命題仍成立。牛頓二項(xiàng)式定理和為偶數(shù)), 為奇數(shù))在整除問(wèn)題中經(jīng)常用到。例3 ：對(duì)于整數(shù)與，定義求證：可整除（1996加拿大數(shù)學(xué)競(jìng)賽試題）【證明】當(dāng)時(shí)，由于能被整除，所以能被整除，另一方面，上式中能被整除，所以也能被整除。因與2+1互質(zhì)，所以能被（2+1）（即）整除。類(lèi)似可證當(dāng)時(shí)，F(xiàn)（2+1，）能被F（2+1,1）整除。故能被整除。例4 ：求一對(duì)整數(shù)，

10、滿足：(1)不能被7整除；（2）能被77整除。 (第25屆IMO試題)【解】= =根據(jù)題設(shè)要求(1)(2)知，即令即即，則故可令即合要求。(第15屆美國(guó)普特南數(shù)學(xué)競(jìng)賽試題)【評(píng)述】數(shù)學(xué)歸納法在整除問(wèn)題中也有廣泛應(yīng)用。例5：是否存在1000000個(gè)連續(xù)整數(shù)，使得每一個(gè)都含有重復(fù)的素因子，即都能被某個(gè)素?cái)?shù)的平方所整除？【解】存在。用數(shù)學(xué)歸納法證明它的加強(qiáng)命題：對(duì)任何正整數(shù)存在個(gè)連續(xù)的整數(shù)，使得每一個(gè)都含有重復(fù)的素因子。當(dāng)=1時(shí)，顯然成立。這只需取一個(gè)素?cái)?shù)的平方。假設(shè)當(dāng)=時(shí)命題成立,即有個(gè)連續(xù)整數(shù),它們分別含有重復(fù)的素因子,任取一個(gè)與都不同的素?cái)?shù)(顯然存在),當(dāng)時(shí),這個(gè)數(shù)中任兩個(gè)數(shù)的差是形如的數(shù),不

11、能被整除,故這個(gè)數(shù)除以后,余數(shù)兩兩不同。但除以后的余數(shù)只有0，1，1這個(gè)，從而恰有一個(gè)數(shù)，使能被整除。這時(shí)，（個(gè)連續(xù)整數(shù)：2，（+1）分別能被整除，即時(shí)命題成立。故題對(duì)一切正整數(shù)均成立。例6：求證：（第1屆美國(guó)數(shù)學(xué)奧林匹克競(jìng)賽試題）【證明】設(shè)其中為質(zhì)數(shù)，為非負(fù)整數(shù)，則 因此只需證明 2 =2上式關(guān)于對(duì)稱，則不妨設(shè)，于是上式變?yōu)椋捍耸斤@然成立，故得證。例7：設(shè)和是兩個(gè)正整數(shù)，為大于或等于3的質(zhì)數(shù)，），試證：（1）；（2）或（1985新加坡數(shù)學(xué)競(jìng)賽試題） 【證明】由已知得，兩式相乘得于是故（1）現(xiàn)用反證法來(lái)證明。若令是的一個(gè)質(zhì)因子，則有因，則，從而于是是、的一個(gè)公約數(shù)，這與=1矛盾，故。（2）因?yàn)?/p>

12、所以而為質(zhì)數(shù)且，故或例8：設(shè)，求最大公約數(shù)（第26屆IMO預(yù)選題）【解】能過(guò)具體計(jì)算可猜想 此式不難用數(shù)學(xué)歸納法獲證。為求，對(duì)分奇偶來(lái)討論。（1）當(dāng)時(shí)，由于和互質(zhì)，所以而當(dāng)時(shí) 時(shí)，與81互質(zhì)。故此時(shí)有 （2）當(dāng)當(dāng)時(shí)與質(zhì)，所以而當(dāng)時(shí)，時(shí)，與34互質(zhì)。故此時(shí)有例9：盒子中各若干個(gè)球，每一次在其中個(gè)盒中加一球。求證：不論開(kāi)始的分布情況如何，總可按上述方法進(jìn)行有限次加球后使各盒中球數(shù)相等的充要條件是 （第26屆IMO預(yù)選題）【證明】設(shè)，則有使得，此式說(shuō)明：對(duì)盒子連續(xù)加球次，可使個(gè)盒子各增加了個(gè)，一個(gè)增加個(gè)。這樣可將多增加了一個(gè)球的盒子選擇為原來(lái)球數(shù)最少的那個(gè)，于是經(jīng)過(guò)次加球之后，原來(lái)球數(shù)最多的盒子中的球與球數(shù)最少的盒子中的球數(shù)之差減少1，因此，經(jīng)過(guò)有限次加球后，各盒球數(shù)差為0，達(dá)到各盒中的球數(shù)相等。用反證法證明必要性。若，則只要在個(gè)盒中放個(gè)球，則不管加球多少次，例如，加球次，則這時(shí)個(gè)盒中共有球（個(gè)），因?yàn)樗圆?/p>