競賽數(shù)學(xué)中的初等數(shù)論精華版

1、競賽數(shù)學(xué)中的初等數(shù)論賈廣素編著2006-8-21序言數(shù)論是競賽數(shù)學(xué)中最重要的一部分，特別是在1991年，IMO在中國舉行，國際上戲稱那一年為數(shù)論年，因為6道IMO試題中有5道與數(shù)論有關(guān)。數(shù)論的魅力在于它可以適合小孩到老頭，只要有算術(shù)基礎(chǔ)的人均可以研究數(shù)論在前幾年還盛傳廣東的一位農(nóng)民數(shù)學(xué)愛好者證明了哥德巴赫猜想，當(dāng)然，這一謠言最終被澄清了?？墒沁@也說明了最難的數(shù)論問題，適合于任何人去研究。初等數(shù)論最基礎(chǔ)的理論在于整除，由它可以演化出許多數(shù)論定理。做數(shù)論題，其實只要整除理論即可，然而要很快地解決數(shù)論問題，則要我們多見識，以及學(xué)習(xí)大量的解題技巧。這里我們介紹一下數(shù)論中必需的一個內(nèi)容：對于，滿足，其中

2、。除了在題目上選擇我們努力做到精挑細選，在內(nèi)容的安排上我們也盡量做到講解詳盡，明白。相信通過對本書學(xué)習(xí)，您可以對數(shù)論有一個大致的了解。希望我們共同學(xué)習(xí)，相互交流，在學(xué)習(xí)交流中，共同提高。編者：賈廣素2006-8-21于山東濟寧第一節(jié)整數(shù)的p進位制及其應(yīng)用正整數(shù)有無窮多個，為了用有限個數(shù)字符號表示出無限多個正整數(shù)，人們發(fā)明了進位制，這是一種位值記數(shù)法。進位制的創(chuàng)立體現(xiàn)了有限與無限的對立統(tǒng)一關(guān)系，近幾年來，國內(nèi)與國際競賽中關(guān)于“整數(shù)的進位制”有較多的體現(xiàn)，比如處理數(shù)字問題、處理整除問題及處理數(shù)列問題等等。在本節(jié)，我們著重介紹進位制及其廣泛的應(yīng)用?；A(chǔ)知識給定一個m位的正整數(shù)A，其各位上的數(shù)字分別記

3、為，則此數(shù)可以簡記為：（其中）。由于我們所研究的整數(shù)通常是十進制的，因此A可以表示成10的次多項式，即，其中且，像這種10的多項式表示的數(shù)常常簡記為。在我們的日常生活中，通常將下標(biāo)10省略不寫，并且連括號也不用，記作，以后我們所講述的數(shù)字，若沒有指明記數(shù)式的基，我們都認(rèn)為它是十進制的數(shù)字。但是隨著計算機的普及，整數(shù)的表示除了用十進制外，還常常用二進制、八進制甚至十六進制來表示。特別是現(xiàn)代社會人們越來越顯示出對二進制的興趣，究其原因，主要是二進制只使用0與1這兩種數(shù)學(xué)符號，可以分別表示兩種對立狀態(tài)、或?qū)α⒌男再|(zhì)、或?qū)α⒌呐袛?，所以二進制除了是一種記數(shù)方法以外，它還是一種十分有效的數(shù)學(xué)工具，可以用

4、來解決許多數(shù)學(xué)問題。為了具備一般性，我們給出正整數(shù)A的p進制表示：，其中且。而仍然為十進制數(shù)字，簡記為。典例分析例1將一個十進制數(shù)字2004（若沒有指明，我們也認(rèn)為是十進制的數(shù)字）轉(zhuǎn)化成二進制與八進制，并將其表示成多項式形式。分析與解答分析：用2作為除數(shù)（若化為p進位制就以p作為除數(shù)），除2004商1002，余數(shù)為0；再用2作為除數(shù)，除1002商501余數(shù)為0；如此繼續(xù)下去，起到商為0為止。所得的各次余數(shù)按從左到右的順序排列出來，便得到所化出的二進位制的數(shù)。解：各次商數(shù)被除數(shù)除數(shù)013715316212525050110022004211111010100各次余數(shù)故，；同理，有，。處理與數(shù)字有

5、關(guān)的問題，通常利用定義建立不定方程來求解。例2求滿足的所有三位數(shù)。（1988年上海市競賽試題）解：由于，則，從而；當(dāng)時，；當(dāng)時，；當(dāng)時，；當(dāng)時，；當(dāng)時，；于是所求的三位數(shù)只有512。例3一個四位數(shù)，它的個位數(shù)字與百位數(shù)字相同。如果將這個四位數(shù)的數(shù)字順序顛倒過來（即個位數(shù)字與千位數(shù)字互換，十位數(shù)字與百位數(shù)字互換），所得的新數(shù)減去原數(shù)，所得的差為7812，求原來的四位數(shù)。（1979年云南省競賽題）解：設(shè)該數(shù)的千位數(shù)字、百位數(shù)字、十位數(shù)字分別為，則原數(shù)顛倒后的新數(shù)由得7812即比較式兩端百位、十位、個位數(shù)字得由于原四位數(shù)的千位數(shù)字不能為0，所以，從而，又顯然百位數(shù)字，所以。所以所求的原四位數(shù)為197

6、9。例4遞增數(shù)列1,3，4,9，10,12,13，是由一些正整數(shù)組成，它們或是3的冪，或是若個不同的3的冪之和，求該數(shù)列的第100項。（第4屆美國數(shù)學(xué)邀請賽試題）解：將已知數(shù)列寫成3的方冪形式：易發(fā)現(xiàn)其項數(shù)恰好是自然數(shù)列對應(yīng)形式的二進制表示：即由于100所以原數(shù)列的第100項為。例51987可以在b進制中寫成三位數(shù)，如果，試確定所有可能的和。（1987年加拿大數(shù)學(xué)競賽試題）解：易知，從而，即，由知。由知故；又因為有12個正約數(shù)，分別為1,2，3,6，9,18,109,218,327,654,981,1962，所以，從而。又由知例6設(shè)是五位數(shù)（第一個數(shù)碼不是零），是由取消它的中間一個數(shù)碼后所成的

