Elementary Number Theory（初等數論）

引用

Burton, D. M. (2011). Elementary Number Theory (7th ed.). McGraw-Hill.

章節概要

全書共16章，之後是雜題、附錄（一般參考文獻、延伸閱讀和數表）、部分習題的答案和索引。若干章節以與該主題相關的數學家（高斯、費馬、歐拉、梅森、拉格朗日、斐波那契、拉馬努金）的小節開頭，構成了本書的歷史線索。

第1章：預備知識

兩個小節，分別講數學歸納法和二項式定理，為後面各章用到的證明技巧和恆等式做準備。

第2章：整數的整除理論

以早期數論的一節開頭，隨後展開帶餘除法、最大公約數和歐幾里得演算法，最後講線性丟番圖方程。這是這門學科的核心對象第一次集中出現的一章。

第3章：質數及其分佈

講算術基本定理、埃拉托斯特尼篩法和哥德巴赫猜想。質數先於同餘出現，因此後面各章可以隨時引用因數分解。

第4章：同餘理論

在介紹卡爾·弗里德里希·高斯的一節之後，給出同餘的基本性質、整數的二進位制與十進位制表示，以及線性同餘和中國餘數定理。隨後關於費馬、歐拉、原根和互反律的各章，都屬於同餘理論的範圍。

第5章：費馬定理

從皮埃爾·德·費馬開始，講費馬小定理與偽質數、威爾遜定理，以及費馬–克萊奇克因數分解法。

第6章：數論函數

討論約數之和與約數個數、莫比烏斯反演公式和取整函數，最後以日曆方面的一個應用結束。

第7章：歐拉對費馬定理的推廣

從萊昂哈德·歐拉一節出發，引出歐拉φ函數、歐拉定理，以及φ函數的一些進一步性質。

第8章：原根與指數

引入整數模 n 的階、質數的原根、有原根的合數模，以及指數理論。

第9章：二次互反律

展開歐拉判別法、勒讓德符號及其性質、二次互反律本身，以及合數模的二次同餘。對許多課程來說，這是古典主線的終點。

第10章：密碼學導論

從凱撒密碼一直講到公鑰密碼，然後講背包密碼系統，以及原根在密碼學中的一個應用。這一章只有三個小節，所以是對該主題的介紹，而不是詳盡的論述。

第11章：特殊形式的數

從馬蘭·梅森開始，講完全數、梅森質數、親和數和費馬數。

第12章：某些非線性丟番圖方程

分為兩節：一節講一個特定的非線性丟番圖方程，另一節講費馬大定理。

第13章：整數表為平方和

在約瑟夫·路易·拉格朗日一節之後，講兩個平方數之和，以及多於兩個平方數之和。

第14章：斐波那契數

介紹斐波那契其人、斐波那契數列，以及關於斐波那契數的若干恆等式。

第15章：連分數

從斯里尼瓦瑟·拉馬努金一節開始，講有限連分數與無限連分數、法裡分數和佩爾方程。

第16章：近期進展

這是一章概覽：哈代、迪克森與厄多斯；質數檢定與因數分解；因數分解的一個應用，即遠端拋硬幣；質數定理與ζ函數。

核心概念

第1–3章：預備知識、整除性、質數

• 數學歸納法：開篇複習、後面論證中使用的證明技巧。
• 歐幾里得演算法：計算最大公約數的方法，也可用來解線性丟番圖方程。
• 算術基本定理：整數可以唯一地分解為質數之積。

第4–5章：同餘與費馬定理

• 同餘：模 n 的算術，並系統地求解線性同餘。
• 中國餘數定理：同時求解模數不同的若干同餘式。
• 費馬小定理與威爾遜定理：關於質數模下的冪和階乘的兩個經典結果。
• 偽質數：能通過費馬型檢驗的合數，把這一定理與質數檢定聯繫起來。

第6–8章：數論函數、歐拉定理、原根

• 莫比烏斯反演公式：由關於約數的求和函數恢復原函數的方法。
• 歐拉φ函數與歐拉定理：計數模 n 的可逆元，並推廣費馬定理。
• 原根與指數：其冪遍歷模 n 全部可逆元的數，以及建立在其上的指數理論。

第9–10章：二次互反律與密碼學

