張本慧，崇金鳳，卓澤朋

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

1 引言

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

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

2 初等數(shù)論在數(shù)學競賽中的應用

2.1 整除理論在數(shù)學競賽中的應用

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

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

解不妨假設 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，其十進制表示法中以6結尾，如果把最后的6去掉并放在最前面所得到的數(shù)是n的4倍.

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

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

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

求[10a]的值.

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

2.2 同余理論在數(shù)學競賽中的應用

首先看這樣一個問題（Q）：假設今天是星期一，那么從今天起再過101010天是星期幾？

這個問題看似很復雜，但是如果從同余的角度來解決這個問題就非常簡單.同余是數(shù)論中的一個基本概念，它是研究整數(shù)問題的重要工具，在各類數(shù)學競賽中也有廣泛的應用.

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

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

天是星期五.

例4[8]（2012年數(shù)學周報杯全國初中數(shù)學聯(lián)賽試題） 假設n是整數(shù)且1≤n≤2012，求滿足(n2-n+3)(n2+n+3)能被5整除的所有n的個數(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個.

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

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

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

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

2.3 數(shù)學競賽中的不定方程

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

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

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

解設三條邊長分別為a,b,c，不妨設a≤b＜c，由于周長為 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ù)論在密碼學中的應用

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

3.1 移位密碼

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

表1 移位密碼

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

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

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

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

寫出每個整數(shù)對應的字母，得到密文為：hphtwwxppelextoytrse

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

3.2 RSA密碼協(xié)議

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

歐拉定理[1]設(a,n)=1，那么 a?(n)≡1(modn)，其中?(n)表示1,2,…,n中與n互素的整數(shù)個數(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)在，假設Alice想加密明文9726，她計算97263533mod11413=5761，然后將密文5761發(fā)送給Bob.當Bob收到密文5761，他通過計算57616597mod 11413=9726即可恢復明文9726.

4 結束語

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