7、四位數(shù)，試確定一切使得是整數(shù)。（第3屆加拿大數(shù)學(xué)競賽試題）解：設(shè)，其中且；而是整數(shù)，可證，即即，這顯然是成立的；又可證，即即，這顯然也是正確的。于是，即，又因為是整數(shù)，從而；于是，即即，而但3102知為正整數(shù)）從而，顯然，因而推得其中。例7若且是其各位數(shù)字和的倍數(shù)，這樣的有多少個？（2004年南昌競賽試題）解：（1）若為個位數(shù)字時，顯然適合，這種情況共有9種；（2）若為100時，也適合；（3）若為二位數(shù)時，不妨設(shè)，則，由題意得即即也就是；若顯然適合，此種情況共有9種；若，則由，故若，則顯然可以，此時共有2810個；若（）9，則或，這樣的數(shù)共有24,42,48,84共4個；綜上所述，共有9191

8、0433個。例8如果一個正整數(shù)在三進制下表示的各數(shù)字之和可以被3整除，那么我們稱為“好的”，則前2005個“好的”正整數(shù)之和是多少？（2005年中國奧林匹克協(xié)作體夏令營試題）解：首先考慮“好的”非負(fù)整數(shù)，考察如下兩個引理：引理1.在3個連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有1個是“好的”。證明：在這三個非負(fù)整數(shù)的三進制表示中，0,1，2各在最后一位出現(xiàn)一次，其作各位數(shù)字相同，于是三個數(shù)各位數(shù)字之和是三個連續(xù)的正整數(shù)，其中有且僅有一個能被3整除（即“好的”），引理1得證。引理2.在9個連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有3個是“好的”。把這3個“好的”非負(fù)整數(shù)化成三進制，0,1，2恰好在這三個

9、三進制數(shù)的最后一位各出現(xiàn)一次。證明：由引理1不難得知在9個連續(xù)非負(fù)整數(shù)（是非負(fù)整數(shù)）中，有且僅有3個是“好的”。另一方面，在這三個“好的”非負(fù)整數(shù)的三進制表示中，最高位與倒數(shù)第三位完全相同，倒數(shù)第二位分別取0,1，2。若它使它們成為“好的”非負(fù)整數(shù)，則最后一位不相同，引理2得證。將所有“好的”非負(fù)整數(shù)按從小到大的順序排成一列，設(shè)第2004個“好的”非負(fù)整數(shù)為，根據(jù)引理1，得，即。設(shè)前個“好的”正整數(shù)之和為，由于前2003個“好的”正整數(shù)之和等于前2004個“好的”非負(fù)整數(shù)之和。因此；又因為和都是“好的”正整數(shù)。因此前2005年“好的”正整數(shù)之和是：。第二節(jié) 整數(shù)的性質(zhì)及其應(yīng)用（1）基礎(chǔ)知識整數(shù)

10、的性質(zhì)有很多，這里我們著重討論整數(shù)的整除性、整數(shù)的奇偶性，質(zhì)數(shù)與合數(shù)、完全平方數(shù)及整數(shù)的尾數(shù)等幾個方面的應(yīng)用。1整除的概念及其性質(zhì)在高中數(shù)學(xué)競賽中如果不加特殊說明，我們所涉及的數(shù)都是整數(shù)，所采用的字母也表示整數(shù)。定義：設(shè)是給定的數(shù)，若存在整數(shù)，使得則稱整除，記作，并稱是的一個約數(shù)(因子)，稱是的一個倍數(shù)，如果不存在上述，則稱不能整除記作 。由整除的定義，容易推出以下性質(zhì)：(1)若且，則(傳遞性質(zhì))；(2)若且，則即為某一整數(shù)倍數(shù)的整數(shù)之集關(guān)于加、減運算封閉。若反復(fù)運用這一性質(zhì)，易知及，則對于任意的整數(shù)有。更一般，若都是的倍數(shù)，則。或著，則其中；(3)若，則或者，或者，因此若且，則；(4)互質(zhì)，

11、若，則；(5)是質(zhì)數(shù)，若，則能整除中的某一個；特別地，若是質(zhì)數(shù)，若，則；(6)(帶余除法)設(shè)為整數(shù)，則存在整數(shù)和，使得，其中，并且和由上述條件唯一確定；整數(shù)被稱為被除得的(不完全)商，數(shù)稱為被除得的余數(shù)。注意：共有種可能的取值：0,1，。若，即為被整除的情形；易知，帶余除法中的商實際上為（不超過的最大整數(shù)），而帶余除法的核心是關(guān)于余數(shù)的不等式：。證明的基本手法是將分解為與一個整數(shù)之積，在較為初級的問題中，這種數(shù)的分解常通過在一些代數(shù)式的分解中取特殊值而產(chǎn)生，下面兩個分解式在這類論證中應(yīng)用很多，見例1、例2。若是正整數(shù)，則；若是正奇數(shù)，則；（在上式中用代）(7)如果在等式中取去某一項外，其余各項

12、均為的倍數(shù)，則這一項也是的倍數(shù)；(8)n個連續(xù)整數(shù)中，有且只有一個是n的倍數(shù)；(9)任何n個連續(xù)的整數(shù)之積一定是n!的倍數(shù)，特別地，三個連續(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ù)；即任意多個偶數(shù)的和、差、積仍為偶數(shù)，奇數(shù)個奇數(shù)的和、差仍為奇數(shù)，偶數(shù)個奇數(shù)的和、差為偶數(shù)，奇數(shù)與偶數(shù)的和為奇數(shù)，和為偶數(shù)；（2）奇數(shù)的平方都可以表示成的形式，偶數(shù)的平方可以表示為或的形式；（3）任何一個正整數(shù)，都可以寫成的形式，其中為負(fù)整數(shù)，為奇數(shù)。（4）若有限個整數(shù)之積為奇數(shù)，則其中每個整數(shù)都是奇數(shù)；若有限個整數(shù)之積

