張本慧，崇金鳳，卓澤朋

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

1 引言

《初等數(shù)論》[1-3]課程主要研究整數(shù)的運(yùn)算規(guī)律.熟練掌握初等數(shù)論的基本內(nèi)容(如整除理論、同余知識(shí)、不定方程、素?cái)?shù)分布、數(shù)論函數(shù)等)、基本思想與基本方法，可以促進(jìn)學(xué)生對(duì)整數(shù)性質(zhì)的深入理解，強(qiáng)化分析問(wèn)題、解決問(wèn)題的能力，擴(kuò)充知識(shí)的廣度，培養(yǎng)發(fā)散思維，為學(xué)生學(xué)習(xí)《離散數(shù)學(xué)》和《近世代數(shù)》等課程奠定必要的基礎(chǔ).本課程是數(shù)學(xué)中最古老的分支之一，也是師范院校數(shù)學(xué)類各專業(yè)的一門專業(yè)選修課，它對(duì)于提高師范專業(yè)學(xué)生的教師素質(zhì)具有十分重要的意義.

《初等數(shù)論》課程與中小學(xué)的數(shù)學(xué)競(jìng)賽緊密相連，如數(shù)學(xué)家羅曼在1959年發(fā)起的國(guó)際數(shù)學(xué)奧林匹克競(jìng)賽，經(jīng)過(guò)五十多年的發(fā)展，它已經(jīng)成為規(guī)模最大、類型多樣、層次較高的一項(xiàng)學(xué)科競(jìng)賽.根據(jù)對(duì)奧林匹克數(shù)學(xué)競(jìng)賽題的統(tǒng)計(jì)，能直接利用數(shù)論知識(shí)解決的題目大約有30%，這還不包括那些解題過(guò)程與數(shù)論相關(guān)的題目.與數(shù)論相關(guān)的世界數(shù)學(xué)難題也有很多，如費(fèi)馬猜想[4]、哥德巴赫猜想[5]等.哥德巴赫猜想至今仍未完全解決，一批又一批的數(shù)學(xué)家們還在不斷努力，這足以看出數(shù)論在數(shù)學(xué)領(lǐng)域的重要地位.《初等數(shù)論》課程并不是孤立的，它與其它學(xué)科也密切相關(guān)，如計(jì)算機(jī)科學(xué)、密碼學(xué)等.本文結(jié)合筆者多年的教學(xué)經(jīng)驗(yàn)和研究方向（密碼學(xué)），談?wù)剶?shù)論在數(shù)學(xué)競(jìng)賽及密碼學(xué)中的相關(guān)應(yīng)用.

2 初等數(shù)論在數(shù)學(xué)競(jìng)賽中的應(yīng)用

2.1 整除理論在數(shù)學(xué)競(jìng)賽中的應(yīng)用

整除理論是初等數(shù)論的基礎(chǔ)，它對(duì)中小學(xué)學(xué)過(guò)的整數(shù)運(yùn)算規(guī)律進(jìn)行了抽象系統(tǒng)的歸納總結(jié)，主要包括最大公約數(shù)理論和算術(shù)基本定理.在各類數(shù)學(xué)競(jìng)賽中，與整除理論有關(guān)的題目占有相當(dāng)大的比例，下面通過(guò)具體的例子來(lái)說(shuō)明如何借助整除理論解決數(shù)學(xué)競(jìng)賽題.

例1[6]（第3屆“希望杯”初一二試題）設(shè)a,b,c是三個(gè)兩兩互素的自然數(shù)，其中任意兩個(gè)之和都能被第三個(gè)整除，求a3+b3+c3的值.

解不妨假設(shè) a＞b＞c，則，又 b|(a+c)，則 b|(b+c+c)?b|(b+2c)?b|2c，而 b,c 互素，故 b|2，又 b＞c，從而 b=2,c=1,a=3，所以 a3+b3+c3=36.

例2[7]（第4屆奧數(shù)題）求滿足下列性質(zhì)的最小自然數(shù)n，其十進(jìn)制表示法中以6結(jié)尾，如果把最后的6去掉并放在最前面所得到的數(shù)是n的4倍.

解n以6結(jié)尾，根據(jù)帶余數(shù)除法有n=10m+6，其中m是正整數(shù)，設(shè)m的位數(shù)為l，根據(jù)題意有

