【正文】 數(shù)學競賽中的數(shù)論問題 羅增儒引言數(shù)論的認識：數(shù)論是關于數(shù)的學問，主要研究整數(shù)，重點對象是正整數(shù)，對中學生可以說，數(shù)論是研究正整數(shù)的一個數(shù)學分支．什么是正整數(shù)呢？人們借助于“集合”和“后繼”關系給正整數(shù)（當時也即自然數(shù)）作過本質(zhì)的描述，正整數(shù)1，2，3，…是這樣一個集合：（1）有一個最小的數(shù)1． （2）每一個數(shù)的后面都有且只有一個后繼數(shù)；除1之外，每一個數(shù)的都是且只是一個數(shù)的后繼數(shù)．這個結(jié)構(gòu)很像數(shù)學歸納法，事實上，有這樣的歸納公理：（3）對的子集，若，且當時，有后繼數(shù)，則．就是這么一個簡單的數(shù)集，里面卻有無窮無盡的奧秘，有的奧秘甚至使得人們懷疑：人類的智慧還沒有成熟到解決它的程度．比如，哥德巴赫猜想：1742年6月7日，普魯士派往俄國的一位公使哥德巴赫寫信給歐拉，提出“任何偶數(shù)，由4開始，都可以表示為兩個素數(shù)和的形式，任何奇數(shù)，由7開始，都可以表示為三個素數(shù)的和．后者是前者的推論，也可獨立證明（已解決）．“表示為兩個素數(shù)和的形式”就是著名的哥德巴赫猜想，簡稱1+1．歐拉認為這是對的，但證不出來．1900年希爾伯特將其歸入23個問題中的第8個問題．1966年陳景潤證得：一個素數(shù)+素數(shù)素數(shù)（1+2），至今仍無人超越．●陳景潤的數(shù)學教師沈元很重視利用名人、名言、名事去激勵學生，他曾多次在開講時，說過這樣的話:“自然科學的皇后是數(shù)學，數(shù)學的皇冠是數(shù)論，哥德巴赫猜想則是皇冠上的明珠．……”陳景潤就是由此而受到了啟示和激勵，展開了艱苦卓絕的終生奮斗和燦爛輝煌的奮斗終生，離摘取“皇冠上的明珠”僅一步之遙．●數(shù)論題涉及的知識不是很多，但用不多的知識來解決問題往往就需要較強的能力和精明多的技巧，有人說：用以發(fā)現(xiàn)數(shù)學人才，在初等數(shù)學中再也沒有比數(shù)論教材更好的課程了．任何學生如能把當今一本數(shù)論教材中的練習做出，就應當受到鼓勵，勸他（她）將來去從事數(shù)學方面的工作（U．Dudley《數(shù)論基礎》前言）．下面，是一個有趣的故事．當代最高產(chǎn)的數(shù)學家厄爾多斯聽說一個叫波薩（匈牙利，1948）的小男孩很聰明，就問了他一個問題加以考察（1959）：如果你手頭上有個正整數(shù)，這些正整數(shù)小于或等于，那么你一定有一對整數(shù)是互素的，你知道這是什么原因嗎？不到12歲的波薩只用了1分半鐘，就給出了問題的解答．他將1～分成（1，2），（3，4），…，（）共個抽屜，手頭的個正整數(shù)一定有兩個屬于同一抽屜，這兩個數(shù)是相鄰的正整數(shù)，必定互素．通過這個問題，厄爾多斯認定波薩是個難得的英才，就精心加以培養(yǎng)，不到兩年，14歲的波薩就發(fā)表了圖論中“波薩定理”．●重視數(shù)學能力的數(shù)學競賽，已經(jīng)廣泛采用數(shù)論題目，是數(shù)學競賽四大支柱之一，四大支柱是：代數(shù)，幾何，初等數(shù)論，組合初步（俗稱代數(shù)題、幾何題、算術題和智力題）．高中競賽加試四道題正好是四大模塊各一題，分別是幾何題、代數(shù)題、數(shù)論題、組合題，一試中也會有數(shù)論題．數(shù)論受到數(shù)學競賽的青睞可能還有一個技術上的原因，就是它能方便地提供從小學到大學各個層面的、新鮮而有趣的題目．數(shù)論題的主要類型：在初中競賽大綱中，數(shù)論的內(nèi)容列有：十進制整數(shù)及表示方法；整除性，被11等數(shù)整除的判定；素數(shù)和合數(shù)，最大公約數(shù)與最小公倍數(shù)；奇數(shù)和偶數(shù)，奇偶性分析；帶余除法和利用余數(shù)分類；完全平方數(shù)；因數(shù)分解的表示法，約數(shù)個數(shù)的計算； 簡單的一次不定方程． 在高中競賽大綱中，數(shù)論的內(nèi)容列有：同余，歐幾里得除法，裴蜀定理，完全剩余類，二次剩余，不定方程和方程組，高斯函數(shù)[]，費馬小定理，格點及其性質(zhì)，無窮遞降法，歐拉定理，孫子定理．根據(jù)已出現(xiàn)的試題統(tǒng)計，中學數(shù)學競賽中的數(shù)論問題的主要有8個重點類型：（1）奇數(shù)與偶數(shù)（奇偶分析法、01法）；（2）約數(shù)與倍數(shù)、素數(shù)與合數(shù)；（3）平方數(shù)；（4）整除；（5）同余；（6）不定方程；（7）數(shù)論函數(shù)、高斯函數(shù)、歐拉函數(shù)；（8）進位制（十進制、二進制）．下面，我們首先介紹數(shù)論題的基本內(nèi)容（10個定義、18條定理），然后，對數(shù)學競賽中的數(shù)論問題作分類講解．第一講 數(shù)論題的基本內(nèi)容中學數(shù)學競賽中的數(shù)論問題涉及的數(shù)論內(nèi)容主要有10個定義、18條定理．首先約定，本文中的字母均表示整數(shù)．定義1 （帶余除法）給定整數(shù)如果有整數(shù)滿足 ，則和分別稱為除以的商和余數(shù)．特別的，時，則稱被整除，記作，或者說是的倍數(shù)，而是的約數(shù)．（的存在性由定理1證明）定義2 （最大公約數(shù)）設整數(shù)中至少有一個不等于零，這個數(shù)的最大公約數(shù)是能整除其中每一個整數(shù)的最大正整數(shù)，記作． 中的沒有順序，最大公約數(shù)也稱最大公因數(shù)．簡單性質(zhì)：．一個功能：可以把對整數(shù)的研究轉(zhuǎn)化為對非負整數(shù)的研究．定義3 （最小公倍數(shù)）非零整數(shù)的最小公倍數(shù)是能被其中每一個所整除的最小正整數(shù)，記作．簡單性質(zhì)：如果是正整數(shù)的公倍數(shù)，則存在正整數(shù)使證明　若不然，有（），由都是的公倍數(shù)得也是的公倍數(shù)，但，與的最小性矛盾．故．定義4 如果整數(shù) 滿足，則稱與是互素的（也稱互質(zhì)）．定義5 大于1且除1及其自身外沒有別的正整數(shù)因子的正整數(shù)，稱為素數(shù)（也稱質(zhì)數(shù)）．其余大于1的正整數(shù)稱為合數(shù)；數(shù)1既不是素數(shù)也不是合數(shù)．定理1 若是兩個整數(shù)，則存在兩個實數(shù)，使，并且是唯一性．證明1 先證存在性．作序列則必在上述序列的某兩項之間，從而存在一個整數(shù)，使 ，即 ，取 ， ，得 ，即存在兩個實數(shù)，使． 再證唯一性．假設不唯一，則同時存在與，使 ， ，相減 ， ， ，但為整數(shù)，故，得，從而．注：如果取消，當或，不保證唯一．經(jīng)典方法：緊扣定義，構(gòu)造法證存在性，反證法證唯一性．證明2 只證存在性，用高斯記號，由 ，有 ，記，故存在使．證明3 只證存在性，作集合 這是一個有下界的非空整數(shù)集，其中必有最小的，設時，有最小值 ．再證，若不然，記，有 即有比更小，這與為最小值矛盾．故存在兩個實數(shù)，使．定理2 設是三個不全為0的整數(shù)，滿足，其中也為整數(shù)，則．證明 設｛的公約數(shù)｝， ｛的公約數(shù)｝．任取，任取，得 ．有中元素的最大值中元素的最大值，即．注：這是輾轉(zhuǎn)相除法求最大公約數(shù)的理論基礎．經(jīng)典方法：要證明，只需證且．定理3 對任意的正整數(shù)，有 ．證明 因為是的公倍數(shù)，所以的最小公倍數(shù)也是的約數(shù)，存在使 ，有 　　且為整數(shù)，故是的約數(shù)．同理是的約數(shù)，即是的公約數(shù)．下面證明，是的最大公約數(shù)．若不然，．有． ①設，可見是的倍數(shù)，同樣，是的倍數(shù)，即是的公倍數(shù)，則存在正整數(shù)使，有，得 與①矛盾，所以，得證．注 也可以由，得，與矛盾．兩步可以交換嗎？定理4 是兩個不同時為0的整數(shù)，若是形如（是任意整數(shù)）的數(shù)中的最小正數(shù)，則（1）|；（2）．證明 （1）由帶余除法有 ，得 ，知也是形如的非負數(shù)，但是形如的數(shù)中的最小正數(shù)，故，即|． （2）由（1）有|，|，得是的公約數(shù)．另一方面，的每一個公約數(shù)都可以整除，所以是的最大公約數(shù)，．推論　若，則存在整數(shù)，使．（很有用）定理5 互素的簡單性質(zhì)： （1）．（2）．（3）．（4）若是一個素數(shù)，是任意一個整數(shù)，且不能被整除，則．證明 因為，所以，素數(shù)的約數(shù)只有兩種可能：．但不能被整除，得．推論 若是一個素數(shù)，是任意一個整數(shù)，則或．（5）若，則存在整數(shù)，使．（定理4推論）（6）若，則．證明 由知存在整數(shù)，使．有 ，得 ．（7）若，則， ．證明 ， ，由（6）．（8）若，則，其中為正整數(shù)．證明 據(jù)（6），由可得． 同樣，由可得．定理6 設是大于1的整數(shù)，則的除1之外的最小的正約數(shù)必是素數(shù)，且當是合數(shù)時，．證明 用反證法，假設不是素數(shù)，則存在正整數(shù)數(shù)，使，但，故有，這與是的除1之外的最小正約數(shù)矛盾，故是素數(shù)．當是合數(shù)時，設，則也是的一個正約數(shù)，由的最小性得，從而，開方得．定理7 素數(shù)有無窮多個，2是唯一的偶素數(shù)．證明 假設素數(shù)只有有限多個，記為，作一個新數(shù) ．若為素數(shù)，則與素數(shù)只有 個矛盾．若為合數(shù)，則必有，使，從而，又與矛盾．綜上所述，素數(shù)不能只有有限多個，所以素數(shù)有無窮多個．2是素數(shù)，而大于2的偶數(shù)都是合數(shù)，所以2是唯一的偶素數(shù)．注：這個證明中，包含著數(shù)學歸納法的早期因素：若假設有個素數(shù)，便有個素數(shù)．（構(gòu)造法、反證法）秒定理8（整除的性質(zhì)）整數(shù)通常指非零整數(shù)（1），；當時，． （2）若，則。若，則。若，且，則．證明