13、為偶數(shù)，則這些整數(shù)中至少有一個是偶數(shù)；兩個整數(shù)的和與差具有相同的奇偶性；偶數(shù)的平方根若是整數(shù)，它必為偶數(shù)。3完全平方數(shù)及其性質(zhì)能表示為某整數(shù)的平方的數(shù)稱為完全平方數(shù)，簡稱平方數(shù)。平方數(shù)有以下性質(zhì)與結(jié)論：（1）平方數(shù)的個位數(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ù)的個位數(shù)一定是6；（5）不能被3整除的數(shù)的平方被3除余1，能被3整數(shù)的數(shù)的平方能被3整除。因而，平方數(shù)被9也合乎的余數(shù)為0,1，4,7，且此平方數(shù)的各位數(shù)字的和被9除的余數(shù)也只能是0,1，

14、4,7；（6）平方數(shù)的約數(shù)的個數(shù)為奇數(shù)；（7）任何四個連續(xù)整數(shù)的乘積加1，必定是一個平方數(shù)。（8）設(shè)正整數(shù)之積是一個正整數(shù)的次方冪（），若（）1，則都是整數(shù)的次方冪。一般地，設(shè)正整數(shù)之積是一個正整數(shù)的次方冪（），若兩兩互素，則都是正整數(shù)的k次方冪。4整數(shù)的尾數(shù)及其性質(zhì)整數(shù)的個位數(shù)也稱為整數(shù)的尾數(shù)，并記為。也稱為尾數(shù)函數(shù)，尾數(shù)函數(shù)具有以下性質(zhì)：（1）；（2）；（3）；（4）；（5）若，則；（6）；（7）；（8）5整數(shù)整除性的一些數(shù)碼特征（即常見結(jié)論）（1）若一個整數(shù)的未位數(shù)字能被2（或5）整除，則這個數(shù)能被2（或5）整除，否則不能；（2）一個整數(shù)的數(shù)碼之和能被3（或9）整除，則這個數(shù)能被3（或9

15、）整除，否則不能；（3）若一個整數(shù)的未兩位數(shù)字能被4（或25）整除，則這個數(shù)能被4（或25）整除，否則不能；（4）若一個整數(shù)的未三位數(shù)字能被8（或125）整除，則這個數(shù)能被8（或125）整除，否則不能；（5）若一個整數(shù)的奇位上的數(shù)碼之和與偶位上的數(shù)碼之和的差是11的倍數(shù)，則這個數(shù)能被11整除，否則不能。6質(zhì)數(shù)與合數(shù)及其性質(zhì)1正整數(shù)分為三類：（1）單位數(shù)1；（2）質(zhì)數(shù)（素數(shù)）：一個大于1的正整數(shù)，如果它的因數(shù)只有1和它本身，則稱為質(zhì)（素）數(shù)；（3）如果一個自然數(shù)包含有大于1而小于其本身的因子，則稱這個自然數(shù)為合數(shù)。2有關(guān)質(zhì)（素）數(shù)的一些性質(zhì)（1）若，則的除1以外的最小正因數(shù)是一個質(zhì)（素）數(shù)。如果

16、，則；（2）若是質(zhì)（素）數(shù)，為任一整數(shù)，則必有或（）1；（3）設(shè)為個整數(shù)，為質(zhì)（素）數(shù)，且，則必整除某個（）；（4）（算術(shù)基本定理）任何一個大于1的正整數(shù)，能唯一地表示成質(zhì)（素）因數(shù)的乘積（不計較因數(shù)的排列順序）；（5）任何大于1的整數(shù)能唯一地寫成的形式，其中為質(zhì)（素）數(shù)（）。上式叫做整數(shù)的標(biāo)準(zhǔn)分解式；（6）若的標(biāo)準(zhǔn)分解式為，的正因數(shù)的個數(shù)記為，則。典例分析例1證明：被1001整除。證明：所以整除。例2對正整數(shù)，記為的十進制表示中數(shù)碼之和。證明：的充要條件是。證明：設(shè)（這里，且），則，于是有對于，知，故式右端個加項中的每一個都是9的倍數(shù)，從而由整除的性質(zhì)可知它們的和也能被9整除，即。由此可易推

17、出結(jié)論的兩個方面。例3設(shè)是一個奇數(shù)，證明L對于任意正整數(shù)，數(shù)不能被整除。證明：時，結(jié)論顯然成立。設(shè)，記所說的和為A，則：。由k是正奇數(shù)，從而結(jié)于每一個，數(shù)被整除，故被除得余數(shù)為2，從而A不可能被整除（注意）。例4設(shè)是正整數(shù)，證明：（）（）。證明：首先，當(dāng)時，易知結(jié)論成立。事實上，時，結(jié)論平凡；當(dāng)時，結(jié)果可由推出來（注意）。最后，的情形可化為上述特殊情形：由帶余除法而，由于，從而由若是正整數(shù)，則知；而，故由上面證明了的結(jié)論知（注意時結(jié)論平凡），從而當(dāng)時，也有（）（）。這就證明了本題的結(jié)論。 例5設(shè)正整數(shù)滿足，證明：不是質(zhì)（素）數(shù)。證法一：由，可設(shè)其中。由意味著有理數(shù)的分子、分母約去了某個正整數(shù)后

18、得既約分?jǐn)?shù)，因此，同理，存在正整數(shù)使得因此，是兩個大于1的整數(shù)之積，從而不是素數(shù)。注：若正整數(shù)適合，則可分解為及的形式，這一結(jié)果在某些問題的解決中很有作用。證法二：由，得，因此，因為是整數(shù)，故也是整數(shù)。若它是一個素數(shù)，設(shè)為，則由可見整除，從而素數(shù)整除或。不妨設(shè)，則，結(jié)合推出，而這是不可能的（因為）。例6求出有序整數(shù)對（）的個數(shù)，其中，是完全平方數(shù)。（1999年美國數(shù)學(xué)邀請賽試題）解：由于，可得：。又，于是若是完全平方數(shù)，則必有。然而，于是必有，即，此時，。所以所求的有序整數(shù)對（）共有98對：。例7證明：若正整數(shù)滿足，則和都是完全平方數(shù)。（2006年山東省第二屆夏令營試題）證法一：已知關(guān)系式即為