又m為正整數(shù)，則13|2(10l-4)?13|10l-4.要求最小的n，問(wèn)題轉(zhuǎn)化為求最小的正整數(shù)l，使得13|10l-4.取l=1,2,…,，逐個(gè)驗(yàn)證求得滿足條件的最小的l=5，從而m=15384，于是所求的最小自然數(shù)n=15384.

例3[8]（2006年全國(guó)初中數(shù)學(xué)聯(lián)賽試題）已知0＜a＜1 且滿足

求[10a]的值.

解由于等于 0 或 1，由題意知，這其中有18個(gè)等于1，從而

2.2 同余理論在數(shù)學(xué)競(jìng)賽中的應(yīng)用

首先看這樣一個(gè)問(wèn)題（Q）：假設(shè)今天是星期一，那么從今天起再過(guò)101010天是星期幾？

這個(gè)問(wèn)題看似很復(fù)雜，但是如果從同余的角度來(lái)解決這個(gè)問(wèn)題就非常簡(jiǎn)單.同余是數(shù)論中的一個(gè)基本概念，它是研究整數(shù)問(wèn)題的重要工具，在各類數(shù)學(xué)競(jìng)賽中也有廣泛的應(yīng)用.

定義1[1]設(shè)m是正整數(shù)，如果m|(a-b)，則稱a同余于 b 模 m，記作 a≡b(modm)，如果 m■(a-b)，則稱a不同余于b模b，記作a?b(modm).

可以這樣回答問(wèn)題（Q）：106≡1(mod7)，1010≡(-2)10≡322≡22≡4(mod6)，假設(shè) 1010=4+6k，其中 k為正整數(shù)，則101010=104+6k≡104≡4(mod7)，所以再過(guò)101010

天是星期五.

例4[8]（2012年數(shù)學(xué)周報(bào)杯全國(guó)初中數(shù)學(xué)聯(lián)賽試題） 假設(shè)n是整數(shù)且1≤n≤2012，求滿足(n2-n+3)(n2+n+3)能被5整除的所有n的個(gè)數(shù).

解首先，(n2-n+3)(n2+n+3)=(n2+3)2-n2=n4+5n2+9，又 5|(n2-n+3)(n2+n+3)，故 5|(n4+9)，從而 n4≡1(mod5)，于是5不能整除n，又2012÷5=402余2，2012-402=1610，即滿足條件的n共有1610個(gè).

例5[7]（第六屆奧數(shù)題）1）求能使2n-1被7整除的所有正整數(shù)n；2）證明：對(duì)任意正整數(shù)n來(lái)說(shuō)，2n+1都不能被7整除.

解對(duì)任意正整數(shù)n，根據(jù)帶余數(shù)除法，存在整數(shù)q,r使得n=6q+r，其中0≤r≤5，從而根據(jù)費(fèi)馬小定理有，2n±1=26q+r±1=(26)q·2r±1≡2r±1(mod7)，r取0,1,2,3,4,5.

1）當(dāng) r=0.3 時(shí)，即 n=6q 或 n=6q+3，此時(shí) 2n-1≡2r-1≡0(mod7)，也就是說(shuō)，當(dāng)且僅當(dāng)3|n時(shí)有7|(2n-1).

2）不論r取0,1,2,3,4,5中的哪一個(gè)，都有2n+1≡2r+1?0(mod7)，也就是說(shuō)，對(duì)任意正整數(shù) n，2n+1都不能被7整除.

2.3 數(shù)學(xué)競(jìng)賽中的不定方程

未知數(shù)的個(gè)數(shù)多于方程個(gè)數(shù)，且未知數(shù)取整數(shù)的方程稱為不定方程.在各類數(shù)學(xué)競(jìng)賽中不定方程的問(wèn)題經(jīng)常出現(xiàn).

定義2[1]稱a1x1+…+akxk=c為k元一次不定方程，這里整數(shù) k≥2，c,a1,…,ak是整數(shù)且 a1,…,ak非零.

例6[8]（2012年全國(guó)初中數(shù)學(xué)聯(lián)賽試題）求各邊長(zhǎng)為整數(shù)且周長(zhǎng)為60的直角三角形的外接圓面積.

