數論基礎

第一章：什麼是數論？

第000007頁

乍一看，“數論”這個詞似乎神秘而寬泛。難道數學不都是關於數字的嗎？這僅僅是數學的另一個名稱嗎？更謹慎的讀者可能會注意到，幾何和邏輯（例如）並不是真正關於數字的，即使有時會用到數字。但是，即使不包括這些主題，“數字的研究”聽起來仍然過於寬泛。確實，“數論”一詞是傳統的，它專門指對整數的研究；也就是說，我們用來計數的數字

1, 2, 3, 4, ...

以及大膽新增的0，以及在方便的時候，負整數。不考慮分數、實數和複數。雖然在日常語言中這些抽象概念被稱為數字，但傳統上它們是在分析課程中研究的。

雖然整數起源於計數，但數論也不是關於計數的。高階計數技術的學習是一個獨立的數學領域，稱為組合數學。因此，數論是對整數及其相互關係的純粹研究，特別是關於加法和乘法，這兩者都將始終將整數轉換為整數。為了理解這意味著什麼，請考慮以下關於整數的問題

• 兩個奇數的和是偶數還是奇數？乘積呢？
• 如果我們將n除以3，餘數為2。如果我們將同一個數n除以17，餘數為9。n的可能值是什麼？
• 2的冪是否可以以“...324”結尾？
• 什麼時候正整數n可以寫成兩個整數平方和？
• 如果n > 1，數字$1+{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n}}$是否可以成為整數？
• 方程$12x-57y=39$是否有整數解x和y？如果將39替換為38呢？

到目前為止，如上所述，數論可能看起來是一個相當抽象的話題，需要花費數月（數年？）來學習。確實，由於其表面上的純潔性和與工業或科學應用的巨大距離，數論曾經被稱為“數學女王”。

第000008頁

情況已不再如此。雖然仍然被認為是抽象數學優雅的典範，但數論現在為資訊理論和計算機科學提供了具體的應用，包括密碼學、資料壓縮、糾錯碼和偽隨機數生成，僅舉幾例。

儘管如此，學習數論最令人信服的理由在於它將簡潔性和令人費解的複雜性獨特地結合在一起，這為數學的美、驚喜和突然的清晰度提供了背景，這些對於那些喜歡數學的人來說是如此令人興奮。

第二章：整數和算術

第000009頁

我們的主要研究物件是整數集Z；也就是說，正整數和負整數

Z = {..., −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, ...}

用N表示自然數集也很方便；也就是說，正整數

N = {1, 2, 3, 4, 5, 6, 7, 8, ...}

我們假設讀者熟悉整數的性質，這些性質應該在小學時就學過。特別是，整數是有序的，並且在加法、減法和乘法下是封閉的。此外，我們還假設N在加法和乘法下是封閉的。

以下恆等式總結了整數的代數性質。

定理2.1（整數算術的基本性質）

設$a,b,c\in Z$。

• $a+b=b+a$（加法是可交換的。）
• $a+(b+c)=(a+b)+c$（加法是結合的。）
• $a+0=a$（零是加法單位元。）
• $a+(-a)=0$（每個整數都有一個加法逆元。）
• $ab=ba$（乘法是可交換的。）
• $a(bc)=(ab)c$（乘法是結合的。）

• $a*1=a$（1 是乘法單位元。）
• $a(b+c)=ab+ac$（分配律）
• 如果 $ab=0$，則 a = 0 或 b = 0（或兩者都為 0）。（整環）

上面列表中的最後一個性質暗示了以下的消去律。

命題 2.2 設 $a,b,c\in Z$，並假設 a ≠ 0。如果 $ab=ac$，則 $b=c$。

證明。由於 $ab=ac$，我們有 $ab-ac=0$。由於 a ≠ 0，定理 2.1 中的最後一個性質意味著 $b-c=0$，因此 $b=c$。

注意我們在上面的證明中沒有說些什麼。我們沒有討論“兩邊同時除以 a”。相反，證明使用了加法、減法

第 000010 頁

和乘法的性質，而沒有直接引用除法。這樣拐彎抹角的原因將在理論展開的過程中變得清晰。