19、（）（）若（或者說中有一個為0時），結(jié)論顯然。不妨設(shè)且，令，則，從而，將其代入得因為，所以，從而；而式又可寫成；因為且，所以所以，從而。所以，所以，從而為完全平方數(shù)。所以也是完全平方數(shù)。證法二：已知關(guān)系式即為（）（）論證的關(guān)鍵是證明正整數(shù)與互素。記（，）。若，則有素因子，從而由知。因為是素數(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

20、+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數(shù)列的通項公式為，記，求所有的正整數(shù)，使得能被8整除（2005年上海競賽試題）解：記注意到，可得因此，Sn+2除以8的余數(shù)，完全由Sn+1、Sn除以8的余數(shù)確定，故由(*)式可以算出各項除以8的余數(shù)依次是1,3，0,5，7,0，1,3，它是一個以6為周期的數(shù)列，從而故當(dāng)且僅當(dāng)練習(xí)題1證明：如果和都是大于3的素數(shù)，則6是的因子。證明：因為是奇數(shù)

21、，所以2是的因子。又因為，除以3的余數(shù)各不相同，而與都不能被3整數(shù)。于是6是的因子。2設(shè)，證明：；解：由，故（）。又因為，從而，于是由整除的性質(zhì)知。3證明：對于任意正整數(shù)，數(shù)不能被整除。證明：只需證2（）2（）即可。因為若是正整數(shù)，則；若是正奇數(shù)，則；故；， 所以2（）。又因為，所以2，所以2（）2即（）2（）命題得證。4已知為正奇數(shù)，求證：。證明：因為若是正整數(shù)，則；若是正奇數(shù)，則；所以，從而；，從而；，從而；又且，所以。5設(shè)a、b、c為滿足不等式1abc的整數(shù)，且（ab-1）（bc-1）（ca-1）能被abc整除，求所有可能數(shù)組（a，b，c）.（1989年上海競賽試題）解  （a

22、b-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.若a3，此時1=-矛盾.已知a1.   只有a=2.當(dāng)a=2時，代入中得2b+2c-1=bc，即   1=0b4，知b=3，從而易得c=5. 說明：在此例中通過對因數(shù)k的范圍討論，從而逐步確定a、b、c是一項重要解題技巧.第三節(jié)整數(shù)的性質(zhì)及其應(yīng)用（2）基礎(chǔ)知識最大公約數(shù)與最小公倍數(shù)是數(shù)論中的一個重要的概念，這里

23、我們主要討論兩個整數(shù)互素、最大公約數(shù)、最小公倍數(shù)等基本概念與性質(zhì)。定義1.（最大公約數(shù)）設(shè)不全為零，同時整除的整數(shù)（如）稱為它們的公約數(shù)。因為不全為零，故只有有限多個，我們將其中最大一個稱為的最大公約數(shù)，用符號（）表示。顯然，最大公約數(shù)是一個正整數(shù)。當(dāng)（）1（即的公約數(shù)只有）時，我們稱與互素（互質(zhì)）。這是數(shù)論中的非常重要的一個概念。同樣，如果對于多個（不全為零）的整數(shù)，可類似地定義它們的最大公約數(shù)（）。若（）1，則稱互素。請注意，此時不能推出兩兩互素；但反過來，若（）兩兩互素，則顯然有（）1。由最大公約數(shù)的定義，我們不難得出最大公約數(shù)的一些簡單性質(zhì)：例如任意改變的符號，不改變（）的值，即；（）

24、可以交換，（）（）；（）作為的函數(shù)，以為周期，即對于任意的實數(shù)，有（）（）等等。為了更詳細地介紹最大公約數(shù)，我們給出一些常用的一些性質(zhì)：（1）設(shè)是不全為0的整數(shù)，則存在整數(shù)，使得；（2）（裴蜀定理）兩個整數(shù)互素的充要條件是存在整數(shù)，使得；事實上，條件的必要性是性質(zhì)（1）的一個特例。反過來，若有使等式成立，不妨設(shè)，則，故及，于是，即，從而。（3）若，則，即的任何一個公約數(shù)都是它們的最大公約數(shù)的約數(shù)；（4）若，則；（5）若，則，因此兩個不互素的整數(shù)，可以自然地產(chǎn)生一對互素的整數(shù)；（6）若，則，也就是說，與一個固定整數(shù)互素的整數(shù)集關(guān)于乘法封閉。并由此可以推出：若，對于有，進而有對有。（7）設(shè)，若，則

25、；（8）設(shè)正整數(shù)之積是一個正整數(shù)的次方冪（），若（）1，則都是整數(shù)的次方冪。一般地，設(shè)正整數(shù)之積是一個正整數(shù)的次方冪（），若兩兩互素，則都是正整數(shù)的次方冪。定義2.設(shè)是兩個非零整數(shù)，一個同時為倍數(shù)的數(shù)稱為它們的公倍數(shù)，的公倍數(shù)有無窮多個，這其中最小的一個稱為的最小公倍數(shù)，記作，對于多個非零實數(shù)，可類似地定義它們的最小公倍數(shù)。最小公倍數(shù)主要有以下幾條性質(zhì)：（1）與的任一公倍數(shù)都是的倍數(shù)，對于多于兩個數(shù)的情形，類似結(jié)論也成立；（2）兩個整數(shù)的最大公約數(shù)與最小公倍滿足：（但請注意，這只限于兩個整數(shù)的情形，對于多于兩個整數(shù)的情形，類似結(jié)論不成立）；（3）若兩兩互素，則；（4）若，且兩兩互素，則。典例分

26、析例1 設(shè)是正整數(shù)，且，它們的最小公倍數(shù)是最大公約數(shù)的120倍，求。解：設(shè)，則，其中且，于是。所以即由及（2）可得：。由（1）可知只能取從而或29，故或。例2設(shè)，則。證明：設(shè)，則，其中。于是，已知條件轉(zhuǎn)化為，故更有，從而轉(zhuǎn)化為，但是，故，結(jié)合，知必有，同時，因此。例3設(shè)正整數(shù)的最大公約數(shù)是1，并且，證明是一個完全平方數(shù)。證明：設(shè)，則，其中，由于，故，現(xiàn)在問題中的等式可以轉(zhuǎn)化為由此可見整除。因為，故，同樣可得，再由便可以推出。設(shè)，其中是一個正整數(shù)。一方面，顯然整除；另一方面，結(jié)合式，得，故，從而，但，故。因此，故，這樣就證明了是一個完全平方數(shù)。例4 都是正整數(shù)，是否存在整數(shù)使得對任意的正整數(shù)，與

27、互質(zhì)？解：令，則，于是存在整數(shù)使得，令，則對任意的正整數(shù)，設(shè)，有即，而，所以，即對任意的正整數(shù)，（，）1。例5 已知，證明：對于任意的正整數(shù)，都有兩兩互素。（2002年克羅地亞競賽試題）證明：設(shè)（其中出現(xiàn)次）。由，故對于有，則是含有0次項的多項式。因此，除以的余數(shù)為1。設(shè)整數(shù)可整除和，又，則當(dāng)除以時余數(shù)為1，即1。所以，矛盾！從而可知兩兩互素。例6求出所有的正整數(shù)對，使得是一個整數(shù)。（2006年山東省第二屆夏令營試題）解：由于且，所以是對稱的。不妨設(shè)。當(dāng)時，則，從而2；當(dāng)時，若時，則有，所以或3；若時，由于是一個整數(shù)，從而使得即，所以。又由于，所以。所以，從而得或3，所以；綜上知所有的為（2,

28、2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).例7已知，且，試問的充要條件是嗎？（2006年山東省第二屆夏令營試題）分析：因為，所以；又，所以；令，則有又因為，所以從而上式且為奇數(shù)，即的充要條件是且為奇數(shù)。例8我們知道有1個質(zhì)因子，且；有2個質(zhì)因子，且如此下去，我們可以猜想： 至少有個質(zhì)因子，且。試證明之。（2006年山東省第二屆夏令營試題）證明：令，則，即要證是整數(shù)且有個質(zhì)因子。下用數(shù)學(xué)歸納法證明是整數(shù)。時，結(jié)論顯然；假設(shè)時，成立；當(dāng)1時，因為(1)3+1=3323；因為，所以，即是整數(shù)。下證至少有個質(zhì)因子。3323()33()23()

