第一節(jié)　整數(shù)的p進(jìn)位制及其應(yīng)用 　　正整數(shù)有無窮多個(gè)，為了用有限個(gè)數(shù)字符號(hào)表示出無限多個(gè)正整數(shù)，人們發(fā)明了進(jìn)位制，這是一種位值記數(shù)法。進(jìn)位制的創(chuàng)立體現(xiàn)了有限與無限的對立統(tǒng)一關(guān)系，近幾年來，國內(nèi)與國際競賽中關(guān)于“整數(shù)的進(jìn)位制”有較多的體現(xiàn)，比如處理數(shù)字問題、處理整除問題及處理數(shù)列問題等等。在本節(jié)，我們著重介紹進(jìn)位制及其廣泛的應(yīng)用。 基礎(chǔ)知識(shí) 給定一個(gè)m位的正整數(shù)A，其各位上的數(shù)字分別記為，則此數(shù)可以簡記為：（其中）。 由于我們所研究的整數(shù)通常是十進(jìn)制的，因此A可以表示成10的次多項(xiàng)式，即，其中且，像這種10的多項(xiàng)式表示的數(shù)常常簡記為。在我們的日常生活中，通常將下標(biāo)10省略不寫，并且連括號(hào)也不用，記作，以后我們所講述的數(shù)字，若沒有指明記數(shù)式的基，我們都認(rèn)為它是十進(jìn)制的數(shù)字。但是隨著計(jì)算機(jī)的普及，整數(shù)的表示除了用十進(jìn)制外，還常常用二進(jìn)制、八進(jìn)制甚至十六進(jìn)制來表示。特別是現(xiàn)代社會(huì)人們越來越顯示出對二進(jìn)制的興趣，究其原因，主要是二進(jìn)制只使用0與1這兩種數(shù)學(xué)符號(hào)，可以分別表示兩種對立狀態(tài)、或?qū)α⒌男再|(zhì)、或?qū)α⒌呐袛?，所以二進(jìn)制除了是一種記數(shù)方法以外，它還是一種十分有效的數(shù)學(xué)工具，可以用來解決許多數(shù)學(xué)問題。 為了具備一般性，我們給出正整數(shù)A的p進(jìn)制表示： ，其中且。而仍然為十進(jìn)制數(shù)字，簡記為。 典例分析 例1．將一個(gè)十進(jìn)制數(shù)字2004（若沒有指明，我們也認(rèn)為是十進(jìn)制的數(shù)字）轉(zhuǎn)化成二進(jìn)制與八進(jìn)制，并將其表示成多項(xiàng)式形式。 分析與解答 　分析：用2作為除數(shù)（若化為p進(jìn)位制就以p作為除數(shù)），除2004商1002，余數(shù)為0；再用2作為除數(shù)，除1002商501余數(shù)為0；如此繼續(xù)下去，起到商為0為止。所得的各次余數(shù)按從左到右的順序排列出來，便得到所化出的二進(jìn)位制的數(shù)。 解： 各次商數(shù) 被除數(shù) 除數(shù) 0 1 3 7 15 31 62 125 250 501 1002 2004 2 1 1 1 1 1 0 1 0 1 0 0 各次余數(shù) 故，； 同理，有，。 處理與數(shù)字有關(guān)的問題，通常利用定義建立不定方程來求解。 例2．求滿足的所有三位數(shù)。　　?。?988年上海市競賽試題） 解：由于，則，從而； 推薦精選 當(dāng)時(shí)，； 當(dāng)時(shí)，； 當(dāng)時(shí)，； 當(dāng)時(shí)，； 當(dāng)時(shí)，； 于是所求的三位數(shù)只有512。 例3．一個(gè)四位數(shù)，它的個(gè)位數(shù)字與百位數(shù)字相同。如果將這個(gè)四位數(shù)的數(shù)字順序顛倒過來（即個(gè)位數(shù)字與千位數(shù)字互換，十位數(shù)字與百位數(shù)字互換），所得的新數(shù)減去原數(shù)，所得的差為7812，求原來的四位數(shù)。　　　　　　　　　　　　　　　 （1979年云南省競賽題） 解：設(shè)該數(shù)的千位數(shù)字、百位數(shù)字、十位數(shù)字分別為，則 原數(shù)　　　　　　　　　　　　　　　　　　　① 顛倒后的新數(shù)　　　　　　　　　　　　　　?、? 由②－①得7812＝ 即　　　③ 比較③式兩端百位、十位、個(gè)位數(shù)字得 由于原四位數(shù)的千位數(shù)字不能為0，所以，從而，又顯然百位數(shù)字，所以。所以所求的原四位數(shù)為1979。 例4．遞增數(shù)列1,3，4,9，10,12,13，……是由一些正整數(shù)組成，它們或是3的冪，或是若個(gè)不同的3的冪之和，求該數(shù)列的第100項(xiàng)。　　　　　　?。ǖ?屆美國數(shù)學(xué)邀請賽試題） 解：將已知數(shù)列寫成3的方冪形式： 易發(fā)現(xiàn)其項(xiàng)數(shù)恰好是自然數(shù)列對應(yīng)形式的二進(jìn)制表示： 即 由于100＝ 所以原數(shù)列的第100項(xiàng)為。 例5．1987可以在b進(jìn)制中寫成三位數(shù)，如果，試確定所有可能的和?！　　　　　　　　　　　　　　　　　。?987年加拿大數(shù)學(xué)競賽試題） 解：易知，從而， 推薦精選 即， 由知。由知故； 又因?yàn)橛?2個(gè)正約數(shù)，分別為1,2，3,6，9,18,109,218,327,654,981,1962，所以，從而。 又由知 例6．設(shè)是五位數(shù)（第一個(gè)數(shù)碼不是零），是由取消它的中間一個(gè)數(shù)碼后所成的四位數(shù)，試確定一切使得是整數(shù)。　　　　　　　　　　?。ǖ?屆加拿大數(shù)學(xué)競賽試題） 解：設(shè)，其中且；； 而是整數(shù)，可證，即 即，這顯然是成立的； 又可證，即＜ 即，這顯然也是正確的。 于是，即，又因?yàn)槭钦麛?shù)，從而； 于是，即＝ 即，而但3　102知為正整數(shù)） 從而，顯然，因而推得其中。 例7．若且是其各位數(shù)字和的倍數(shù)，這樣的有多少個(gè)？ （2004年南昌競賽試題） 解：（1）若為個(gè)位數(shù)字時(shí)，顯然適合，這種情況共有9種； 　?。?）若為100時(shí)，也適合； 　?。?）若為二位數(shù)時(shí)，不妨設(shè)，則，由題意得 即即也就是； 若顯然適合，此種情況共有9種； 若，則由，故 若，則顯然可以，此時(shí)共有2＋8＝10個(gè)； 若（）9，則或，這樣的數(shù)共有24,42,48,84共4個(gè)； 綜上所述，共有9＋1＋9＋10＋4＝33個(gè)。 推薦精選 例8．如果一個(gè)正整數(shù)在三進(jìn)制下表示的各數(shù)字之和可以被3整除，那么我們稱為“好的”，則前2005個(gè)“好的”正整數(shù)之和是多少？（2005年中國奧林匹克協(xié)作體夏令營試題） 解：首先考慮“好的”非負(fù)整數(shù)，考察如下兩個(gè)引理： 引理1.在3個(gè)連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有1個(gè)是“好的”。 證明：在這三個(gè)非負(fù)整數(shù)的三進(jìn)制表示中，0,1，2各在最后一位出現(xiàn)一次，其作各位數(shù)字相同，于是三個(gè)數(shù)各位數(shù)字之和是三個(gè)連續(xù)的正整數(shù)，其中有且僅有一個(gè)能被3整除（即“好的”），引理1得證。 引理2.在9個(gè)連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有3個(gè)是“好的”。把這3個(gè)“好的”非負(fù)整數(shù)化成三進(jìn)制，0,1，2恰好在這三個(gè)三進(jìn)制數(shù)的最后一位各出現(xiàn)一次。 證明：由引理1不難得知在9個(gè)連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有3個(gè)是“好的”。 另一方面，在這三個(gè)“好的”非負(fù)整數(shù)的三進(jìn)制表示中，最高位與倒數(shù)第三位完全相同，倒數(shù)第二位分別取0,1，2。若它使它們成為“好的”非負(fù)整數(shù)，則最后一位不相同，引理2得證。 將所有“好的”非負(fù)整數(shù)按從小到大的順序排成一列，設(shè)第2004個(gè)“好的”非負(fù)整數(shù)為，根據(jù)引理1，得，即。 設(shè)前個(gè)“好的”正整數(shù)之和為，由于前2003個(gè)“好的”正整數(shù)之和等于前2004個(gè)“好的”非負(fù)整數(shù)之和。因此； 又因?yàn)楹投际恰昂玫摹闭麛?shù)。因此前2005年“好的”正整數(shù)之和是： 　　。 第二節(jié) 整數(shù)的性質(zhì)及其應(yīng)用（1） 基礎(chǔ)知識(shí) 整數(shù)的性質(zhì)有很多，這里我們著重討論整數(shù)的整除性、整數(shù)的奇偶性，質(zhì)數(shù)與合數(shù)、完全平方數(shù)及整數(shù)的尾數(shù)等幾個(gè)方面的應(yīng)用。 1．整除的概念及其性質(zhì) 在高中數(shù)學(xué)競賽中如果不加特殊說明，我們所涉及的數(shù)都是整數(shù)，所采用的字母也表示整數(shù)。 定義：設(shè)是給定的數(shù)，，若存在整數(shù)，使得則稱整除，記作，并稱是的一個(gè)約數(shù)(因子)，稱是的一個(gè)倍數(shù)，如果不存在上述，則稱不能整除記作 。 由整除的定義，容易推出以下性質(zhì)： (1)若且，則(傳遞性質(zhì))； (2)若且，則即為某一整數(shù)倍數(shù)的整數(shù)之集關(guān)于加、減運(yùn)算封閉。若反復(fù)運(yùn)用這一性質(zhì)，易知及，則對于任意的整數(shù)有。更一般，若都是的倍數(shù)，則?；蛑瑒t其中； (3)若，則或者，或者，因此若且，則； (4)互質(zhì)，若，則； 推薦精選 (5)是質(zhì)數(shù)，若，則能整除中的某一個(gè)；特別地，若是質(zhì)數(shù)，若，則； (6)(帶余除法)設(shè)為整數(shù)，，則存在整數(shù)和，使得，其中，并且和由上述條件唯一確定；整數(shù)被稱為被除得的(不完全)商，數(shù)稱為被除得的余數(shù)。注意：共有種可能的取值：0,1，……，。若，即為被整除的情形； 易知，帶余除法中的商實(shí)際上為（不超過的最大整數(shù)），而帶余除法的核心是關(guān)于余數(shù)的不等式：。證明的基本手法是將分解為與一個(gè)整數(shù)之積，在較為初級(jí)的問題中，這種數(shù)的分解常通過在一些代數(shù)式的分解中取特殊值而產(chǎn)生，下面兩個(gè)分解式在這類論證中應(yīng)用很多，見例1、例2。 若是正整數(shù)，則； 若是正奇數(shù)，則；（在上式中用代） (7)如果在等式中取去某一項(xiàng)外，其余各項(xiàng)均為的倍數(shù)，則這一項(xiàng)也是的倍數(shù)； (8)n個(gè)連續(xù)整數(shù)中，有且只有一個(gè)是n的倍數(shù)； (9)任何n個(gè)連續(xù)的整數(shù)之積一定是n!的倍數(shù)，特別地，三個(gè)連續(xù)的正整數(shù)之積能被6整除； 2．奇數(shù)、偶數(shù)有如下性質(zhì)： (1)奇數(shù)奇數(shù)=偶數(shù)，偶數(shù)偶數(shù)＝偶數(shù)，奇數(shù)偶數(shù)＝奇數(shù)，偶數(shù)偶數(shù)＝偶數(shù)，奇數(shù)偶數(shù)＝偶數(shù)，奇數(shù)奇數(shù)＝奇數(shù)；即任意多個(gè)偶數(shù)的和、差、積仍為偶數(shù)，奇數(shù)個(gè)奇數(shù)的和、差仍為奇數(shù)，偶數(shù)個(gè)奇數(shù)的和、差為偶數(shù)，奇數(shù)與偶數(shù)的和為奇數(shù)，和為偶數(shù)； （2）奇數(shù)的平方都可以表示成的形式，偶數(shù)的平方可以表示為或的形式； （3）任何一個(gè)正整數(shù)，都可以寫成的形式，其中為負(fù)整數(shù)，為奇數(shù)。 （4）若有限個(gè)整數(shù)之積為奇數(shù)，則其中每個(gè)整數(shù)都是奇數(shù)；若有限個(gè)整數(shù)之積為偶數(shù)，則這些整數(shù)中至少有一個(gè)是偶數(shù)；兩個(gè)整數(shù)的和與差具有相同的奇偶性；偶數(shù)的平方根若是整數(shù)，它必為偶數(shù)。 3．完全平方數(shù)及其性質(zhì) 能表示為某整數(shù)的平方的數(shù)稱為完全平方數(shù)，簡稱平方數(shù)。平方數(shù)有以下性質(zhì)與結(jié)論： （1）平方數(shù)的個(gè)位數(shù)字只可能是0,1，4,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ù)的數(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ù)。 （8）設(shè)正整數(shù)之積是一個(gè)正整數(shù)的次方冪（），若（）＝1，則都是整數(shù)的次方冪。一般地，設(shè)正整數(shù)之積是一個(gè)正整數(shù)的次方冪（），若兩兩互素，則都是正整數(shù)的k次方冪。 4．整數(shù)的尾數(shù)及其性質(zhì)　 整數(shù)的個(gè)位數(shù)也稱為整數(shù)的尾數(shù)，并記為。也稱為尾數(shù)函數(shù)，尾數(shù)函數(shù)具有以下性質(zhì)： 推薦精選 （1）；（2）＝； （3）；（4）；； （5）若，則；（6）； （7）； （8） 5．整數(shù)整除性的一些數(shù)碼特征（即常見結(jié)論） （1）若一個(gè)整數(shù)的未位數(shù)字能被2（或5）整除，則這個(gè)數(shù)能被2（或5）整除，否則不能； （2）一個(gè)整數(shù)的數(shù)碼之和能被3（或9）整除，則這個(gè)數(shù)能被3（或9）整除，否則不能； （3）若一個(gè)整數(shù)的未兩位數(shù)字能被4（或25）整除，則這個(gè)數(shù)能被4（或25）整除，否則不能； （4）若一個(gè)整數(shù)的未三位數(shù)字能被8（或125）整除，則這個(gè)數(shù)能被8（或125）整除，否則不能； （5）若一個(gè)整數(shù)的奇位上的數(shù)碼之和與偶位上的數(shù)碼之和的差是11的倍數(shù)，則這個(gè)數(shù)能被11整除，否則不能。 6．質(zhì)數(shù)與合數(shù)及其性質(zhì) 1．正整數(shù)分為三類：（1）單位數(shù)1；（2）質(zhì)數(shù)（素?cái)?shù)）：一個(gè)大于1的正整數(shù)，如果它的因數(shù)只有1和它本身，則稱為質(zhì)（素）數(shù)；（3）如果一個(gè)自然數(shù)包含有大于1而小于其本身的因子，則稱這個(gè)自然數(shù)為合數(shù)。 2．有關(guān)質(zhì)（素）數(shù)的一些性質(zhì) （1）若，則的除1以外的最小正因數(shù)是一個(gè)質(zhì)（素）數(shù)。如果，則； （2）若是質(zhì)（素）數(shù)，為任一整數(shù)，則必有或（）＝1； （3）設(shè)為個(gè)整數(shù)，為質(zhì)（素）數(shù)，且，則必整除某個(gè)（）； （4）（算術(shù)基本定理）任何一個(gè)大于1的正整數(shù)，能唯一地表示成質(zhì)（素）因數(shù)的乘積（不計(jì)較因數(shù)的排列順序）； （5）任何大于1的整數(shù)能唯一地寫成　　①　　　　　的形式，其中為質(zhì)（素）數(shù)（）。上式叫做整數(shù)的標(biāo)準(zhǔn)分解式； （6）若的標(biāo)準(zhǔn)分解式為①，的正因數(shù)的個(gè)數(shù)記為，則。 典例分析 例1．證明：被1001整除。 證明： 所以整除。 例2．對正整數(shù)，記為的十進(jìn)制表示中數(shù)碼之和。證明：的充要條件是。 證明：設(shè)（這里，且），則，于是有 推薦精選 　　　　　?、? 對于，知，故①式右端個(gè)加項(xiàng)中的每一個(gè)都是9的倍數(shù)，從而由整除的性質(zhì)可知它們的和也能被9整除，即。由此可易推出結(jié)論的兩個(gè)方面。 例3．設(shè)是一個(gè)奇數(shù)，證明L對于任意正整數(shù)，數(shù)不能被整除。 證明：時(shí)，結(jié)論顯然成立。設(shè)，記所說的和為A，則： 。 由k是正奇數(shù)，從而結(jié)于每一個(gè)，數(shù)被整除，故被除得余數(shù)為2，從而A不可能被整除（注意）。 例4．設(shè)是正整數(shù)，，證明：（）（）。 證明：首先，當(dāng)時(shí)，易知結(jié)論成立。事實(shí)上，時(shí)，結(jié)論平凡；當(dāng)時(shí)，結(jié)果可由推出來（注意）。 最后，的情形可化為上述特殊情形：由帶余除法而，由于，從而由若是正整數(shù)，則知；而，故由上面證明了的結(jié)論知?。ㄗ⒁鈺r(shí)結(jié)論平凡），從而當(dāng)時(shí)，也有（）（）。這就證明了本題的結(jié)論。 例5．設(shè)正整數(shù)滿足，證明：不是質(zhì)（素）數(shù)。 證法一：由，可設(shè)其中。由意味著有理數(shù)的分子、分母約去了某個(gè)正整數(shù)后得既約分?jǐn)?shù)，因此，　　　　　　　?、? 同理，存在正整數(shù)使得　　　　　　　　　　　　　　　　　　?、? 因此，＝是兩個(gè)大于1的整數(shù)之積，從而不是素?cái)?shù)。 注：若正整數(shù)適合，則可分解為①及②的形式，這一結(jié)果在某些問題的解決中很有作用。 證法二：由，得，因此，因?yàn)槭钦麛?shù)，故也是整數(shù)。 若它是一個(gè)素?cái)?shù)，設(shè)為，則由　　　　　　　　　　　　　?、邸　　　? 可見整除，從而素?cái)?shù)整除或。不妨設(shè)｜，則，結(jié)合③推出，而這是不可能的（因?yàn)椋? 推薦精選 例6．求出有序整數(shù)對（）的個(gè)數(shù)，其中，，是完全平方數(shù)?！　　　　　　　　　　　　　　　　　。?999年美國數(shù)學(xué)邀請賽試題） 解：由于，可得： ＜。 又，于是 若是完全平方數(shù)，則必有＝。 然而＝，于是必有，即，此時(shí)，。所以所求的有序整數(shù)對（）共有98對： 。 例7．證明：若正整數(shù)滿足，則和都是完全平方數(shù)。　　　　　　　　　　　　　　　?。?006年山東省第二屆夏令營試題） 證法一：已知關(guān)系式即為 （）（）＝　　　　　　　　　　?、? 若（或者說中有一個(gè)為0時(shí)），結(jié)論顯然。 不妨設(shè)且，令，則， 從而＝，將其代入①得　　② 因?yàn)?，所以，從而? 而②式又可寫成； 因?yàn)榍?，所? 所以，從而。 所以，所以＝，從而為完全平方數(shù)。 所以也是完全平方數(shù)。 證法二：已知關(guān)系式即為 （）（）＝　　　　　　　　　　　① 推薦精選 論證的關(guān)鍵是證明正整數(shù)與互素。 記（，）。若，則有素因子，從而由①知。因?yàn)槭撬財(cái)?shù)，故，結(jié)合知，從而由得1，這是不可能的。故，從而由①推知正整數(shù)與都是完全平方數(shù)。 例8．證明不存在正整數(shù)，使2n2+1，3n2+1，6n2+1都是完全平方數(shù)。 證明：假設(shè)存在這樣的正整數(shù)，使2n2+1，3n2+1，6n2+1都是完全平方數(shù)，那么 （2n2+1）（3n2+1）（6n2+1）也必定是完全平方數(shù)。 而（2n2+1）（3n2+1）（6n2+1）＝36n6+36n4+11n2+1； 　36n6+36n4+9n2；36n6+36n4+12n3+9n2+6n+1； 所以（2n2+1）（3n2+1）（6n2+1）＜與（2n2+1）（3n2+1）（6n2+1）為完全平方數(shù)矛盾。 例9．?dāng)?shù)列的通項(xiàng)公式為，． 記，求所有的正整數(shù)，使得能被8整除．（2005年上海競賽試題） 解：記 　　 　　注意到　　，可得 因此，Sn+2除以8的余數(shù)，完全由Sn+1、Sn除以8的余數(shù)確定 ，故由(*)式可以算出各項(xiàng)除以8的余數(shù)依次是1,3，0,5，7,0，1,3，……，它是一個(gè)以6為周期的數(shù)列，從而 故當(dāng)且僅當(dāng) 練習(xí)題 1．證明：如果和都是大于3的素?cái)?shù)，則6是的因子。 推薦精選 證明：因?yàn)槭瞧鏀?shù)，所以2是的因子。又因?yàn)?，，除?的余數(shù)各不相同，而與都不能被3整數(shù)。于是6是的因子。 2．設(shè)，證明：； 解：由，故｜（）。 又因?yàn)?，從而｜，于是由整除的性質(zhì)知 。 3．證明：對于任意正整數(shù)，數(shù)　不能被整除。 證明：只需證2（）2（）即可。 因?yàn)槿羰钦麛?shù)，則； 若是正奇數(shù)，則； 故｜；｜，……， ｜ 所以｜2（）。 又因?yàn)?，所以?，所以　2（）＋2 即（）2（）命題得證。 4．已知為正奇數(shù)，求證：。 證明：因?yàn)槿羰钦麛?shù)，則； 若是正奇數(shù)，則； 　　所以，，從而； 　　　　，，從而； 　　　　，，從而； 又且，所以。 5．設(shè)a、b、c為滿足不等式1＜a＜b＜c的整數(shù)，且（ab-1）（bc-1）（ca-1）能被abc整除，求所有可能數(shù)組（a，b，c）.　　　　　　　　　　　（1989年上海競賽試題） 推薦精選 解  ∵（ab-1）（bc-1）（ca-1） =a2b2c2-abc（a+b+c）+ab+ac+bc-1，① ∵abc|（ab-1）（bc-1）（ca-1）. ∴存在正整數(shù)k,使ab+ac+bc-1=kabc,     ② k=＜＜＜＜　　∴k=1. 若a≥3，此時(shí)1=-＜矛盾. 已知a＞1.   ∴只有a=2. 當(dāng)a=2時(shí)，代入②中得2b+2c-1=bc，即   1=＜ ∴0＜b＜4，知b=3，從而易得c=5. 說明：在此例中通過對因數(shù)k的范圍討論，從而逐步確定a、b、c是一項(xiàng)重要解題技巧. 第三節(jié)　整數(shù)的性質(zhì)及其應(yīng)用（2） 基礎(chǔ)知識(shí) 　　最大公約數(shù)與最小公倍數(shù)是數(shù)論中的一個(gè)重要的概念，這里我們主要討論兩個(gè)整數(shù)互素、最大公約數(shù)、最小公倍數(shù)等基本概念與性質(zhì)。 定義1.（最大公約數(shù)）設(shè)不全為零，同時(shí)整除的整數(shù)（如）稱為它們的公約數(shù)。因?yàn)椴蝗珵榱?，故只有有限多個(gè)，我們將其中最大一個(gè)稱為的最大公約數(shù)，用符號(hào)（）表示。顯然，最大公約數(shù)是一個(gè)正整數(shù)。 當(dāng)（）＝1（即的公約數(shù)只有）時(shí)，我們稱與互素（互質(zhì)）。這是數(shù)論中的非常重要的一個(gè)概念。 　　　同樣，如果對于多個(gè)（不全為零）的整數(shù)，可類似地定義它們的最大公約數(shù)（）。若（）＝1，則稱互素。請注意，此時(shí)不能推出兩兩互素；但反過來，若（）兩兩互素，則顯然有（）＝1。 　　由最大公約數(shù)的定義，我們不難得出最大公約數(shù)的一些簡單性質(zhì)：例如任意改變的符號(hào)，不改變（）的值，即；（）可以交換，（）＝（）；（）作為的函數(shù)，以為周期，即對于任意的實(shí)數(shù)，有（）＝（）等等。為了更詳細(xì)地介紹最大公約數(shù)，我們給出一些常用的一些性質(zhì)： 推薦精選 （1）設(shè)是不全為0的整數(shù)，則存在整數(shù)，使得； （2）（裴蜀定理）兩個(gè)整數(shù)互素的充要條件是存在整數(shù)，使得； 事實(shí)上，條件的必要性是性質(zhì)（1）的一個(gè)特例。反過來，若有使等式成立，不妨設(shè)，則，故及，于是，即，從而。 （3）若，則，即的任何一個(gè)公約數(shù)都是它們的最大公約數(shù)的約數(shù)； （4）若，則； （5）若，則，因此兩個(gè)不互素的整數(shù)，可以自然地產(chǎn)生一對互素的整數(shù)； （6）若，則，也就是說，與一個(gè)固定整數(shù)互素的整數(shù)集關(guān)于乘法封閉。并由此可以推出：若，對于有，進(jìn)而有對有。 （7）設(shè)，若，則； （8）設(shè)正整數(shù)之積是一個(gè)正整數(shù)的次方冪（），若（）＝1，則都是整數(shù)的次方冪。一般地，設(shè)正整數(shù)之積是一個(gè)正整數(shù)的次方冪（），若兩兩互素，則都是正整數(shù)的次方冪。 定義2.設(shè)是兩個(gè)非零整數(shù)，一個(gè)同時(shí)為倍數(shù)的數(shù)稱為它們的公倍數(shù)，的公倍數(shù)有無窮多個(gè)，這其中最小的一個(gè)稱為的最小公倍數(shù)，記作，對于多個(gè)非零實(shí)數(shù)，可類似地定義它們的最小公倍數(shù)［］。 　　最小公倍數(shù)主要有以下幾條性質(zhì)： （1）與的任一公倍數(shù)都是的倍數(shù)，對于多于兩個(gè)數(shù)的情形，類似結(jié)論也成立； （2）兩個(gè)整數(shù)的最大公約數(shù)與最小公倍滿足：（但請注意，這只限于兩個(gè)整數(shù)的情形，對于多于兩個(gè)整數(shù)的情形，類似結(jié)論不成立）； （3）若兩兩互素，則［］＝｜｜； （4）若，且兩兩互素，則｜。 典例分析 例1． 設(shè)是正整數(shù)，且，它們的最小公倍數(shù)是最大公約數(shù)的120倍，求。 解：設(shè)，則，其中且，于是。 推薦精選 所以即　　 由及（2）可得： 。 由（1）可知只能取 從而或29，故或。 例2．設(shè)，，則。 證明：設(shè)，則，，其中。于是，已知條件轉(zhuǎn)化為，故更有，從而轉(zhuǎn)化為，但是，故，結(jié)合，知必有，同時(shí)，因此。 例3．設(shè)正整數(shù)的最大公約數(shù)是1，并且，證明是一個(gè)完全平方數(shù)。 證明：設(shè)，則，，其中，由于，故，現(xiàn)在問題中的等式可以轉(zhuǎn)化為　　　　　　　① 由此可見整除。因?yàn)?，故，同樣可得，再由便可以推出。設(shè)，其中是一個(gè)正整數(shù)。一方面，顯然整除；另一方面，結(jié)合①式，得，故，從而，但，故。 因此，，故，這樣就證明了是一個(gè)完全平方數(shù)。 例4． 都是正整數(shù)，是否存在整數(shù)使得對任意的正整數(shù)，與互質(zhì)？ 解：令，，則，于是存在整數(shù)使得， 令，則對任意的正整數(shù)，設(shè)，有 即，而，，所以，即對任意的正整數(shù)，（，）＝1。 例5． 已知，證明：對于任意的正整數(shù)，都有 兩兩互素。（2002年克羅地亞競賽試題） 推薦精選 證明：設(shè)（其中出現(xiàn)次）。由，故對于有，則是含有0次項(xiàng)的多項(xiàng)式。因此，除以的余數(shù)為1。設(shè)整數(shù)可整除和，又＝，則當(dāng)除以時(shí)余數(shù)為1，即＝＋1。所以，矛盾！ 從而可知兩兩互素。 例6．求出所有的正整數(shù)對，使得是一個(gè)整數(shù)。 （2006年山東省第二屆夏令營試題） 解：由于且 ，所以是對稱的。不妨設(shè)。 當(dāng)時(shí)，則，從而＝2； 當(dāng)時(shí)，若時(shí)，則有，所以或3； 　　　　　　若時(shí)，由于是一個(gè)整數(shù)，從而使得　即，所以＜。 　　　　　　　又由于，，所以。 　　　　　　　所以，從而得或3，所以； 綜上知所有的為（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5). 例7．已知，且，試問的充要條件是嗎？ （2006年山東省第二屆夏令營試題） 分析：因?yàn)?，所以? 又，所以； 令，則有 推薦精選 又因?yàn)椋? 從而上式且為奇數(shù)，即的充要條件是且為奇數(shù)。 例8．我們知道有1個(gè)質(zhì)因子，且； 　　　　　　　有2個(gè)質(zhì)因子，且 　　　　　　　……………… 如此下去，我們可以猜想： 至少有個(gè)質(zhì)因子，且。試證明之。　　　　　　　　　　　　　　　　　　?。?006年山東省第二屆夏令營試題） 證明：令＝，則＝，即要證是整數(shù)且有個(gè)質(zhì)因子。下用數(shù)學(xué)歸納法證明是整數(shù)。 時(shí)，結(jié)論顯然； 假設(shè)時(shí)，成立； 當(dāng)＋1時(shí)，因?yàn)?－1)3+1=3－32＋3； 因?yàn)椋?，即是整?shù)。 下證至少有個(gè)質(zhì)因子。 ＝3－32＋3＝()3－3()2＋3(). 因?yàn)椋?)，令，則＝ 由于(,3)=1，所以(,)=1，從而必有異于質(zhì)因子的質(zhì)因子， 所以至少有個(gè)質(zhì)因子?！　　　　　　　　∽C畢！ 練習(xí) 1．若是奇數(shù)，則。 分析：要證明與互質(zhì)，我們只需要證明它們的公因子為1即可，但是這對于不好處理，由為奇數(shù)這一條件，我們可以想到從而找到思路。 證明：由于為奇數(shù)，故，又，從而（，）（），而（）＝（2）＝1，故。 2．若17|(2a+3b),試證：17|(9a+5b). 證明：注意到2(9a+5b)=9(2a+3b)－17b,于是17|2(9a+5b).但是(17,2)=1,即得17|(9a+5b). 3．設(shè)是正整數(shù)，若不是整數(shù)，則必為無理數(shù)。 證明：設(shè)是非整數(shù)的有理數(shù)，則可設(shè)，于是。因?yàn)? 推薦精選 故可知。但，因而。這與是整數(shù)矛盾！證畢。 4．設(shè)a,b是不全為0的整數(shù)，一切形如ax+by的數(shù)中，最小的正數(shù)是d，試證：d=(a,b). 5.記Fn＝＋1，試證：(Fn,Fm)=1,這里. 第四節(jié)　同余 　　同余式性質(zhì)應(yīng)用非常廣泛，在處理某些整除性、進(jìn)位制、對整數(shù)分類、解不定方程等方面的問題中有著不可替代的功能，與之密切相關(guān)的的數(shù)論定理有歐拉定理、費(fèi)爾馬定理和中國剩余定理。 基礎(chǔ)知識(shí) 三個(gè)數(shù)論函數(shù) 對于任何正整數(shù)均有定義的函數(shù)，稱為數(shù)論函數(shù)。在初等數(shù)論中，所能用到的無非也就有三個(gè)，分別為：高斯(Gauss)取整函數(shù)[x]及其性質(zhì)，除數(shù)函數(shù)d(n)和歐拉(Euler)函數(shù)和它的計(jì)算公式。 1． 高斯(Gauss)取整函數(shù)[] 設(shè)是實(shí)數(shù)，不大于的最大整數(shù)稱為的整數(shù)部分，記為[]；稱為的小數(shù)部分，記為｛｝。例如：［0.5］＝0，等等。 由的定義可得如下性質(zhì)： 性質(zhì)1.； 性質(zhì)2.； 性質(zhì)3.設(shè)，則； 性質(zhì)4.;; 性質(zhì)5.　； 性質(zhì)6.對于任意的正整數(shù)，都有如下的埃米特恒等式成立： 　　　； 為了描述性質(zhì)7，我們給出如下記號(hào)：若，且　，則稱為恰好整除，記為。例如：我們有等等，其實(shí)，由整數(shù)唯一分解定理：任何大于1的整數(shù)能唯一地寫成的形式，其中為質(zhì)（素）數(shù)（）。我們還可以得到：。 性質(zhì)7.若，則 推薦精選 　　　請注意，此式雖然被寫成了無限的形式，但實(shí)際上對于固定的，必存在正整數(shù)，使得，因而，故，而且對于時(shí)，都有。因此，上式實(shí)際上是有限項(xiàng)的和。另外，此式也指出了乘數(shù)的標(biāo)準(zhǔn)分解式中，素因數(shù)的指數(shù)的計(jì)算方法。 2．除數(shù)函數(shù)d(n) 正整數(shù)的正因數(shù)的個(gè)數(shù)稱為除數(shù)函數(shù)，記為d(n)。這里給出d(n)的計(jì)算公式： d(n)＝，為素?cái)?shù)唯一分解定理中的指數(shù)。為了敘述地更加明確，我們組出素?cái)?shù)唯一分解定理。 算術(shù)基本定理（素?cái)?shù)唯一分解定理）：任何一大于1的整數(shù)均可以分解為素?cái)?shù)的乘積，若不考慮素?cái)?shù)乘積的先后順序，則分解式是唯一的。 例如：。當(dāng)一個(gè)整數(shù)分解成素?cái)?shù)的乘積時(shí)，其中有些素?cái)?shù)可以重復(fù)出現(xiàn)。例如在上面的分解式中，2出現(xiàn)了三次。把分解式中相同的素?cái)?shù)的積寫成冪的形式，我們就可以把大于1的正整數(shù)寫成　　?。?） 此式稱為的標(biāo)準(zhǔn)分解式。這樣，算術(shù)基本定理也可以描述為大于1的整數(shù)的標(biāo)準(zhǔn)分解式是唯一的（不考慮乘積的先后順序）。 　　推論1.若的標(biāo)準(zhǔn)分解式是（1）式，則是的正因數(shù)的充要條件是： 　　　?。?） 應(yīng)說明（2）不能稱為是的標(biāo)準(zhǔn)分解式，，其原因是其中的某些可能取零值（也有可能不含有某個(gè)素因數(shù)，因而） 推論2.設(shè)，且，若是整數(shù)的次方，則也是整數(shù)的次方。特別地，若是整數(shù)的平方，則也是整數(shù)的平方。 3. 歐拉(Euler)函數(shù) 設(shè)正整數(shù)0,1，……中與互素的個(gè)數(shù)，稱之為的歐拉函數(shù)，并記為。若的標(biāo)準(zhǔn)分解式是，則的計(jì)算公式是： 　 例如：； . 以下我們講述同余的概念： 同余的概念是高斯（Gauss）在1800年左右給出的。設(shè)是正整數(shù)，若用去除整數(shù)，所得的余數(shù)相同，則稱為與關(guān)于模同余，記作，否則，稱為與關(guān)于模不同余。 定義1.（同余）設(shè)，若，則稱和對模同余，記作；若不然，則稱和對模不同余，記作　。例如：，等等。 推薦精選 當(dāng)時(shí)，，則稱是對模的最小非負(fù)剩余。 由帶余除法可知，和對模同余的充要條件是與被除得的余數(shù)相同。對于固定的模，模的同余式與通常的等式有許多類似的性質(zhì)： 性質(zhì)1. 的充要條件是也即。 性質(zhì)2.同余關(guān)系滿足以下規(guī)律： （1）（反身性）； （2）（對稱性）若，則； （3）（傳遞性）若，，則； （4）（同余式相加）若，，則； （5）（同余式相乘）若，，則； 反復(fù)利用（4）（5），可以對多個(gè)兩個(gè)的（模相同的）同余式建立加、減和乘法的運(yùn)算公式。特別地，由（5）易推出：若，為整數(shù)且，則；但是同余式的消去律一般并不成立，即從未必能推出，可是我們卻有以下結(jié)果： （6）若，則，由此可以推出，若，則有，即在與互素時(shí)，可以在原同余式兩邊約去而不改變模（這一點(diǎn)再一次說明了互素的重要性）。 現(xiàn)在提及幾個(gè)與模相關(guān)的簡單而有用的性質(zhì)： （7）若，｜，則； （8）若，，則； （9）若，則，特別地，若兩兩互素時(shí)，則有； 性質(zhì)3.若，則；； 性質(zhì)4.設(shè)是系數(shù)全為整數(shù)的多項(xiàng)式，若，則。 這一性質(zhì)在計(jì)算時(shí)特別有用：在計(jì)算大數(shù)字的式子時(shí)，可以改變成與它同余的小的數(shù)字，使計(jì)算大大地簡化。如例3。 定義2.設(shè)，是使成立的最小正整，則稱為對模的階。 在取定某數(shù)后，按照同余關(guān)系把彼此同余的整數(shù)歸為一類，這些數(shù)稱為模的剩余類。一個(gè)類的任何一個(gè)數(shù)，都稱為該類所有數(shù)的剩余。顯然，同類的余數(shù)相同，不同類的余數(shù)不相同，這樣我們就把全體整數(shù)按照模劃分為了個(gè)剩余類：。在上述的個(gè)剩余類中，每一類任意取一個(gè)剩余，可以得到個(gè)數(shù) 推薦精選 ，稱為模的一個(gè)完全剩余系。例如關(guān)系模7，下面的每一組數(shù)都是一個(gè)完全剩余系： 0，1，2，3，4，5，6； -7，8，16，3，-10，40，20； -3，-2，-1，0，1，2，3。 顯然，一組整數(shù)成為模的完全剩余系只需要滿足兩個(gè)條件（1）有個(gè)數(shù)；（2）各數(shù)關(guān)于模兩兩不同余。最常用的完全剩余系是最小非負(fù)完全剩余系及絕對值最小完全剩余系。模的最小非負(fù)完全剩余系是：0，1，2，………,;即除數(shù)為時(shí)，余數(shù)可能取到的數(shù)的全部值。 當(dāng)為奇數(shù)時(shí)，絕對值最小的完全剩余系是：； 當(dāng)為偶數(shù)時(shí)，絕對值最小的完全剩余系有兩個(gè)： ； 。 以上只是我們個(gè)人對同余及剩余類的理解，為了方便大家研究，我們把有關(guān)材料上的具體概念給出，希望大家好好地研究： 定義3.（同余類）設(shè)，每一個(gè)這樣的類為模的同余類。 說明：整數(shù)集合可以按模來分類，確切地說，若和模同余，則和屬同一類，否則不屬于同一類，每一個(gè)這樣的類為模的一個(gè)同余類。由帶余除法，任一整數(shù)必恰與0,1,……，中的一個(gè)模同余，而0,1,……，這個(gè)數(shù)彼此模不同余，因此模共有個(gè)不同的同余類，即。 例如，模2的同余類共有兩個(gè)，即通常說的偶數(shù)類與奇數(shù)類，這兩類中的數(shù)分別具有形式和（為任意整數(shù)）。 定義4。（剩余類）設(shè)是正整數(shù)，把全體整按對模的余數(shù)分成類，相應(yīng)的個(gè)集合記為：，其中，稱為模的一個(gè)剩余類。以下是幾條常用性質(zhì)： （1）且； （2）每一個(gè)整數(shù)僅在的一個(gè)里； （3）對于任意，則的充要條件是。 定義5.（完全剩余系）一組數(shù)稱為模的完全剩余系，如果對任意有且僅有一個(gè)是對模的剩余，即。換一種說法更好理解： 設(shè)為模的全部剩余類，從每個(gè)中任取一個(gè)，得個(gè)數(shù)組成的數(shù)組，叫做模的一個(gè)完全剩余系。 說明：在個(gè)剩余類中各任取一個(gè)數(shù)作為代表，這樣的個(gè)數(shù)稱為模的一個(gè)完全剩余系，簡稱模的完系。換句話說，個(gè)數(shù)稱為模的一個(gè)完系，是指它們彼此模不同余，例如0,1，2，……，是模的一個(gè)完系，這稱作是模的最小非負(fù)完系。 性質(zhì)：（1）個(gè)整數(shù)構(gòu)成模的一個(gè)完全剩余系兩兩對模不同余； 　　?。?）若，則與同時(shí)跑遍模的完全剩余系。 推薦精選 典例分析 例1．試解方程：。 解：因?yàn)樽筮吺钦麛?shù)，因而右邊的分式也應(yīng)該是整數(shù)，所以 于是，從而，故。 但是是整數(shù)，故，，代入前面的不等式，得，直接觀察即知，于是。 例2．?dāng)?shù)100！的十進(jìn)位制表示中，未尾連續(xù)地有多少位全是零？ 解：命題等價(jià)于100！最多可以被10的多少次方整除。因?yàn)橐蚨?00！中2的指數(shù)大于5的指數(shù)，所以100！中5的指數(shù)就是所需求出的零的位數(shù)。 由即可知100！的未尾連續(xù)地有24位全是數(shù)碼零。 例3．試求被50除所得的余數(shù)。 解：由于是關(guān)于的整系數(shù)多項(xiàng)式，而，于是知 。 又注意到，故 又，所以 注意到，因而29就是所求的余數(shù)。 說明：在上述過程中，我們已經(jīng)看到的作用。一般而言，知道一個(gè)整數(shù)的多少次冪關(guān)于模同余于是非常有用的。事實(shí)上，若，則對大的指數(shù)利用帶余除法定理，可得，于是有，這里余數(shù)是一個(gè)比小得多的數(shù)，這樣一來，計(jì)算的問題，就轉(zhuǎn)化成了計(jì)算余數(shù)次冪的問題，從而使計(jì)算簡單化。 例4．設(shè)，計(jì)算某星期一后的第天是6星期幾？ 推薦精選 解；星期幾的問題是被7除求余數(shù)的問題。由于，于是， ，因而。 為了把指數(shù)的指數(shù)寫成的形式，還需取6為模來計(jì)算。為此我們有 ，進(jìn)而有，，依次類推，有，所以 從而， 這樣，星期一后的第天將是星期五。 例5．求所有的素?cái)?shù)，使與也是素?cái)?shù)。 分析：要使與也是素?cái)?shù)，應(yīng)該是對除以某個(gè)數(shù)素的余數(shù)進(jìn)行分類討論，最后確定只能是這個(gè)素?cái)?shù)。由于只有兩個(gè)數(shù)，所以不能太大，那樣討論起來也不會(huì)有什么效果，試驗(yàn)發(fā)現(xiàn)對本題不起任何效果，現(xiàn)對展開討論。 解：設(shè)，，且 若或4時(shí)，，； 若或3時(shí)，，； 即時(shí)，為5的倍數(shù)且比5大，不為質(zhì)數(shù)。故，此時(shí)， ；都是素?cái)?shù)。 即可題有唯一解。 注：要使幾個(gè)數(shù)同為質(zhì)數(shù)，一般是對這幾個(gè)數(shù)也合乎以某一質(zhì)數(shù)的余數(shù)來確定，如均為質(zhì)數(shù)，可得只能為3，由于這是的一次式，故三個(gè)數(shù)就模3，而二次式對三個(gè)數(shù)就模5，四個(gè)數(shù)一般就模7了。 例6．求滿足的全部正整數(shù)。 分析：如果，兩邊，得，這是不可能的； 　　　如果，而中有一個(gè)大于1，則另一個(gè)也大于1，得，故為奇數(shù)，，得，而，為奇數(shù)，從而，矛盾！ 所以為唯一解。 注：在解不定方程時(shí)，往往要分情況討論，也常常利用同余來導(dǎo)出一些性質(zhì)求出矛盾！ 推薦精選 例7．?dāng)?shù)列滿足： 證明：（1）對任意為正整數(shù)；(2)對任意為完全平方數(shù)。 （2005年全國高中數(shù)學(xué)聯(lián)賽試題） 證明：（1）由題設(shè)得且嚴(yán)格單調(diào)遞增.將條件式變形得兩邊平方整理得?、? 　　　　　　　　　　　　　　　　　　② ①-②得 　　　　　　　　　　　　　　　　　　　　　　?、? 由③式及可知，對任意為正整數(shù). （2）將①兩邊配方，得?、? 由③式≡ ∴≡≡0（mod3）∴為正整數(shù)，④式成立. 是完全平方數(shù). 例8．若可以寫成有限小數(shù)，那么自然數(shù)的值是多少？ 解：由于 若與互素，則分?jǐn)?shù)是既約分?jǐn)?shù)； 若與不互素，設(shè)它們的公約數(shù)為，且，設(shè)，則，故與的公約數(shù)是5，此時(shí)分?jǐn)?shù)的分子、分母只有公約數(shù)5。 由于可以寫成有限小數(shù)，故約分之后的分母除了2,5以外，沒還有其它的公約數(shù)，因此。 因?yàn)槭瞧鏀?shù)，，故，即。 由于故，從而，即， 推薦精選 故只有才是有限小數(shù)。 練習(xí) 1． 試求方程的實(shí)數(shù)解。（答案：） 2． 若，試出至少5個(gè)的值。（答案：17，32，34，40，48） 3． 試求被25除所得的余數(shù)。（答案：24） 4． 設(shè)整數(shù)使，這些中最小的正整數(shù)為，試證：。特別地，若，則。 證明：設(shè)，則易知，但是最小的正整數(shù)，故只能為0，即。 5． 設(shè)是任意整數(shù)，試證下面形狀的數(shù)都不是完全平方數(shù)：（1）；（2）。 解：（1）不同余； （2）或3，但或1。 6． 求所有滿足的正整數(shù)三元組。 第五節(jié)　初等數(shù)論中的幾個(gè)重要定理 基礎(chǔ)知識(shí) 定義（歐拉(Euler)函數(shù)）一組數(shù)稱為是模的既約剩余系，如果對任意的，且對于任意的，若＝1，則有且僅有一個(gè)是對模的剩余，即。并定義中和互質(zhì)的數(shù)的個(gè)數(shù)，稱為歐拉（Euler）函數(shù)。 這是數(shù)論中的非常重要的一個(gè)函數(shù)，顯然，而對于，就是1,2，…，中與互素的數(shù)的個(gè)數(shù)，比如說是素?cái)?shù)，則有。 引理：；可用容斥定理來證（證明略）。 定理1：（歐拉（Euler）定理）設(shè)＝1，則。 證明：取模的一個(gè)既約剩余系，考慮，由于與互質(zhì)，故仍與 推薦精選 互質(zhì)，且有　，于是對每個(gè)都能找到唯一的一個(gè)，使得，這種對應(yīng)關(guān)系是一一的，從而，。 ，，故。證畢。 分析與解答：要證，我們得設(shè)法找出個(gè)相乘，由個(gè)數(shù)我們想到中與互質(zhì)的的個(gè)數(shù)：，由于＝1，從而也是與互質(zhì)的個(gè)數(shù)，且兩兩余數(shù)不一樣，故（），而（）＝1，故。 這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個(gè)數(shù)組組成另外一組剩余系來解決問題。 定理2：（費(fèi)爾馬（Fermat）小定理）對于質(zhì)數(shù)及任意整數(shù)有。 設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則。若不是的倍數(shù)，則由引理及歐拉定理得，，由此即得。 定理推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則。 定理3：（威爾遜（Wilson）定理）設(shè)為質(zhì)數(shù)，則。 分析與解答：受歐拉定理的影響，我們也找個(gè)數(shù)，然后來對應(yīng)乘法。 證明：對于，在中，必然有一個(gè)數(shù)除以余1，這是因?yàn)閯t好是的一個(gè)剩余系去0。 　　　從而對，使得； 　　　若，，則，，故對于，有　。即對于不同的對應(yīng)于不同的，即中數(shù)可兩兩配對，其積除以余1，然后有，使，即與它自己配對，這時(shí)，，或，或。 　　除外，別的數(shù)可兩兩配對，積除以余1。故。 推薦精選 定義：設(shè)為整系數(shù)多項(xiàng)式（），我們把含有的一組同余式（）稱為同余方組程。特別地，，當(dāng)均為的一次整系數(shù)多項(xiàng)式時(shí)，該同余方程組稱為一次同余方程組.若整數(shù)同時(shí)滿足： ，則剩余類（其中）稱為同余方程組的一個(gè)解，寫作 定理4：（中國剩余定理）設(shè)是兩兩互素的正整數(shù)，那么對于任意整數(shù)，一次同余方程組，必有解，且解可以寫為： 這里，，以及滿足，（即為對模的逆）。 中國定理的作用在于它能斷言所說的同余式組當(dāng)模兩兩互素時(shí)一定有解，而對于解的形式并不重要。 定理5：（拉格郎日定理）設(shè)是質(zhì)數(shù)，是非負(fù)整數(shù)，多項(xiàng)式是一個(gè)模為次的整系數(shù)多項(xiàng)式（即 ），則同余方程至多有個(gè)解（在模有意義的情況下）。 定理6：若為對模的階，為某一正整數(shù)，滿足，則必為的倍數(shù)。 以上介紹的只是一些系統(tǒng)的知識(shí)、方法，經(jīng)常在解決數(shù)論問題中起著突破難點(diǎn)的作用。另外還有一些小的技巧則是在解決、思考問題中起著排除情況、輔助分析等作用，有時(shí)也會(huì)起到意想不到的作用，如：，。這里我們只介紹幾個(gè)較為直接的應(yīng)用這些定理的例子。 典例分析 例1.設(shè)，求證：。 證明：因?yàn)?，故由知，從而，但是，故由歐拉定理得：，，從而；同理，。 于是，，即。 注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：若有正整數(shù)使，則有，其中； 因而關(guān)于，數(shù)列的項(xiàng)依次同余于這個(gè)數(shù)列相繼的項(xiàng)成一段，各段是完全相同的，因而是周期數(shù)列。如下例： 推薦精選 例2．試求不大于100，且使成立的自然數(shù)的和。 解：通過逐次計(jì)算，可求出關(guān)于的最小非負(fù)剩余（即為被11除所得的余數(shù)）為： 因而通項(xiàng)為的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)成周期為5的周期數(shù)列： 3，9，5，4，1，3，9，5，4，1，……… 類似地，經(jīng)過計(jì)算可得的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)成周期為10的周期數(shù)列： 7，5，2，3，10，4，6，9，8，1，……… 于是由上兩式可知通項(xiàng)為的數(shù)列的項(xiàng)的最小非負(fù)剩余，構(gòu)成周期為10（即上兩式周期的最小公倍數(shù)）的周期數(shù)列： 3，7，0，0，4，0，8，7，5，6，……… 這就表明，當(dāng)時(shí)，當(dāng)且僅當(dāng)時(shí)，，即； 又由于數(shù)列的周期性，故當(dāng)時(shí)，滿足要求的只有三個(gè)，即 從而當(dāng)時(shí)，滿足要求的的和為： . 下面我們著重對Fetmat小定理及其應(yīng)用來舉例： 例3．求證：對于任意整數(shù)，是一個(gè)整數(shù)。 證明：令，則只需證是15的倍數(shù)即可。 由3，5是素?cái)?shù)及Fetmat小定理得，，則 ； 而（3，5）=1，故，即是15的倍數(shù)。所以是整數(shù)。 例4．求證：（為任意整數(shù)）。 證明：令，則； 所以含有因式 由Fetmat小定理，知13|7| 又13，7，5，3，2兩兩互素，所以2730=能整除。 推薦精選 例5．設(shè)是直角三角形的三邊長。如果是整數(shù)，求證：可以被30整除。 證明：不妨設(shè)是直角三角形的斜邊長，則。 若2 ，2 ，2 c，則，又因?yàn)槊埽? 所以2|. 若3 ，3 ，3 c，因?yàn)?，則，又，矛盾！從而3|. 若 5 ，5 ，5 c，因?yàn)?，? 所以或0(mod5)與矛盾！ 從而5|. 又(2,3,5)=1，所以30|. 下面講述中國剩余定理的應(yīng)用 例6．證明：對于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都有大于1的平方因子。 證明：由于素?cái)?shù)有無窮多個(gè)，故我們可以取個(gè)互不相同的素?cái)?shù)，而考慮同余組 ① 因?yàn)轱@然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個(gè)數(shù)分別被平方數(shù)整除。 注：（1）本題的解法體現(xiàn)了中國剩余定理的一個(gè)基本功效，它常常能將“找連續(xù)個(gè)正整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找個(gè)兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。 （2）本題若不直接使用素?cái)?shù)，也中以采用下面的變異方法：由費(fèi)爾馬數(shù)兩兩互素，故將①中的轉(zhuǎn)化為后，相應(yīng)的同余式也有解，同樣可以導(dǎo)出證明。 例7．證明：對于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都不是冪數(shù)。 分析：我們來證明，存在連續(xù)個(gè)正整數(shù)，其中每一個(gè)數(shù)都至少有一個(gè)素因子，在這個(gè)數(shù)的標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個(gè)數(shù)不是冪數(shù)。 證明：取個(gè)互不相同的素?cái)?shù)，考慮同余組 因?yàn)轱@然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。 對于因?yàn)?，故，但由①式可?，即在的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，故都不是冪數(shù)。 例8． 設(shè)是給定的偶數(shù)，且是偶數(shù)。 證明：存在整數(shù)使得，且。 推薦精選 證明：我們先證明，當(dāng)為素?cái)?shù)冪時(shí)結(jié)論成立。實(shí)際上，能夠證明，存在使 且： 若，則條件表明為偶數(shù)，此時(shí)可取； 若，則與中有一對滿足要求。 一般情形下，設(shè)是的一個(gè)標(biāo)準(zhǔn)分解，上面已經(jīng)證明，對每個(gè)存在整數(shù)使得且，而由中國剩余定理， 同余式 ①有解， 同余式 ②有解。 現(xiàn)不難驗(yàn)證解符合問題中的要求：因，故 ， 于是，又由①②知， 故。 注：此題的論證表現(xiàn)了中國剩余定理最為基本的作用：將一個(gè)關(guān)于任意正整數(shù)的問題，化為為素?cái)?shù)冪的問題，而后者往往是比較好處理的。 練習(xí)： 1．設(shè)是給定的素?cái)?shù)，證明：數(shù)列中有無窮多項(xiàng)被整除。 2．求證：=為整值多項(xiàng)式。 3．?dāng)?shù)列：1，31，331，3331，………中有無窮多個(gè)合數(shù)。 4．設(shè)為任意給定的正整數(shù)，證明：存在連續(xù)個(gè)正整數(shù)，其中每一個(gè)都不是素?cái)?shù)的冪。 5．設(shè)為正整數(shù)，具有性質(zhì)：等式對所有的正整數(shù)成立。 證明：，其中是某個(gè)整數(shù)。 第六節(jié)　不定方程 所謂不定方程，是指未知數(shù)的個(gè)數(shù)多于方程個(gè)數(shù)，且未知數(shù)受到某些（如要求是有理數(shù)、整數(shù)或正整數(shù)等等）的方程或方程組。不定方程也稱為丟番圖方程，是數(shù)論的重要分支學(xué)科，也是歷史上最活躍的數(shù)學(xué)領(lǐng)域之一。不定方程的內(nèi)容十分豐富，與代數(shù)數(shù)論、幾何數(shù)論、集合數(shù)論等等都有較為密切的聯(lián)系。不定方程的重要性在數(shù)學(xué)競賽中也得到了充分的體現(xiàn)，每年世界各地的數(shù)學(xué)競賽吉，不定方程都占有一席之地；另外它也是培養(yǎng)學(xué)生思維能力的好材料，數(shù)學(xué)競賽中的不定方程問題，不僅要求學(xué)生對初等數(shù)論的一般理論、方法有一定的了解，而且更需要講究思想、方法與技巧，創(chuàng)造性的解決問題。在本節(jié)我們來看一看不定方程的基礎(chǔ)性的題目。 基礎(chǔ)知識(shí) 1．不定方程問題的常見類型： （1）求不定方程的解； （2）判定不定方程是否有解； （3）判定不定方程的解的個(gè)數(shù)（有限個(gè)還是無限個(gè)）。 推薦精選 2．解不定方程問題常用的解法： （1）代數(shù)恒等變形：如因式分解、配方、換元等； （2）不等式估算法：利用不等式等方法，確定出方程中某些變量的范圍，進(jìn)而求解； （3）同余法：對等式兩邊取特殊的模（如奇偶分析），縮小變量的范圍或性質(zhì)，得出不定方程的整數(shù)解或判定其無解； （4）構(gòu)造法：構(gòu)造出符合要求的特解，或構(gòu)造一個(gè)求解的遞推式，證明方程有無窮多解； （5）無窮遞推法。 以下給出幾個(gè)關(guān)于特殊方程的求解定理： （一）二元一次不定方程（組） 定義1.形如(不同時(shí)為零)的方程稱為二元一次不定方程。 定理1.方程有解的充要是； 定理2.若，且為的一個(gè)解，則方程的一切解都可以表示成 為任意整數(shù))。 定理3.元一次不定方程，()有解的充要條件是. 方法與技巧： 1．解二元一次不定方程通常先判定方程有無解。若有解，可先求一個(gè)特解，從而寫出通解。當(dāng)不定方程系數(shù)不大時(shí)，有時(shí)可以通過觀察法求得其解，即引入變量，逐漸減小系數(shù)，直到容易得其特解為止； 2．解元一次不定方程時(shí)，可先順次求出， ……，.若 ，則方程無解；若|，則方程有解，作方程組： 求出最后一個(gè)方程的一切解，然后把的每一個(gè)值代入倒數(shù)第二個(gè)方程，求出它的一切解，這樣下去即可得方程的一切解。 3．個(gè)元一次不定方程組成的方程組，其中，可以消去個(gè)未知數(shù)，從而消去了個(gè)不定方程，將方程組轉(zhuǎn)化為一個(gè)元的一次不定方程。 （二）高次不定方程（組）及其解法 1．因式分解法：對方程的一邊進(jìn)行因式分解，另一邊作質(zhì)因式分解，然后對比兩邊，轉(zhuǎn)而求解若干個(gè)方程組； 2．同余法：如果不定方程有整數(shù)解，則對于任意，其整數(shù)解滿足，利用這一條件，同余可以作為探究不定方程整數(shù)解的一塊試金石； 3．不等式估計(jì)法：利用不等式工具確定不定方程中某些字母的范圍，再分別求解； 4．無限遞降法：若關(guān)于正整數(shù)的命題對某些正整數(shù)成立，設(shè)是使成立的最小正整數(shù)，可以推出：存在，使得 推薦精選 成立，適合證明不定方程無正整數(shù)解。 方法與技巧： 1．因式分解法是不定方程中最基本的方法，其理論基礎(chǔ)是整數(shù)的唯一分解定理，分解法作為解題的一種手段，沒有因定的程序可循，應(yīng)具體的例子中才能有深刻地體會(huì)； 2．同余法主要用于證明方程無解或?qū)С鲇薪獾谋匾獥l件，為進(jìn)一步求解或求證作準(zhǔn)備。同余的關(guān)鍵是選擇適當(dāng)?shù)哪?，它需要?jīng)過多次嘗試； 3．不等式估計(jì)法主要針對方程有整數(shù)解，則必然有實(shí)數(shù)解，當(dāng)方程的實(shí)數(shù)解為一個(gè)有界集，則著眼于一個(gè)有限范圍內(nèi)的整數(shù)解至多有有限個(gè)，逐一檢驗(yàn)，求出全部解；若方程的實(shí)數(shù)解是無界的，則著眼于整數(shù)，利用整數(shù)的各種性質(zhì)產(chǎn)生適用的不等式； 4．無限遞降法論證的核心是設(shè)法構(gòu)造出方程的新解，使得它比已選擇的解“嚴(yán)格地小”，由此產(chǎn)生矛盾。 （三）特殊的不定方程 1．利用分解法求不定方程整數(shù)解的基本思路： 將轉(zhuǎn)化為后，若可分解為，則解的一般形式為，再取舍得其整數(shù)解； 2．定義2：形如的方程叫做勾股數(shù)方程，這里為正整數(shù)。 對于方程，如果，則，從而只需討論的情形，此時(shí)易知兩兩互素，這種兩兩互素的正整數(shù)組叫方程的本原解。 定理3.勾股數(shù)方程滿足條件的一切解可表示為： ，其中且為一奇一偶。 推論：勾股數(shù)方程的全部正整數(shù)解（的順序不加區(qū)別）可表示為： 其中是互質(zhì)的奇偶性不同的一對正整數(shù)，是一個(gè)整數(shù)。 勾股數(shù)不定方程的整數(shù)解的問題主要依據(jù)定理來解決。 3．定義3.方程且不是平方數(shù))是的一種特殊情況，稱為沛爾(Pell)方程。 這種二元二次方程比較復(fù)雜，它們本質(zhì)上歸結(jié)為雙曲線方程的研究，其中都是整數(shù)，且非平方數(shù)，而。它主要用于證明問題有無數(shù)多個(gè)整數(shù)解。對于具體的可用嘗試法求出一組成正整數(shù)解。如果上述pell方程有正整數(shù)解，則稱使的最小的正整數(shù)解為它的最小解。 定理4.Pell方程且不是平方數(shù))必有正整數(shù)解，且若設(shè)它的最小解為，則它的全部解可以表示成： 推薦精選 . 上面的公式也可以寫成以下幾種形式： （1）；（2）；（3）. 定理5.Pell方程且不是平方數(shù))要么無正整數(shù)解，要么有無窮多組正整數(shù)解，且在后一種情況下，設(shè)它的最小解為，則它的全部解可以表示為 定理6. （費(fèi)爾馬（Fermat）大定理）方程為整數(shù))無正整數(shù)解。 費(fèi)爾馬（Fermat）大定理的證明一直以來是數(shù)學(xué)界的難題，但是在1994年6月，美國普林斯頓大學(xué)的數(shù)學(xué)教授A.Wiles完全解決了這一難題。至此，這一困擾了人們四百多年的數(shù)學(xué)難題終于露出了廬山真面目，脫去了其神秘面紗。 典例分析 例1．求不定方程的整數(shù)解。 解：先求的一組特解，為此對37，107運(yùn)用輾轉(zhuǎn)相除法： ，， 將上述過程回填，得： 由此可知，是方程的一組特解，于是，是方程的一組特解，因此原方程的一切整數(shù)解為：。 例2．求不定方程的所有正整數(shù)解。 解：用原方程中的最小系數(shù)7去除方程的各項(xiàng)，并移項(xiàng)得： 因?yàn)槭钦麛?shù)，故也一定是整數(shù)，于是有，再用5去除比式的兩邊，得，令為整數(shù)，由此得。 經(jīng)觀察得是最后一個(gè)方程的一組解，依次回代，可求得原方程的一組特解：，所以原方程的一切整數(shù)解為：。 例3．求不定方程的正整數(shù)解。 解：顯然此方程有整數(shù)解。先確定系數(shù)最大的未知數(shù)的取值范圍，因?yàn)榈淖钚≈禐?，所以。 推薦精選 當(dāng)時(shí)，原方程變形為，即，由上式知是偶數(shù)且故方程組有5組正整數(shù)解，分別為，，，，； 當(dāng)時(shí)，原方程變形為，即，故方程有3組正整數(shù)解，分別為：，，； 當(dāng)時(shí)，原方程變形為，即，故方程有2組正整數(shù)解，分別為：，； 當(dāng)時(shí)，原方程變形為，即，故方程只有一組正整數(shù)解，為。 故原方程有11組正整數(shù)解（如下表）： 2 4 6 8 10 2 4 6 2 4 2 13 10 7 4 1 9 6 3 5 2 1 1 1 1 1 1 2 2 2 3 3 4 例4．求出方程的所有正整數(shù)解。 解：先求最小解。令 當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)，。所以的最小解為，于是： 例5．在