• 勒讓德符號與二次互反律：判斷一個數是否為某個質數模下平方數的工具。
• 公鑰密碼：從古典密碼到現代體制的路線，書中以背包密碼系統為例。

第11–16章：專題

• 完全數、梅森質數與費馬數：特殊形式的數及其聯繫。
• 平方和：哪些整數可以表為兩個或更多個平方數之和。
• 連分數與佩爾方程：逼近實數，並求解一個經典的丟番圖方程。
• 質數定理與ζ函數：數論的解析一面，直到最後一節才出現。

評析

優點

• 歷史背景融入結構。 出版社的介紹把本書定位為對古典數論的簡明敘述，以從古代到近期研究的歷史為背景。目錄印證了這一點：高斯、費馬、歐拉、梅森、拉格朗日、斐波那契和拉馬努金各自成為一節的標題，第2章也以早期數論開頭。
• 清晰的古典主線。 第2章到第9章沿一條線推進：整除性、質數、同餘、費馬與歐拉、原根、二次互反律。讀者可以不繞彎地走完標準課程，後面各章各講一個獨立的話題，可以按興趣選擇。
• 後半部分題材廣泛。 特殊數、平方和、斐波那契數、連分數以及對近期進展的概覽，讓課程在講完核心之後有很多選擇。
• 對做題的支援。 書末有雜題、數表、部分習題的答案，以及一般參考文獻和延伸閱讀，學生可以核對結果，也能找到接下來讀什麼。

局限

• 古典範圍。 目錄中看不到代數數論，質數定理和ζ函數只出現在最後一章的最後一節。要走向代數數論或解析數論的學生需要另找教材。
• 密碼學較簡短。 密碼學只有一章，三個小節，排在二次互反律之後；以密碼學為中心的課程會希望有一本更早、更充分地融入密碼學的書。
• 只有部分習題有答案。 書末提供的是部分習題而非全部習題的答案，獨自學習的學生核對證明的手段有限，有學習夥伴或老師會更有幫助。
• 小節較少的章節。 有幾章只有很少的小節：第12章兩節，第3、10、14章各三節，想在這些話題上深入的課程可能需要補充材料。

在課程中的定位

在本站的數論書籍中，Burton 是一本古典的一學期教材。Silverman 的 A Friendly Introduction to Number Theory 從高中代數出發，強調實驗與猜想，是更平緩的入門第一本；Robin Wilson 的 Number Theory: A Very Short Introduction 是一本配有簡短證明和歷史的緊湊導覽，適合想在投入完整課程之前先了解全貌的讀者。Burton 則是古典課程的完整篇幅的講法，經原根和二次互反律，一直到平方和與連分數等後面的章節。

Kraft 和 Washington 的 An Introduction to Number Theory with Cryptography 涵蓋許多相同的古典內容，同時把密碼學應用貫穿始終，因此在以安全和計算為目標時是自然的替代選擇。若要更進一步，Hardy 和 Wright 的 An Introduction to the Theory of Numbers 是初等數論與解析數論的經典論著；Ireland 和 Rosen 的 A Classical Introduction to Modern Number Theory 是以抽象代數為前提的研究生教材，通向互反律、有限域上的ζ函數和橢圓曲線。

如何使用本書

出版社把本書定位為數學專業、中學教育專業和電腦科學專業學生修讀的一學期本科數論課程的教材。本站的先修條件一欄寫的是包括歸納法在內的一些證明經驗，第1章會複習歸納法和二項式定理。

第一遍閱讀的實用計畫如下：

• 核心： 第2–5章和第7–9章，即從整除性到二次互反律。第6章的數論函數（及其日曆應用）可以根據時間決定取捨。
• 按興趣選擇： 密碼學讀第10章，特殊數和平方和讀第11章和第13章，連分數和佩爾方程讀第15章，第16章則可作為質數檢定和解析方法的預告。
• 歷史小節： 作為背景閱讀；它們介紹結果背後的人物，也能說明某個話題為什麼出現在課程中。
• 習題： 每一節都要做計算題和證明題的搭配，並用書末部分習題的答案和數表核對結果。

讀完之後還想深入的讀者，可以把本書的延伸閱讀作為起點，或轉向上面提到的更高階的教材。