初等整數論 台大數學系 齊震宇

大家小學時就知道每個正整數都可以寫成 質數的乘積，像是 、 。 問： 給定整數 ， (這裡 為相異質數， 為正整數或 。) 請問 有幾個正的因數？ 學過排列組合的同學馬上會回答： 「 超簡單 der， 答案是 。 因為 的正因數全體恰為形如 並滿足 、 的數。」

真是這麼簡單 der 嗎？ 仔細想想他的理由： 「 的正因數全體恰為形如 並滿足 、 的數。」 形狀如此的數字當然都是 的正因數，但 反過來， 的正因數為何非長這樣不可呢？ 你能說明為什麼嗎？ (先想想再往下看！) 你有沒有不經意地用到下面這件事？ 「如果一質數 整除若干個正整數的乘積， 那麼 必至少整除其中某一個。」

來問個更瞎的問題好了？ 給定若干個質數 ， 是否能找到兩組 非負整數 與 ，使得 但卻對 中的某個數 有 ？ 換句話說， 給定若干個質數 ， 是否能找到兩組 非負整數 與 ，使得 但卻對 中的某個數 有 ？ 換句話說， 把一個正整數寫成質數乘積的方法 只有一種嗎？ (先想想再往下看！) 是否又偷偷用了 「如果一質數 整除若干個正整數的乘積， 那麼 必至少整除其中某一個。」 為什麼這是對的呢？ (試著從這堂課的內容裡找線索！)

在以下的課程中，你會不斷看到「定義」 這兩個字。 所謂定義，指的是去規定要用甚麼 名稱或術語來 稱呼某種特定的數學對象； 代表某種特定的概念、行為或現象。 但任何定義或是 論證中使用的對象與概念都必須嚴格採用先前 已經給出的定義， 思考時可以大膽想像與嘗試， 不能訴諸平常可能的習慣用 語或想法。 在數學入門上，不這麼做很容易會 造成許多障礙，這點非常重要。 這是一種很難的遊戲，但玩久了定會愛不釋手！

Why? 除法(division) 給定一整數 與一自然數 ， 必可找到一整數 與一自然數 滿足條件 ， 且這樣的組合 、 是唯一的。 給定一整數 與一自然數 ， 必可找到一整數 與一自然數 滿足條件 ， Why? 且這樣的組合 、 是唯一的。 條件 相當於說 首先， 整數 必須使得 成立。 這樣的 存在， 因為 ； (見下頁圖解說明) 這樣的 唯一， 因為不同 對應的區間不相交。 有了 ， 就唯一地決定了 。

除法(division) 拿長度為 的「區間尺」量 ： 此操作稱為以 為被除數、 為除數的除法， 整數 與自然數 分別稱為商與餘數。 定義 說「 整除 」或說「 被 整除」 的意思是 。

( ) 可除性(divisibility) 給定兩整數 與 。 定義： 我們說「 是 的因數」、「 是 的倍數」 的意思是 給定兩整數 與 。 定義： 我們說「 是 的因數」、「 是 的倍數」 的意思是 存在一個整數 使得 。 我們記這樣的狀況為 ，否則記 。 ( ) 練習ㄧ： 證明 整除 。 (請從左右兩邊的定義 出發而非使用直覺！ 例： 、 。

公因數(divisor)與最大公因數(greatest common divisor) 給定兩個整數 與 。 定義 與 的公因數中最大者稱為它們的 最大公因數， 記作 或 。 (不要跟區間或座標符號搞混了！) 立刻可以提幾個自然的問題： (1)怎麼實際求得 ？ (除了真的「列出」 與 的所有因數。) (2) 有甚麼性質？

歐幾里得除法(the euclidean algorithm) 給定兩個整數 與 。 (又名「歐幾里得除法」) 與 的最大公因數可透過輾轉相除法求得。 原理： 如果有整數 與 滿足 ， 則 與 的公因數全體 與 的公因數全體 例如要求 的最大公因數： 與 的共同因數全體 與 的共同因數全體 與 的共同因數全體 與 的因數全體

它的逆命題對嗎？ 有整數解 整係數一次方程式 給定三個整數 、 與 。 問： 何時能找到整數 與 令 ？ 換句話說， 方程式 何時有整數解？ 給定三個整數 、 與 。 問： 何時能找到整數 與 令 ？ 換句話說， 方程式 何時有整數解？ 首先注意到， 如果 有整數解， 則 與 的公因數都會是 的因數。 特別地， 與 的最大公因數會是 的因數。 這說明 有整數解 它的逆命題對嗎？

？ 有整數解 整係數一次方程式 給定三個整數 、 與 。 假設 ， 也就是有一整數 使得 。 要解方程式 的整數解， 只須找 的整數解即可： 給定三個整數 、 與 。 有整數解 ？ 假設 ， 也就是有一整數 使得 。 要解方程式 的整數解， 只須找 的整數解即可： 若兩整數 與 滿足 ， 則 。 要如何找 的整數解呢？

整係數一次方程式 事實上， (反轉了的)輾轉相除法提供了求 的整數解的方法。 以求方程式 的整數解為例。 故 。

整係數一次方程式 總結前面的討論，我們證明了 定理 給定三個整數 、 與 ， 有整數解 。 實作流程 思考： 給定三個整數 、 與 ， 有整數解 。 實作流程 先利用輾轉相除法求 並記錄過程 為 原方程的一組整數解 倒轉輾轉相除法過程，求出一組 的整數解 。 無整數解 思考： 有一組整數解後，怎麼找出所有整數解？

( 。) 整係數一次方程式 因此，給定兩個整數 與 ， 我們有 有整數解 。 特別地， 如果 與 互質， 則對任何整數 ， 因此，給定兩個整數 與 ， 我們有 有整數解 。 特別地， 如果 與 互質， 則對任何整數 ， 方程式 總有整數解。 給定兩個整數 與 。 思考： 有了一組整數解，如何找出所有的整數解？ 練習二： 整數 若整除 且與 互質，則整除 。 ( 。)

同餘(congruence) 定義 給定三個整數 、 及 並假設 。 如果 ， 我們記 。 讀作「 與 (模 )同餘」。 例如 與 。

同餘 給定一整數 。 同餘與運算 給定整數 、 、 與 。 如果 且 ， 則 且 。 也就是說， 這種奇怪的等號「 」 跟普通的等號很像， 等量相加或相乘仍為等量。 證明： 與 均為 的倍數。

同餘 給定一整數 。 同餘與運算 給定整數 、 、 與 。 如果 且 ， 則 且 。 同餘反元素 給定一整數 。 。 這樣的 稱為 的一個同餘反元素， 因為 與 的積在同餘意義下等於 。 證明： 因為 與 互質， 由定理知 存在整數 與 滿足 ， 故 。

同餘 給定一整數 。 同餘與運算 給定整數 、 、 與 。 如果 且 ， 則 且 。 同餘反元素 給定一整數 。 。 這樣的 稱為 的一個同餘反元素， 因為 與 的積在同餘意義下等於 。 證明： 因為存在整數 使得 ， 故存在整數 使得 ， 即 。 由定理知 。

同餘 給定一整數 。 同餘與運算 給定整數 、 、 與 。 如果 且 ， 則 且 。 同餘反元素 給定一整數 。 。 同餘消去律 對任三整數 、 與 ， 如果 且 ， 則 。 證明： 將原式兩邊同乘某個 的同餘反元素。