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