29、.因為()，令，則由于(,3)=1，所以(,)=1，從而必有異于質(zhì)因子的質(zhì)因子，所以至少有個質(zhì)因子。證畢！練習(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è)，于是。因為故可知。但，因而。這與是

30、整數(shù)矛盾！證畢。4設(shè)a,b是不全為0的整數(shù)，一切形如ax+by的數(shù)中，最小的正數(shù)是d，試證：d=(a,b).5.記Fn1，試證：(Fn,Fm)=1,這里.第四節(jié)同余同余式性質(zhì)應(yīng)用非常廣泛，在處理某些整除性、進位制、對整數(shù)分類、解不定方程等方面的問題中有著不可替代的功能，與之密切相關(guān)的的數(shù)論定理有歐拉定理、費爾馬定理和中國剩余定理?；A(chǔ)知識三個數(shù)論函數(shù)對于任何正整數(shù)均有定義的函數(shù)，稱為數(shù)論函數(shù)。在初等數(shù)論中，所能用到的無非也就有三個，分別為：高斯(Gauss)取整函數(shù)x及其性質(zhì)，除數(shù)函數(shù)d(n)和歐拉(Euler)函數(shù)和它的計算公式。1 高斯(Gauss)取整函數(shù)設(shè)是實數(shù)，不大于的最大整數(shù)稱為的

31、整數(shù)部分，記為；稱為的小數(shù)部分，記為。例如：0.50，等等。由的定義可得如下性質(zhì)：性質(zhì)1.；性質(zhì)2.；性質(zhì)3.設(shè)，則；性質(zhì)4.;性質(zhì)5.；性質(zhì)6.對于任意的正整數(shù)，都有如下的埃米特恒等式成立：；為了描述性質(zhì)7，我們給出如下記號：若，且，則稱為恰好整除，記為。例如：我們有等等，其實，由整數(shù)唯一分解定理：任何大于1的整數(shù)能唯一地寫成的形式，其中為質(zhì)（素）數(shù)（）。我們還可以得到：。性質(zhì)7.若，則請注意，此式雖然被寫成了無限的形式，但實際上對于固定的，必存在正整數(shù)，使得，因而，故，而且對于時，都有。因此，上式實際上是有限項的和。另外，此式也指出了乘數(shù)的標(biāo)準(zhǔn)分解式中，素因數(shù)的指數(shù)的計算方法。2除數(shù)函數(shù)d

32、(n)正整數(shù)的正因數(shù)的個數(shù)稱為除數(shù)函數(shù)，記為d(n)。這里給出d(n)的計算公式：d(n)，為素數(shù)唯一分解定理中的指數(shù)。為了敘述地更加明確，我們組出素數(shù)唯一分解定理。算術(shù)基本定理（素數(shù)唯一分解定理）：任何一大于1的整數(shù)均可以分解為素數(shù)的乘積，若不考慮素數(shù)乘積的先后順序，則分解式是唯一的。例如：。當(dāng)一個整數(shù)分解成素數(shù)的乘積時，其中有些素數(shù)可以重復(fù)出現(xiàn)。例如在上面的分解式中，2出現(xiàn)了三次。把分解式中相同的素數(shù)的積寫成冪的形式，我們就可以把大于1的正整數(shù)寫成（1）此式稱為的標(biāo)準(zhǔn)分解式。這樣，算術(shù)基本定理也可以描述為大于1的整數(shù)的標(biāo)準(zhǔn)分解式是唯一的（不考慮乘積的先后順序）。推論1.若的標(biāo)準(zhǔn)分解式是（1

33、）式，則是的正因數(shù)的充要條件是：（2）應(yīng)說明（2）不能稱為是的標(biāo)準(zhǔn)分解式，其原因是其中的某些可能取零值（也有可能不含有某個素因數(shù)，因而）推論2.設(shè)，且，若是整數(shù)的次方，則也是整數(shù)的次方。特別地，若是整數(shù)的平方，則也是整數(shù)的平方。3. 歐拉(Euler)函數(shù)設(shè)正整數(shù)0,1，中與互素的個數(shù)，稱之為的歐拉函數(shù)，并記為。若的標(biāo)準(zhǔn)分解式是，則的計算公式是：例如：； .以下我們講述同余的概念：同余的概念是高斯（Gauss）在1800年左右給出的。設(shè)是正整數(shù)，若用去除整數(shù)，所得的余數(shù)相同，則稱為與關(guān)于模同余，記作，否則，稱為與關(guān)于模不同余。定義1.（同余）設(shè)，若，則稱和對模同余，記作；若不然，則稱和對模不同