解設(shè)三條邊長(zhǎng)分別為a,b,c，不妨設(shè)a≤b＜c，由于周長(zhǎng)為 60且 a+b＞c，則

又 a2+b2=c2，將 c=60-a-b 代入，得

由于 a≤b＜c＜30，

故 30＜60-a＜60，30＜60-b＜60，60-b≤60-a，從而

3 初等數(shù)論在密碼學(xué)中的應(yīng)用

密碼學(xué)的基本目的是使得兩個(gè)在不安全信道中通信的人，以一種使他們的敵人不能明白和理解通信內(nèi)容的方式進(jìn)行通信.很多密碼協(xié)議的設(shè)計(jì)都是以數(shù)論知識(shí)為基礎(chǔ)，如移位密碼、RSA密碼協(xié)議等.

3.1 移位密碼

移位密碼[9]是古典密碼中的一種，其理論基礎(chǔ)是數(shù)論中的模運(yùn)算.

表1 移位密碼

建立26個(gè)英文字母和模26剩余之間的一一對(duì)應(yīng)關(guān)系，如a?0,b?1,…,z?25，然后利用移位密碼就可以加密英文句子，下面介紹例7.

例7設(shè)移位密碼的密鑰為K=11，明文為wewillmeetatmidnight

寫出明文中的字母對(duì)應(yīng)的整數(shù)，得：22/4/22/8/11/11/12/4/4/19/0/19/12/8/3/13/8/6/7/19

將每個(gè)整數(shù)與11相加并作模26運(yùn)算，得：7/15/7/19/22/22/23/15/15/4/11/4/23/19/14/24/19/17/18/4

寫出每個(gè)整數(shù)對(duì)應(yīng)的字母，得到密文為：hphtwwxppelextoytrse

要對(duì)密文解密，只需執(zhí)行逆過(guò)程.

3.2 RSA密碼協(xié)議

1977 年，Rivest、Shamir和 Adleman 設(shè)計(jì)了著名的RSA密碼協(xié)議[9]，其理論基礎(chǔ)是歐拉定理.

歐拉定理[1]設(shè)(a,n)=1，那么 a?(n)≡1(modn)，其中?(n)表示1,2,…,n中與n互素的整數(shù)個(gè)數(shù).

表2 RSA密碼協(xié)議

例8假定Bob選取p=101,q=113，從而n=101×113=11413,?(n)=100×112=11200，假定 Bob選取加密指數(shù)b=3533，那么解密指數(shù)a=b-1mod11200=6597.Bob在目錄中發(fā)布n=11413和b=3533.現(xiàn)在，假設(shè)Alice想加密明文9726，她計(jì)算97263533mod11413=5761，然后將密文5761發(fā)送給Bob.當(dāng)Bob收到密文5761，他通過(guò)計(jì)算57616597mod 11413=9726即可恢復(fù)明文9726.

4 結(jié)束語(yǔ)

《初等數(shù)論》課程的內(nèi)容豐富多彩，它的基礎(chǔ)知識(shí)可能并不難學(xué)，其難點(diǎn)是如何利用這些知識(shí)解決一些實(shí)際問(wèn)題.在實(shí)際的教學(xué)過(guò)程中，大學(xué)老師切勿照本宣科，純粹地把概念和定理傳遞給學(xué)生，而是應(yīng)在適當(dāng)?shù)恼鹿?jié)引入適當(dāng)?shù)母?jìng)賽題，并教會(huì)學(xué)生如何應(yīng)用數(shù)論知識(shí)去解決這些問(wèn)題，一方面提高學(xué)生的解題能力和邏輯思維能力，另一方面促使學(xué)生特別是師范生以較高的觀點(diǎn)去看待中小學(xué)數(shù)學(xué)知識(shí)，為今后更好地從事中小學(xué)的數(shù)學(xué)教學(xué)和競(jìng)賽輔導(dǎo)打下良好的基礎(chǔ).適時(shí)地將《初等數(shù)論》課程與密碼學(xué)聯(lián)系在一起，豐富教學(xué)內(nèi)容，激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生從事科學(xué)研究的良好習(xí)慣，為今后畢業(yè)論文的撰寫和進(jìn)一步深造打下堅(jiān)實(shí)基礎(chǔ).