34、余，記作。例如：，等等。當(dāng)時，則稱是對模的最小非負(fù)剩余。由帶余除法可知，和對模同余的充要條件是與被除得的余數(shù)相同。對于固定的模，模的同余式與通常的等式有許多類似的性質(zhì)：性質(zhì)1. 的充要條件是也即。性質(zhì)2.同余關(guān)系滿足以下規(guī)律：（1）（反身性）；（2）（對稱性）若，則；（3）（傳遞性）若，則；（4）（同余式相加）若，則；（5）（同余式相乘）若，則；反復(fù)利用（4）（5），可以對多個兩個的（模相同的）同余式建立加、減和乘法的運算公式。特別地，由（5）易推出：若，為整數(shù)且，則；但是同余式的消去律一般并不成立，即從未必能推出，可是我們卻有以下結(jié)果：（6）若，則，由此可以推出，若，則有，即在與互素時，可以

35、在原同余式兩邊約去而不改變模（這一點再一次說明了互素的重要性）?，F(xiàn)在提及幾個與模相關(guān)的簡單而有用的性質(zhì)：（7）若，則；（8）若，則；（9）若，則，特別地，若兩兩互素時，則有；性質(zhì)3.若，則；性質(zhì)4.設(shè)是系數(shù)全為整數(shù)的多項式，若，則。這一性質(zhì)在計算時特別有用：在計算大數(shù)字的式子時，可以改變成與它同余的小的數(shù)字，使計算大大地簡化。如例3。定義2.設(shè)，是使成立的最小正整，則稱為對模的階。在取定某數(shù)后，按照同余關(guān)系把彼此同余的整數(shù)歸為一類，這些數(shù)稱為模的剩余類。一個類的任何一個數(shù)，都稱為該類所有數(shù)的剩余。顯然，同類的余數(shù)相同，不同類的余數(shù)不相同，這樣我們就把全體整數(shù)按照模劃分為了個剩余類：。在上述的個

36、剩余類中，每一類任意取一個剩余，可以得到個數(shù)，稱為模的一個完全剩余系。例如關(guān)系模7，下面的每一組數(shù)都是一個完全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。 顯然，一組整數(shù)成為模的完全剩余系只需要滿足兩個條件（1）有個數(shù)；（2）各數(shù)關(guān)于模兩兩不同余。最常用的完全剩余系是最小非負(fù)完全剩余系及絕對值最小完全剩余系。模的最小非負(fù)完全剩余系是：0，1，2，,;即除數(shù)為時，余數(shù)可能取到的數(shù)的全部值。當(dāng)為奇數(shù)時，絕對值最小的完全剩余系是：；當(dāng)為偶數(shù)時，絕對值最小的完全剩余系有兩個：；。以上只是我們個人對同余及剩余類的理解，為了方便大家研究，我

37、們把有關(guān)材料上的具體概念給出，希望大家好好地研究：定義3.（同余類）設(shè)，每一個這樣的類為模的同余類。說明：整數(shù)集合可以按模來分類，確切地說，若和模同余，則和屬同一類，否則不屬于同一類，每一個這樣的類為模的一個同余類。由帶余除法，任一整數(shù)必恰與0,1,，中的一個模同余，而0,1,，這個數(shù)彼此模不同余，因此模共有個不同的同余類，即。例如，模2的同余類共有兩個，即通常說的偶數(shù)類與奇數(shù)類，這兩類中的數(shù)分別具有形式和（為任意整數(shù)）。定義4。（剩余類）設(shè)是正整數(shù)，把全體整按對模的余數(shù)分成類，相應(yīng)的個集合記為：，其中，稱為模的一個剩余類。以下是幾條常用性質(zhì)：（1）且；（2）每一個整數(shù)僅在的一個里；（3）對于

38、任意，則的充要條件是。定義5.（完全剩余系）一組數(shù)稱為模的完全剩余系，如果對任意有且僅有一個是對模的剩余，即。換一種說法更好理解：設(shè)為模的全部剩余類，從每個中任取一個，得個數(shù)組成的數(shù)組，叫做模的一個完全剩余系。說明：在個剩余類中各任取一個數(shù)作為代表，這樣的個數(shù)稱為模的一個完全剩余系，簡稱模的完系。換句話說，個數(shù)稱為模的一個完系，是指它們彼此模不同余，例如0,1，2，是模的一個完系，這稱作是模的最小非負(fù)完系。性質(zhì)：（1）個整數(shù)構(gòu)成模的一個完全剩余系兩兩對模不同余；（2）若，則與同時跑遍模的完全剩余系。典例分析例1試解方程：。解：因為左邊是整數(shù)，因而右邊的分式也應(yīng)該是整數(shù)，所以于是，從而，故。但是

39、是整數(shù)，故，代入前面的不等式，得，直接觀察即知，于是。例2數(shù)100！的十進位制表示中，未尾連續(xù)地有多少位全是零？解：命題等價于100！最多可以被10的多少次方整除。因為因而100！中2的指數(shù)大于5的指數(shù)，所以100！中5的指數(shù)就是所需求出的零的位數(shù)。由即可知100！的未尾連續(xù)地有24位全是數(shù)碼零。例3試求被50除所得的余數(shù)。解：由于是關(guān)于的整系數(shù)多項式，而，于是知。又注意到，故又，所以注意到，因而29就是所求的余數(shù)。說明：在上述過程中，我們已經(jīng)看到的作用。一般而言，知道一個整數(shù)的多少次冪關(guān)于模同余于是非常有用的。事實上，若，則對大的指數(shù)利用帶余除法定理，可得，于是有，這里余數(shù)是一個比小得多的數(shù)

40、，這樣一來，計算的問題，就轉(zhuǎn)化成了計算余數(shù)次冪的問題，從而使計算簡單化。例4設(shè)，計算某星期一后的第天是6星期幾？解；星期幾的問題是被7除求余數(shù)的問題。由于，于是，因而。為了把指數(shù)的指數(shù)寫成的形式，還需取6為模來計算。為此我們有，進而有，依次類推，有，所以從而，這樣，星期一后的第天將是星期五。例5求所有的素數(shù)，使與也是素數(shù)。分析：要使與也是素數(shù)，應(yīng)該是對除以某個數(shù)素的余數(shù)進行分類討論，最后確定只能是這個素數(shù)。由于只有兩個數(shù)，所以不能太大，那樣討論起來也不會有什么效果，試驗發(fā)現(xiàn)對本題不起任何效果，現(xiàn)對展開討論。解：設(shè)，且若或4時，；若或3時，；即時，為5的倍數(shù)且比5大，不為質(zhì)數(shù)。故，此時，；都是素

41、數(shù)。即可題有唯一解。注：要使幾個數(shù)同為質(zhì)數(shù)，一般是對這幾個數(shù)也合乎以某一質(zhì)數(shù)的余數(shù)來確定，如均為質(zhì)數(shù)，可得只能為3，由于這是的一次式，故三個數(shù)就模3，而二次式對三個數(shù)就模5，四個數(shù)一般就模7了。例6求滿足的全部正整數(shù)。分析：如果，兩邊，得，這是不可能的；如果，而中有一個大于1，則另一個也大于1，得，故為奇數(shù)，得，而，為奇數(shù)，從而，矛盾！所以為唯一解。注：在解不定方程時，往往要分情況討論，也常常利用同余來導(dǎo)出一些性質(zhì)求出矛盾！例7數(shù)列滿足：證明：（1）對任意為正整數(shù)；(2)對任意為完全平方數(shù)。（2005年全國高中數(shù)學(xué)聯(lián)賽試題）證明：（1）由題設(shè)得且嚴(yán)格單調(diào)遞增.將條件式變形得兩邊平方整理得-得由

42、式及可知，對任意為正整數(shù).（2）將兩邊配方，得由式0（mod3）為正整數(shù)，式成立.是完全平方數(shù).例8若可以寫成有限小數(shù)，那么自然數(shù)的值是多少？解：由于若與互素，則分?jǐn)?shù)是既約分?jǐn)?shù)；若與不互素，設(shè)它們的公約數(shù)為，且，設(shè)，則，故與的公約數(shù)是5，此時分?jǐn)?shù)的分子、分母只有公約數(shù)5。由于可以寫成有限小數(shù)，故約分之后的分母除了2,5以外，沒還有其它的公約數(shù)，因此。因為是奇數(shù)，故，即。由于故，從而，即，故只有才是有限小數(shù)。練習(xí)1 試求方程的實數(shù)解。（答案：）2 若，試出至少5個的值。（答案：17，32，34，40，48）3 試求被25除所得的余數(shù)。（答案：24）4 設(shè)整數(shù)使，這些中最小的正整數(shù)為，試證：。特別

43、地，若，則。證明：設(shè)，則易知，但是最小的正整數(shù)，故只能為0，即。5 設(shè)是任意整數(shù)，試證下面形狀的數(shù)都不是完全平方數(shù)：（1）；（2）。解：（1）不同余； （2）或3，但或1。6 求所有滿足的正整數(shù)三元組。第五節(jié)初等數(shù)論中的幾個重要定理基礎(chǔ)知識定義（歐拉(Euler)函數(shù)）一組數(shù)稱為是模的既約剩余系，如果對任意的，且對于任意的，若1，則有且僅有一個是對模的剩余，即。并定義中和互質(zhì)的數(shù)的個數(shù)，稱為歐拉（Euler）函數(shù)。這是數(shù)論中的非常重要的一個函數(shù)，顯然，而對于，就是1,2，中與互素的數(shù)的個數(shù)，比如說是素數(shù)，則有。引理：；可用容斥定理來證（證明略）。定理1：（歐拉（Euler）定理）設(shè)1，則。證明

44、：取模的一個既約剩余系，考慮，由于與互質(zhì)，故仍與互質(zhì)，且有，于是對每個都能找到唯一的一個，使得，這種對應(yīng)關(guān)系是一一的，從而，。，故。證畢。分析與解答：要證，我們得設(shè)法找出個相乘，由個數(shù)我們想到中與互質(zhì)的的個數(shù)：，由于1，從而也是與互質(zhì)的個數(shù)，且兩兩余數(shù)不一樣，故（），而（）1，故。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩余系來解決問題。定理2：（費爾馬（Fermat）小定理）對于質(zhì)數(shù)及任意整數(shù)有。設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則。若不是的倍數(shù)，則由引理及歐拉定理得，由此即得。定理推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則。定理3：（威爾遜（Wilson）定理）設(shè)為質(zhì)數(shù)，

45、則。分析與解答：受歐拉定理的影響，我們也找個數(shù)，然后來對應(yīng)乘法。證明：對于，在中，必然有一個數(shù)除以余1，這是因為則好是的一個剩余系去0。從而對，使得；若，則，故對于，有。即對于不同的對應(yīng)于不同的，即中數(shù)可兩兩配對，其積除以余1，然后有，使，即與它自己配對，這時，或，或。除外，別的數(shù)可兩兩配對，積除以余1。故。定義：設(shè)為整系數(shù)多項式（），我們把含有的一組同余式（）稱為同余方組程。特別地，當(dāng)均為的一次整系數(shù)多項式時，該同余方程組稱為一次同余方程組.若整數(shù)同時滿足：，則剩余類（其中）稱為同余方程組的一個解，寫作定理4：（中國剩余定理）設(shè)是兩兩互素的正整數(shù)，那么對于任意整數(shù)，一次同余方程組，必有解，且

46、解可以寫為：這里，以及滿足，（即為對模的逆）。中國定理的作用在于它能斷言所說的同余式組當(dāng)模兩兩互素時一定有解，而對于解的形式并不重要。定理5：（拉格郎日定理）設(shè)是質(zhì)數(shù)，是非負(fù)整數(shù)，多項式是一個模為次的整系數(shù)多項式（即 ），則同余方程至多有個解（在模有意義的情況下）。定理6：若為對模的階，為某一正整數(shù)，滿足，則必為的倍數(shù)。以上介紹的只是一些系統(tǒng)的知識、方法，經(jīng)常在解決數(shù)論問題中起著突破難點的作用。另外還有一些小的技巧則是在解決、思考問題中起著排除情況、輔助分析等作用，有時也會起到意想不到的作用，如：，。這里我們只介紹幾個較為直接的應(yīng)用這些定理的例子。典例分析例1.設(shè)，求證：。證明：因為，故由知，

47、從而，但是，故由歐拉定理得：，從而；同理，。于是，即。注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：若有正整數(shù)使，則有，其中；因而關(guān)于，數(shù)列的項依次同余于這個數(shù)列相繼的項成一段，各段是完全相同的，因而是周期數(shù)列。如下例：例2試求不大于100，且使成立的自然數(shù)的和。解：通過逐次計算，可求出關(guān)于的最小非負(fù)剩余（即為被11除所得的余數(shù)）為：因而通項為的數(shù)列的項的最小非負(fù)剩余構(gòu)成周期為5的周期數(shù)列：3，9，5，4，1，3，9，5，4，1，類似地，經(jīng)過計算可得的數(shù)列的項的最小非負(fù)剩余構(gòu)成周期為10的周期數(shù)列：7，5，2，3，10，4，6，9，8，1，于是由上兩式可知通項為的數(shù)列的項的最小非負(fù)剩余，構(gòu)成周期為10（即上

48、兩式周期的最小公倍數(shù)）的周期數(shù)列：3，7，0，0，4，0，8，7，5，6，這就表明，當(dāng)時，當(dāng)且僅當(dāng)時，即；又由于數(shù)列的周期性，故當(dāng)時，滿足要求的只有三個，即從而當(dāng)時，滿足要求的的和為：.下面我們著重對Fetmat小定理及其應(yīng)用來舉例：例3求證：對于任意整數(shù)，是一個整數(shù)。證明：令，則只需證是15的倍數(shù)即可。由3，5是素數(shù)及Fetmat小定理得，則；而（3，5）=1，故，即是15的倍數(shù)。所以是整數(shù)。例4求證：（為任意整數(shù)）。證明：令，則；所以含有因式由Fetmat小定理，知13|7|又13，7，5，3，2兩兩互素，所以2730=能整除。例5設(shè)是直角三角形的三邊長。如果是整數(shù)，求證：可以被30整除。

49、證明：不妨設(shè)是直角三角形的斜邊長，則。若2 ，2 ，2 c，則，又因為矛盾！所以2|.若3 ，3 ，3 c，因為，則，又，矛盾！從而3|.若 5 ，5 ，5 c，因為，所以或0(mod5)與矛盾！從而5|.又(2,3,5)=1，所以30|.下面講述中國剩余定理的應(yīng)用例6證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都有大于1的平方因子。證明：由于素數(shù)有無窮多個，故我們可以取個互不相同的素數(shù)，而考慮同余組 因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個數(shù)分別被平方數(shù)整除。注：（1）本題的解法體現(xiàn)了中國剩余定理的一個基本功效，它常常能將“找連續(xù)個正整數(shù)具有某

50、種性質(zhì)”的問題轉(zhuǎn)化為“找個兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。 （2）本題若不直接使用素數(shù)，也中以采用下面的變異方法：由費爾馬數(shù)兩兩互素，故將中的轉(zhuǎn)化為后，相應(yīng)的同余式也有解，同樣可以導(dǎo)出證明。例7證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都不是冪數(shù)。分析：我們來證明，存在連續(xù)個正整數(shù)，其中每一個數(shù)都至少有一個素因子，在這個數(shù)的標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個數(shù)不是冪數(shù)。證明：取個互不相同的素數(shù)，考慮同余組因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。對于因為，故，但由式可知 ，即在的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，故都不是冪數(shù)。例8 設(shè)是給定的偶數(shù)，

51、且是偶數(shù)。證明：存在整數(shù)使得，且。證明：我們先證明，當(dāng)為素數(shù)冪時結(jié)論成立。實際上，能夠證明，存在使 且：若，則條件表明為偶數(shù)，此時可??；若，則與中有一對滿足要求。一般情形下，設(shè)是的一個標(biāo)準(zhǔn)分解，上面已經(jīng)證明，對每個存在整數(shù)使得且，而由中國剩余定理，同余式 有解，同余式 有解?，F(xiàn)不難驗證解符合問題中的要求：因，故 ，于是，又由知，故。注：此題的論證表現(xiàn)了中國剩余定理最為基本的作用：將一個關(guān)于任意正整數(shù)的問題，化為為素數(shù)冪的問題，而后者往往是比較好處理的。練習(xí)：1設(shè)是給定的素數(shù)，證明：數(shù)列中有無窮多項被整除。2求證：=為整值多項式。3數(shù)列：1，31，331，3331，中有無窮多個合數(shù)。4設(shè)為任意給

52、定的正整數(shù)，證明：存在連續(xù)個正整數(shù)，其中每一個都不是素數(shù)的冪。5設(shè)為正整數(shù)，具有性質(zhì)：等式對所有的正整數(shù)成立。證明：，其中是某個整數(shù)。第六節(jié)不定方程所謂不定方程，是指未知數(shù)的個數(shù)多于方程個數(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ù)論

53、的一般理論、方法有一定的了解，而且更需要講究思想、方法與技巧，創(chuàng)造性的解決問題。在本節(jié)我們來看一看不定方程的基礎(chǔ)性的題目?；A(chǔ)知識1不定方程問題的常見類型：（1）求不定方程的解；（2）判定不定方程是否有解；（3）判定不定方程的解的個數(shù)（有限個還是無限個）。2解不定方程問題常用的解法：（1）代數(shù)恒等變形：如因式分解、配方、換元等；（2）不等式估算法：利用不等式等方法，確定出方程中某些變量的范圍，進而求解；（3）同余法：對等式兩邊取特殊的模（如奇偶分析），縮小變量的范圍或性質(zhì)，得出不定方程的整數(shù)解或判定其無解；（4）構(gòu)造法：構(gòu)造出符合要求的特解，或構(gòu)造一個求解的遞推式，證明方程有無窮多解；（5）無窮遞推法。以下給出幾個關(guān)于特殊方程的求解定理：（一）二元一次不定方程（組）定義1.形如(不同時為零)的方程稱為二元一次不定方程。定理1.方程有解的充要是；定理2.若，且為的一個解，則方程的一切解都可以表示成為任意整數(shù))。定理3.元一次不定方程，()有解的充要條件是.方法與技巧：1解二元一次不定方程通常先判定方程有無解。