離散數學/數論

簡介

'數論' 本身就是一個龐大而涵蓋面廣的學科。我們將在這裡探討數論中的關鍵概念。

與實分析和微積分處理稠密實數集不同，數論考察的是離散集合中的數學，例如N或Z。如果你不確定集合的概念，你可能需要重新閱讀集合論。

數論是研究整數的學科，它是數學中最古老和最豐富的分支之一。它的基本概念包括整除性、素數和方程的整數解——這些概念都很容易理解，但它們立即引出了數學中最著名的定理和最大的未解問題。數論也是一門高度跨學科的學科。組合學（計數的研究）、代數和複分析中的思想都找到了自己的位置，最終成為理解數論各個部分的必要條件。事實上，所有數學中最偉大的開放問題，黎曼猜想，與複分析有著密切的聯絡。但不要害怕，直接開始學習初等數論吧，它是最熱情的純數學邀請之一，也是應用數學中最令人驚訝的領域之一！

整除性

請注意，在R、Q和C中，我們可以自由地除法，除了零。這個性質通常稱為封閉性——兩個有理數的商仍然是有理數，等等。但是，如果我們把數學運算限制在Z這樣的集合中，就會遇到困難。這是因為，在整數中，兩個整數相除的結果可能不是另一個整數。例如，我們當然可以將 6 除以 2 得到 3，但我們不能將 6 除以 5，因為分數 6/5 不屬於整數集。

然而，我們可以引入一個新的關係，其中定義了除法。我們把這種關係稱為整除性，如果${\frac {b}{a}}$是一個整數，我們就說

• $a$ 整除 $b$
• $a$ 是 $b$ 的一個因子
• $b$ 是 $a$ 的一個倍數
• $b$ 可以被 $a$ 整除

形式上，如果存在一個整數 $q$ 使得 $b=qa$，那麼我們說 $a$ **整除** $b$，並寫作 $a\mid b$。如果 $a$ 不整除 $b$，那麼我們寫作 $a\nmid b$

**命題。** 以下是該定義的一些基本推論。令 a，b，c 為整數

• (a) 如果 a|b，那麼 a|(bc)。
• (b) 如果 a|b 且 b|c，那麼 a|c。
• (c) 如果 a|b 且 a|c，那麼對於任意整數 x 和 y，a|(xb+yc) - 換句話說，a 整除其倍數的任何線性組合。
• (d) 如果 a|b 且 b|a，那麼 a = b 或 a = -b。
• (e) 如果 c 不為 0，那麼 a|b 等價於 ca|cb。

商和餘數定理

對於任何整數 n 和任何 k > 0，存在唯一的 q 和 r 使得

n = qk + r (其中 0 ≤ r < k)

這裡 n 被稱為被除數。

我們稱 q 為 **商**，r 為 **餘數**，k 為 **除數**。

透過代數重排，這個定理可能更容易理解

n/k = q + r/k (0 ≤ r/k < 1)

模運算

我們能對整除另一個數的數說些什麼？以 8 為例。1 除以 8 的餘數是多少？使用上面的除數定理

0 = 8*0 + 0

1 = 8*0 + 1

2 = 8*0 + 2

:

8 = 8*1 + 0

9 = 8*1 + 1

10 = 8 * 1 + 2

:

等等

我們對餘數有一個表示法，可以將上面的等式寫成

0 mod 8 = 0

1 mod 8 = 1

2 mod 8 = 2

3 mod 8 = 3

4 mod 8 = 4

5 mod 8 = 5

6 mod 8 = 6

7 mod 8 = 7

8 mod 8 = 0

9 mod 8 = 1

10 mod 8 = 2

:

我們也可以寫成

1 ≡ 1 (mod 8)

2 ≡ 2 (mod 8)

3 ≡ 3 (mod 8)

4 ≡ 4 (mod 8)

5 ≡ 5 (mod 8)

6 ≡ 6 (mod 8)

7 ≡ 7 (mod 8)

8 ≡ 0 (mod 8)

9 ≡ 1 (mod 8)

10 ≡ 2 (mod 8)

:

這些表示法都簡短地代表了

a = 8k+r，其中 k 為整數。

因此，例如，x ≡ 1 (mod 8) 等同於說

x = 8k+1

注意，這裡比較除數演算法的餘數是 1。x ≡ 1 (mod 8) 詢問哪些數除以 8 的餘數為 1？顯然，解是 x=8×0+1, 8×1+1,... = 1, 9, ...

通常情況下，我們對除以 n 的所有餘數集合感興趣 - 我們稱之為 **模 n** - 並寫作 Z_n。注意，該集合是有限的。9 除以 8 的餘數是 1，與 1 除以 8 的餘數相同。因此，在某種意義上，9 實際上是“與” 1 “相同”。事實上，關係 “≡”

x ≡ y 當且僅當 x mod n = y mod n。

是一個等價關係。我們稱該關係為 **同餘**。注意，由同餘定義的等價類正是 Z_n 的元素。

我們可以透過使用除數演算法找到一個模 n 的數 a（或說 a 與 n 同餘）。

加法、減法和乘法在 Z_n 中有效 - 例如 3 + 6 (mod 8) = 9 (mod 8) = 1 (mod 8)。這些數字看起來很奇怪，但它們遵循許多正常的性質，例如交換性和結合性。

如果我們有一個大於 n 的數，我們通常先把它歸約到模 n - 再次使用除數演算法。例如，如果我們想要找到 11+3 mod 8，通常更容易計算 3 + 3 (mod 8)，而不是將 14 歸約到模 8。一個常用的技巧是，例如，如果我們有 6 + 7 (mod 8)，我們可以使用 **負** 數代替，使問題變為 -2 + -1 = -3 = 5 (mod 8)。

當我們想要檢視包含模某個 n 的數的方程時，我們經常使用第二種表示法。例如，我們可能想要找到一個數 x 使得

3x ≡ 5 (mod 8)

我們可以透過試探法來找到解（遍歷從 0 到 7 的所有數字），但如果模數非常大怎麼辦？我們將在後面研究更系統的解決方案。

**注意：** 我們通常說我們在 Z_n 中工作，並在整個過程中使用等號。熟悉這三種寫模運算方程和表示式的形式。

模運算的一致性

令 $n\geq 2$ 表示任意基數。給定任意整數 $x$，整數序列 $...,x-2n,x-n,x,x+n,x+2n,...$ 在模 $n$ 意義下彼此同餘。

$...\equiv x-2n\equiv x-n\equiv x\equiv x+n\equiv x+2n\equiv ...\;\;({\text{mod}}\;n)$

在模運算中，兩個在模 $n$ 意義下同餘的整數 $x$ 和 $y$ ($x\equiv y\;\;({\text{mod}}\;n)$) 都“代表”來自 $\mathbb {Z} _{n}$ 的相同量。只要 $x\equiv y\;\;({\text{mod}}\;n)$，可以用任意整數 $x$ 代替整數 $y$。

這意味著

• 給定任意整數 $x_{1},x_{2}$ 和 $y_{1},y_{2}$，如果 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ 並且 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，那麼 $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$。

證明

由於 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$，存在整數 $k_{x}\in \mathbb {Z}$ 使得 $x_{2}=x_{1}+k_{x}n$。

由於 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，存在整數 $k_{y}\in \mathbb {Z}$ 使得 $y_{2}=y_{1}+k_{y}n$。

可以推匯出 $x_{2}+y_{2}=(x_{1}+k_{x}n)+(y_{1}+k_{y}n)=(x_{1}+y_{1})+(k_{x}+k_{y})n$，因此 $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$。

• 對於任意整數 $x_{1},x_{2}$ 和 $y_{1},y_{2}$，如果 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ 且 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，則 $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$。

證明

由於 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$，存在整數 $k_{x}\in \mathbb {Z}$ 使得 $x_{2}=x_{1}+k_{x}n$。

由於 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，存在整數 $k_{y}\in \mathbb {Z}$ 使得 $y_{2}=y_{1}+k_{y}n$。

可以推匯出 $x_{2}y_{2}=(x_{1}+k_{x}n)(y_{1}+k_{y}n)=x_{1}y_{1}+k_{x}y_{1}n+x_{1}k_{y}n+k_{x}k_{y}n^{2}$$=x_{1}y_{1}+(k_{x}y_{1}+x_{1}k_{y}+k_{x}k_{y}n)n$ 因此 $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$.

進位制

在數學中，不同進位制之間的轉換是最繁瑣的過程之一。

我們日常生活中使用的數字都是十進位制的。這意味著用十個數字來表示一個數字。這十個數字是 {0,1,2,3,4,5,6,7,8,9}。

類似地，四進位制有四個數字 {0,1,2,3}，二進位制有兩個數字 {0,1}。二進位制有時被稱為二進位制。

還有大於十進位制的進位制。對於這些進位制，通常使用字母來表示大於十的數字。例如十六進位制（Hexadecimal）。此進制中使用的數字是 {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}。

為了在不同進位制之間進行轉換，必須知道如何進行除法並求餘數。

要從十進位制轉換為其他進位制，只需要不斷地用目標進位制的值進行除法，然後對第一個除法的結果再進行除法，忽略餘數，依此類推，直到結果小於目標進位制的值（因此除法的結果將為零）。然後，目標進位制的數字是從末尾到開頭讀取的餘數。

以下展示瞭如何將十進位制數（105）轉換為二進位制。

運算	餘數
105 / 2 = 52	1
52 / 2 = 26	0
26 / 2 = 13	0
13 / 2 = 6	1
6 / 2 = 3	0
3 / 2 = 1	1
1 / 2 = 0	1

答案： 1101001

完成此過程後，將餘數從下到上依次排列，然後將最後一個商（在本例中為 1101001）顯示為數字 105 的二進位制等價值。

總而言之，將十進位制的原始數字反覆進行除法，記錄餘數，直到商小於進位制的數值。

這適用於將任何十進位制數字轉換為任何進位制。如果進制中存在任何字母，則使用字母替換大於 9 的任何餘數。例如，將十進位制中的 11 寫成十四進位制。

運算	餘數
11 / 14 = 0	B (=11)

答案： B

由於 11 只有一個餘數，所以它被寫成一個數字。根據模式 {10=A, 11=B, 12=C...35=Z}，將其寫成 B。如果你寫 “11” 作為答案，那就是錯誤的，因為十四進位制的 “11” 等於十進位制的 15！

要將任何進位制的數字轉換為十進位制，應使用以下過程

以十進位制的 3210 為例。在個位（10⁰）上是 0。在十位（10¹）上是 1。在百位（10²）上是 2。在千位（10³）上是 3。

計算上述數字值的公式為

3×10³ + 2×10² + 1×10¹ + 0×10⁰ = 3000 + 200 + 10 + 0 = 3210。

從任何進位制轉換為十進位制的過程類似。例如，以六進位制的 3452 為例。在個位（6⁰）上是 2。在六位（6¹）上是 5。在三十六位（6²）上是 4。在 216 位（6³）上是 3。

計算上述數字值（在十進位制中）的公式為

3×6³ + 4×6² + 5×6¹ + 2×6⁰ = 648 + 144 + 30 + 2 = 824。

六進位制的 3452 在十進位制中為 824。

一種更高效的演算法是將最左邊的數字加上進位制值，然後重複該過程，依次處理下一個數字。

((3 * 6 + 4) * 6 + 5) * 6 + 2 = 824

不同進位制之間的轉換過程乍看起來可能很困難，但如果經常練習，就會變得很容易。

質數

質數是整數的基石。質數是一個大於 1 的正整數，它只有兩個約數：1 和它本身。例如，17 是質數，因為只有 1 和 17 才能整除它。數字 6 不是質數，因為 6 有超過兩個約數，分別是 1、2、3、6。此外，請注意 1 不是質數，因為 1 只有一個約數。

一些質數

質數序列的開頭是

2, 3, 5, 7, 11, 13, 17, 19, 23, ...

歐幾里得證明存在無限多個質數

古希臘數學家歐幾里得給出了一個關於質數無窮多的優雅證明。這個證明依賴於這樣一個事實，即所有非質數——合數——都可以被唯一地分解成質數的乘積。

歐幾里得的證明採用反證法：我們假設質數只有有限個，然後證明我們可以得出邏輯上矛盾的事實。

所以我們開始了。首先，我們假設質數只有有限個

p₁, p₂, ... , p_n

現在考慮以下定義的數字 M

M = 1 + p₁ * p₂ * ... * p_n

關於數字 M 有兩個重要的事實——最終是矛盾的

1. 它不可能是質數，因為 p_n 是最大的質數（根據我們的初始假設），而 M 明顯大於 p_n。因此，一定存在某個質數 p 可以整除 M。
2. 它不能被 p₁, p₂, ..., p_n 中的任何一個數字整除。考慮一下，如果你試圖將 M 除以列表 p₁, p₂, ... , p_n 中的任何一個質數會發生什麼。從 M 的定義可以看出，你最終會得到餘數 1。這意味著 p——整除 M 的質數——必須大於 p₁, ..., p_n 中的任何一個。

因此，我們證明了 M 可以被一個比 p_n 大的質數 p 整除。因此，不可能存在最大的質數。

這兩個事實表明，M 必須被一個大於 p_n 的質數整除。因此，不可能存在最大的質數。

請注意，此證明並未提供直接生成任意大素數的方法，儘管它始終會生成一個被新的素數整除的數字。假設我們只知道一個素數：2。因此，我們的素數列表很簡單，即 p₁=2。然後，在證明的符號中，M=1+2=3。我們注意到 M 是素數，因此我們將 3 新增到列表中。現在，M = 1 +2 *3 = 7。同樣，7 是素數。因此，我們將其新增到列表中。現在，M = 1+2*3*7 = 43：又是素數。繼續此過程一次，我們計算 M = 1+2*3*7*43 = 1807 =13*139。因此，我們看到 M 不是素數。

從另一個角度來看：注意，雖然 1+2、1+2*3、1+2*3*5、1+2*3*5*7 和 1+2*3*5*7*11 是素數，但 1+2*3*5*7*11*13=30031=59*509 不是。

素數測試

有很多簡單而複雜的素數測試方法。我們將在本文中介紹一些簡單的測試方法。在高階課程中，我們將介紹一些更快、更復雜的方法來測試一個數字是否是素數。

檢查

最直接、最簡單的排除數字 n 為素數的方法是檢查數字的個位數或最後一位。

如果數字 n 以偶數 0、2、4、6、8 結尾，我們可以證明數字 n 不能是素數。例如，取 n = 87536 = 8753(10) + 6。由於 10 可被 2 整除，6 可被 2 整除，因此 87536 必須可被 2 整除。一般而言，任何偶數都可以表示為 n = a*10 + b 的形式，其中 b = 0、2、4、6、8。由於 10 可被 2 整除，b 可被 2 整除，因此 n = a*10 + b 可被 2 整除。因此，任何以偶數結尾的數字 n，例如 7777732 或 8896，都可以被 2 整除，因此 n 不是素數。

在類似的論證中，如果數字 n 以 5 結尾，我們可以證明數字 n 不能是素數。如果 n 的最後一位數字，稱之為 b，是 5，我們可以將 n 表示為 n = a*10 + b 的形式，其中 b = 5。由於 10 可被 5 整除，b = 5 可被 5 整除，因此 n = a*10 + b 可被 5 整除。因此，任何以 5 結尾的數字 n，例如 93475，都可以被 5 整除，因此 n 不是素數。

因此，如果大於 5 的數字是素數，它必須以 1、3、7 或 9 結尾。注意，這並不意味著所有以 1、3、7 或 9 結尾的數字都是素數。例如，雖然數字 11、23、37、59 是素數，但數字 21 = 3*7、33 = 3*11、27 = 3*9、39 = 3*13 不是素數。因此，如果數字以 1、3、7 或 9 結尾，我們需要進一步測試。

試除法

要測試以 1、3、7 或 9 結尾的數字 n 是否是素數，我們可以簡單地嘗試最小的素數，並嘗試將其除以 n。如果不能整除，我們將取下一個最大的素數，然後再次嘗試，依此類推。當然，如果我們以這種方式取所有小於 n 的素數，並且無法除以 n，那麼我們有理由說 n 是素數。然而，可以證明，我們不必取所有小於 n 的素數來測試 n 是否是素數。我們可以使用試除法更早地停止測試。

試除法的理由是，如果數字 n 沒有小於或等於 ${\sqrt {n}}$ 的除數，那麼 n 必須是素數。我們可以用反證法來證明這一點。假設 n 沒有小於或等於 ${\sqrt {n}}$ 的除數。如果 n 不是素數，則必須存在兩個數字 a 和 b 使得 $a*b=n$。特別地，根據我們的假設，${\sqrt {n}}<a$ 並且 ${\sqrt {n}}<b$。但是，然後 $n={\sqrt {n}}{\sqrt {n}}<a*b=n$。由於數字不能大於自身，因此數字 n 必須是素數。

試除法是一種素數測試方法，它涉及取一個數字 n，然後依次用小於或等於 ${\sqrt {n}}$ 的素數除以它。

例如，113 是素數嗎？${\sqrt {113}}$ 大約為 10.63... 我們只需要測試 2、3、5、7 是否能整除 113（不留餘數，即商是整數）。

113/2 不是整數，因為最後一位數字不是偶數。

113/3 (=37.666...) 不是整數。

113/5 不是整數，因為最後一位數字不以 0 或 5 結尾。

113/7 (=16.142857...) 不是整數。

因此，我們不需要檢視小於 113 的任何其他素數，例如 11、13、17 等，因為 2、3、5、7 不能整除 113，所以 113 是素數。

注意，在排除了 2 和 3 作為除數之後，我們接下來考慮下一個素數 5，而不是下一個數字 4。我們知道不要考慮 4，因為我們知道 2 不能整除 113。如果 2 不能整除 113，那麼 4 肯定也不能，因為如果 4 整除 113，並且 2 整除 4，那麼 2 就應該整除 113。所以我們只使用下一個最便宜的素數來測試，而不是下一個連續的數字。

如果我們測試 91，我們會得到：

91/2 不是整數，因為最後一位數字不是偶數。

91/3= (30.333) 不是整數。

91/5= 不是整數，因為最後一位數字不以 0 或 5 結尾。

91/7=13 是整數

所以我們知道，由於 7 整除 91，所以 91 不是素數。

試除法通常只用於相對較小的數字，因為它效率低下。但是，該技術有兩個優點：首先，一旦我們測試了數字，我們就可以確定它是素數；其次，如果數字不是素數，它也會給出數字的因子。

為了獲得一些小的素數，最好使用 埃拉託斯特尼篩法，而不是使用試除法順序測試每個數字。 埃拉託斯特尼篩法基本上是一個透過消除來尋找素數的過程。 我們首先從一個連續數字列表開始，比如 1 到 100。 將數字 1 刪除，因為該數字不是素數。 選擇下一個最小的未劃去的數字 2，並將其圈起來。 現在，在列表中劃去所有 2 的倍數。 接下來，選擇下一個最小的未圈起的數字 3。 將數字 3 圈起來，並劃去所有 3 的倍數。 下一個最小的未圈起的數字應該是 5，因為 4 是 2 的倍數，應該已經被劃去了。 將數字 5 圈起來，並劃去所有 5 的倍數。 下一個最小的未圈起的數字應該是 7，因為 6 是 2 的倍數。 將 7 圈起來，並劃去所有 7 的倍數。 現在，下一個未劃去的數字應該是 11，因為 8、9、10 分別是 2、3 和 2 的倍數。 如果我們繼續以這種方式進行，剩下的就是圈起來的數字，即素數。 但是請注意，在劃去 7 的倍數後，我們實際上可以停止並圈起所有未劃去的數字，因為根據結果，由於 ${\sqrt {100}}=10$ 小於 100 的任何非素數都必須能被 2、3、5 或 7 整除。

算術基本定理

算術基本定理是一個關於數字分解的重要定理。 該定理基本上指出，每個正整數都可以以唯一的方式寫成素數的乘積（忽略素數乘積的順序）。

特別是，算術基本定理意味著任何數字，例如 1,943,032,663，要麼是素數，要麼可以分解成素數的乘積。 如果像 1,943,032,663 這樣的數字可以分解成素數，例如 11×13×17×19×23×31×59，那麼嘗試尋找另一個不同的素數組合來得到相同的數字是徒勞的。

為了使該定理對數字 1 仍然適用，我們認為 1 是零個素數的乘積。

更正式地說，

對於所有 n∈N

n=p₁p₂p₃...

其中 p_i 都是素數，可以重複。

以下是一些示例。

4 = 2 × 2 = 2²

12 = 2 × 2 × 3 = 2² × 3

11 = 11.

在建立貝祖等式之後，將給出算術基本定理的證明。

最小公倍數和最大公約數

我們可以根據兩個數字的分解確定它們的兩個特徵：最小公倍數，即LCM，和最大公約數，即GCD（也稱為最大公因數，即GCF）

最小公倍數

兩個數字 a 和 b 的最小公倍數（或最小公倍數）是指由 LCM(a,b) 表示的最小數字，該數字既能被數字 a 整除，又能被數字 b 整除。 我們可以透過找到 a 和 b 的素數分解，併為每個素數因子選擇最大冪來找到 LCM(a,b)。

換句話說，如果數字 a 分解成 $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$，而數字 b 分解成 $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$，那麼 LCM(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$，其中 $\gamma _{i}=Maximum(\alpha _{i},\beta _{i})$ 對於 i = 1 到 n。

例如，讓我們看看如何找到 5500 和 450 的最小公倍數，它恰好是 49500。 首先，我們找到 5500 和 450 的素數分解，即

5500=2² 5³ 11

450=2 3 ² 5²

注意，我們為數字 5500 和數字 450 得出的不同素數是 2、3、5 和 11。 現在，讓我們用這些素數的適當冪來完全表示 5500 和 450。

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

LCM(5500,450) 將以 2^? 3^? 5^? 11^? 的形式出現。 現在我們只需要找到每個素數的冪是多少。

因此，我們比較 5500 和 450 中每個素數的冪。 讓我們考慮第一個素數 2 的冪。 在數字 5500 中，素數 2 的冪是 2，而在數字 450 中，素數 2 的冪是 1。 由於素數 2 的冪在 2 和 1 之間的最大值是 2，因此我們使用 2 作為素數 2 的冪。

現在讓我們考慮素數 3 的冪。 在數字 5500 中，素數 3 的冪是 0，而在數字 450 中，素數 3 的冪是 2。 由於素數 3 的冪在 0 和 2 之間的最大值是 2，因此我們使用 2 作為素數 3 的冪。

類似地，讓我們考慮下一個素數 5 的冪。 在數字 5500 中，素數 5 的冪是 3，而在數字 450 中，素數 5 的冪是 2。 由於素數 5 的冪在 3 和 2 之間的最大值是 3，因此我們使用 3 作為素數 5 的冪。

最後，讓我們考慮素數 11 的冪，它是我們列表中的最後一個素數。在數字 5500 中，素數 11 被提升到第一冪，在數字 450 中，素數 11 被提升到零次冪。由於素數 11 的冪在 1 和 0 之間的最大值為 1，因此我們使用 1 作為最後一個素數 11 的冪。

因此，我們結果的乘積是 LCM(5500,450)=2² 3² 5³ 11¹ = 49500。

GCD

兩個數字 a 和 b 的最大公約數是表示為 GCD(a,b) 的最大數字，它同時可以整除數字 a 和數字 b。與查詢 LCM(a,b) 的過程類似，我們可以透過查詢 a 和 b 的質因數分解來找到 GCD(a,b)，但選擇每個質因子的最小冪。

換句話說，如果數字 a 分解為 $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$，而數字 b 分解為 $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$，那麼 GCD(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$ 其中 $\gamma _{i}=Minimum(\alpha _{i},\beta _{i})$ 對於 i = 1 到 n。

例如，讓我們看一下如何找到 5500 和 450 的最大公約數，它恰好是 50。首先，我們找到 5500 和 450 的質因數分解，即

5500=2² 5³ 11

450=2 3 ² 5²

注意，我們為數字 5500 和數字 450 得出的不同素數是 2、3、5 和 11。 現在，讓我們用這些素數的適當冪來完全表示 5500 和 450。

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

GCD(5500,450) 將採用 2^? 3^? 5^? 11^? 的形式。我們現在要做的就是找到每個素數的冪是多少。

現在我們比較 5500 和 450 中每個素數的冪。讓我們考慮第一個素數 2 的冪。在數字 5500 中，素數 2 被提升到第二冪，在數字 4</syntaxhighlight> 50 中，素數 2 被提升到第一冪。由於素數 2 的冪在 2 和 1 之間的最小值為 1，因此我們使用 1 作為素數 2 的冪。

現在讓我們考慮素數 3 的冪。在數字 5500 中，素數 3 被提升到零次冪，在數字 450 中，素數 3 被提升到第二冪。由於素數 3 的冪在 0 和 2 之間的最小值為 0，因此我們使用 0 作為素數 3 的冪。

類似地，讓我們考慮下一個素數 5 的冪。在數字 5500 中，素數 5 被提升到第三冪，在數字 450 中，素數 5 被提升到第二冪。由於素數 5 的冪在 3 和 2 之間的最小值為 2，因此我們使用 2 作為素數 5 的冪。

最後，讓我們考慮素數 11 的冪，它是我們列表中的最後一個素數。在數字 5500 中，素數 11 被提升到第一冪，在數字 450 中，素數 11 被提升到零次冪。由於素數 11 的冪在 1 和 0 之間的最小值為 0，因此我們使用 0 作為最後一個素數 11 的冪。

因此，我們結果的乘積是 GCD(5500,450)=2¹ 3⁰ 5² 11⁰ = 50。

性質

• gcd(a,b)=gcd(b,a)
• gcd(a,b) = gcd(b,q)，其中 q 是 a 除以 b 的餘數
• gcd(a/d, b/d)=1，其中 d 是 gcd(a,b)

歐幾里得演算法

歐幾里得演算法是一種可以讓我們在不進行因式分解^*的情況下找到兩個數字的 GCD 的演算法。歐幾里得演算法只包含加法和乘法運算，並且以 GCD 的上述性質為基礎。

^* 因式分解是一個“困難”的過程，也就是說，對一個數字進行因式分解需要很長時間，具體取決於數字的長度。這就是為什麼以後，當您需要找到一對數字的 GCD 時，您很可能永遠不會對數字進行因式分解並使用素數的性質，而是使用歐幾里得演算法。

一個例子

我們將透過計算 gcd(458,44) 來了解它是如何工作的

首先，用 44 除 458 並得到餘數

458 = 44 × 10 + 18

現在假設一個數字是 458 和 44 的公約數。那麼它也必須是 18 的約數。要看到這一點，將上面的方程重新排列為

458 - 44×10 =18

當這個方程被 44 和 458 的公約數除時，左側得到一個整數，因此右側也必須得到一個整數。根據定義，這意味著該數字也是 18 的約數。透過相同的推理，18 和 44 的任何公約數也是 458 的約數。由於 458 和 44 的所有公約數都等於 44 和 18 的公約數，因此，特別地，最大公約數是相等的。因此，我們有 gcd(458,44)=gcd(44,18)

該演算法的下一步是將 44 除以 18 並找到餘數。

44 = 18 × k + r

44 = 18 × 2 + 8

重複這個過程；不斷用之前的餘數除之前的除數

18 = 8 × 2 + 2

8 = 2 × 4 + 0

我們的最大公約數是零之前的最後一個餘數，在本例中為 2。這是因為證明了 gcd(458,44)=gcd(44,18) 的推理適用於每一步，所以 gcd(458,44)=gcd(44,18)=gcd(18,8)=gcd(8,2)=gcd(2,0)=2。

矩陣方法

我們可以構造一個矩陣，提供一種計算最大公約數的替代方法。一般形式上，矩陣為

${\begin{bmatrix}1&0&b\\0&1&a\\\end{bmatrix}}$

回想一下，寫出兩個數的最大公約數的一種方法是作為整數線性組合。例如，如果我們正在尋找最大公約數，我們可以將其表示為as + bt，其中a 和b 是我們正在比較的兩個數，而s 和t 是整數。我們也知道b = aq + r，其中r 是b 除以a 後的餘數。在我們將第二行從第一行中減去後，我們得到

${\begin{bmatrix}1&-q_{1}&r_{1}\\0&1&a\\\end{bmatrix}}$

如果r_2 不為零，我們必須繼續該過程；這次，從第二行中減去第一行。我們繼續這個過程，直到其中一個r 被儘可能地減少。現在我們得到了最大公約數。在那行中，1 和 0 所在的位置的數字分別表示t 和s。

現在讓我們來看一個計算示例。

${\begin{bmatrix}1&0&99\\0&1&7\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&0&99\\0&14&98\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&-14&1\\0&14&98\\\end{bmatrix}}$

我們可以看到，現在進一步操作是微不足道的；我們只會得到第二行，其中a 所在的位置為零。所以我們檢視第一行並記住1 代表我們的餘數，1(=t) 乘以b，-14(=s) 乘以a，使得

$1=99\times 1+-14\times 7$

這可以透過歐幾里得演算法進行檢查，gcd(7,99)=1。

擴充套件歐幾里得演算法

如果我們嘗試透過回代來逆轉歐幾里得演算法的過程會發生什麼？回代相當繁瑣且容易出錯，因此這裡有一種更快的方法。

繪製一個包含四列的表格，從左到右依次標記為q、r、u、v。為了方便起見，標記一列i，表示我們當前所處的步驟。將a 和b（較大者位於上方）放在r 列中，並相應地放置 1 和 0

${\begin{matrix}i&q&r&u&v\\-1&.&b&0&1\\0&.&a&1&0\\\end{matrix}}$

現在透過取b/a 的商並將其放在q 列的下一個空間中，然後取b-aq 放在r 列中，向下迭代。

要更新u 和v，取

u_i = u_i-2-u_i-1q_i

v_i = v_i-2-v_i-1q_i

事實上，你正在尋找u 和v，使得 au + bv = gcd (a,b)。在某個時刻，gcd (a,b) 實際上是第 i 階段的餘數，所以你也可以計算 u_i 和 v_i，使得 au_i + bv_i = r_i，在每個階段。

推匯出上面發現的遞推關係來自以下三個方程（第二個方程是歐幾里得演算法的基本性質，另外兩個方程是我們為實現目標而設定的約束）

au_i-1 + bv_i-1 = r_i-1

r_i-2 = q_ir_i-1 + r_i

au_i + bv_i = r_i

訣竅是適當表示 r_i-2。

當你在r 列中獲得 0 時停止寫入。

然後找到 gcd(450,44)（這與 gcd(44,450) 相同）

${\begin{matrix}i&q&r&u&v\\-1&.&450&0&1\\0&.&44&1&0\\1&10&10&-10&1\\2&4&4&41&-4\\3&2&\mathbf {2} &-92&9\\4&2&0&-&-\\\end{matrix}}$

加粗的數字是最大公約數。觀察 (9)×450+(-92)×44=2，顯然這些u 和v 非常特殊。關於一般情況我們能說些什麼呢？

貝祖等式

在上面的情況下，我們有 9×450+(-92)×44=gcd(450,44)。所以 450 和 44 的最大公約數可以寫成 450 和 44 的線性組合，係數為整數。事實證明，這適用於任何一對整數。這個結果被稱為“貝祖等式”，可以表述如下

對於任何一對非零整數a 和b，存在整數u 和v，使得

au+bv=gcd(a,b)

證明

如果 *a* 和 *b* 是任何一對整數，且不全是 0，那麼顯然存在整數 *u* 和 *v* 使得 *au*+ *bv* 為正數（只需將 *u* 和 *v* 的符號分別與 *a* 和 *b* 的符號匹配即可，例如），並且對於所有整數 *u* 和 *v*，*au*+ *bv* 也是一個整數（因為整數在加法和乘法下是封閉的）。因此，存在一個非空正整數集，其包含形式為 *au*+ *bv* 的數字；我們將其稱為 S。由於 S 是一個非空的正整數集，它必須有一個最小元素（這就是所謂的 良序原理）。將此數字稱為 *d*。斷言是 $d=gcd(a,b)$。由於 *d* 屬於 S，因此

(1)$d=ua+vb$

對於合適的 *u* 和 *v*。設 *n* 為 *a* 和 *b* 的任何正公約數。由於 *n* 整除 (1) 的右邊，它也整除 d。因此 $d=qn$ 對於某些整數 $q\geq 1$。因此，*a* 和 *b* 的任何公約數都小於或等於 *d*。因此，如果 *d* 是 *a* 和 *b* 的公約數，那麼它是最大的公約數。現在只剩下要證明 *d* 實際上是一個公約數。

為了證明這一點，我們將證明 S 中的任何元素都可以被 *d* 整除。這將證明 *d* 是 *a* 和 *b* 的公約數，因為 *a* 和 *b* 都是 S 的元素（因為 *a* = 1×a + 0×b 且 *b* = 0×a + 1×b）。設 *t* 為 S 中的任何元素。然後，根據除法演算法

$t=qd+r$

對於某些 $0\leq r<d$。如果 *r* 不為 0，那麼它就在 S 中。這是因為 *d* 和 *t* 都在 S 中，所以

$r=t-qd=(u_{1}a+v_{1}b)-q(u_{2}a+v_{2}b)=(u_{1}-qu_{2})a+(v_{1}-qv_{2})b=u'a+v'b$

但是，由於 $r<d$ 且 *d* 是 S 的最小元素，這是不可能的。唯一另一種可能性是 *r=0*。因此，S 中的任何元素 *t* 都可以被 *d* 整除。由於這包括 *a* 和 *b*，因此 *d* 是一個公約數。將此結果與先前的結果結合起來，就建立了貝祖等式。

*u* 和 *v* 的值可以使用表格方法或歐幾里得演算法中的回代法獲得。

算術基本定理的證明

貝祖等式的一個應用是在證明算術基本定理時。在證明這一點之前，還需要另外兩個結果：引理 1：如果一個素數 *p* 整除兩個整數的乘積 $ab$，那麼它必須整除 *a* 或 *b*（或兩者）。

證明：如果 *p* 同時整除 *a* 和 *b*，則無需證明。假設 *p* 不整除 *a*。如果可以在該假設下證明 *p* 整除 *b*，則引理將被證明。

由於 *p* 不整除 *a*，因此 *gcd(a,p)*=1（因為 *p* 的唯一約數是 1 和 *p*，但 *p* 不是公約數）。因此，根據貝祖等式，存在整數 *u* 和 *v* 使得

$1=ua+vp$

將此方程乘以 *b* 可得

$b=uab+vbp$

*p* 整除右手邊的兩項，因此也整除左手邊。因此，*p* 整除 *b*，如需證明的那樣。

引理 2：如果一個素數 *p* 除以一個整數的乘積，$a_{1}a_{2}...a_{n}$，那麼它一定至少除以其中一個因子。

證明：該證明是透過對因子數量 *n* 進行 歸納法。對於 n=2，該陳述根據引理 1 為真。假設該陳述對 *n=k* 為真，並考慮 *k* + 1 個因子的乘積。如果 *p* 除以多個因子，那麼就沒有什麼需要證明的。假設 *p* 不除以任何因子 $a_{1},a_{2},...a_{k}$。將證明 *p* 必須除以 $a_{k+1}$。由於該陳述對 n=k 為真，那麼由於 *p* 不除以 $a_{1}a_{2}...a_{k}$ 中的任何因子，它一定不除以該乘積（根據 逆否命題）。令 $a_{1}a_{2}...a_{k}=b$。那麼 $a_{1}a_{2}...a_{k}a_{k+1}=ba_{k+1}$。然後，結論根據引理 1 得出。

算術基本定理：任何正整數 *n* 都可以表示為素數的乘積。該乘積除了項的順序外是唯一的。

證明：該定理第一部分的證明是透過對 *n* 進行歸納法。如果 *n*=1，它是 0 個素數的乘積。假設所有小於 *n* 的正整數都可以表示為素數的乘積。如果 *n* 是素數，那麼它是 1 個素數的乘積。假設 *n* 不是素數或 1。那麼 $n=ab$，其中 *a* 和 *b* 是兩個小於 *n* 的正整數。由於 *a* 和 *b* 都小於 *n*，根據歸納假設，它們可以寫成素數的乘積。組合這些乘積可以得到 *n* 作為素數的乘積，如所要求的那樣。

現在證明第二部分。假設 *n* 有兩個素數分解，

$n=p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{s}$

$p_{1}$ 除以左側，因此也必須除以右側。根據引理 2，這意味著 $p_{1}$ 必須除以其中一個 $q_{i}$。但這些都是素數，所以 $p_{1}$ 能除以 $q_{i}$ 的唯一途徑是，如果對於某個 *i*，有 $p_{1}=q_{i}$。在等式兩邊消去 $p_{1}$ 會形成另一個相同形式的等式。因此，可以同樣證明，對於其他一些 *i*，$p_{2}=q_{i}$，以此類推，直到左側的所有因子都被消去。在此之後，右側一定沒有任何剩餘的因子，因為它必須等於 1。這證明了任何兩個素數分解都包含相同的素數因子，正如要證明的那樣。

劃分乘積的除數

算術基本定理也可以從以下引理推匯出來

引理： 給定整數 $a$，$b$ 和 $c$，如果 $c$ 整除 $ab$（記為 $c|ab$），則存在整數 $m$ 和 $n$ 使得 $c=mn$ 且 $m|a$ 和 $n|b$。

換句話說，整除一個乘積的整數本身可以分解成一個乘積，其中每個因子都整除來自 $ab$ 的對應因子。這意味著當 $a$ 和 $b$ 相乘時，不會產生新的素數。

該引理由算術基本定理和貝祖等式得出，但這裡將給出更直接的證明。

證明：如果 $a$，$b$，或 $c$ 等於 $0$，則該引理是顯然的。此外，如果 $a$，$b$，或 $c$ 為負數，則如果該引理對於絕對值 $|a|$，$|b|$，和 $|c|$ 成立，則很容易證明該引理對於 $a$，$b$，和 $c$ 也成立。現在假設 $a$，$b$，和 $c$ 都是嚴格的正整數。

形成一個包含 $a\times b$ 個元素的整數陣列 $S$，它有 $a$ 列和 $b$ 行。 $s_{(x,y)}$ 將表示第 $x$ 列第 $y$ 行的整數。 透過按行掃描陣列，從第 1 行開始，每行從第 1 列開始，依次對陣列 $S$ 進行“光柵”掃描，使用以下迴圈模式來分配值給 $s_{(x,y)}$：$1,2,...,c$。實質上，$s_{(x,y)}$ 是來自範圍 $\{1,2,\dots ,c\}$ 中唯一的整數，滿足 $s_{(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。由於 $c|ab$，因此 $s_{(1,1)}=1$ 且 $s_{(a,b)}=c$。

如前所述，陣列 $S$ 的“光柵掃描”是 $S$ 中元素的迴圈遍歷，其中列索引 $x$ 在 $1,2,...,a$ 中迴圈，每次 $x$ 從 $a$ 轉變為 $1$ 時，行索引 $y$ 在迴圈 $1,2,...,b$ 中前進一步。

在下圖中，網格 $S$，其中 $a=14$；$b=15$；和 $c=6$，被明確地和使用磚塊圖案來描繪。

陣列 $S$ 可以無限複製並用來形成無限陣列 $S_{\infty }$。對於任意整數 $u$ 和 $v$，$S_{\infty }$ 中由第 $a(u-1)+1$ 列到第 $a(u-1)+a$ 列，第 $(b(v-1)-(u-1))+1$ 行到第 $(b(v-1)-(u-1))+b$ 行的條目塊是 $S$ 的副本。對於任意整數 $x$ 和 $y$，$S_{\infty }$ 中的條目 $s_{\infty ,(x,y)}$ 是範圍 $\{1,2,\dots ,c\}$ 中唯一的整數，使得 $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。

陣列 S 的表示圖，其中 a = 14；b = 15；c = 6。(1,1) 條目是左下角。

用磚石圖案表示的陣列 S，其中 a = 14；b = 15；c = 6。每個“磚石”是序列 1、2、3、4、5、6。

表示 $S$ 的多個磚石圖案可以拼接在一起，形成一個連續的牆，表示 $S_{\infty }$。

給定任意列 $x$ 和行 $y$，$S_{\infty }$ 中位於 $(x,y)$ 的元素 $s_{\infty ,(x,y)}$ 是 $\{1,2,...,c\}$ 中唯一的整數，使得 $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。給定任意位移列位移 $\Delta x$ 和行位移 $\Delta y$，差值 $s_{\infty ,(x+\Delta x,y+\Delta y)}-s_{\infty ,(x,y)}$ 與 $\Delta x+a\Delta y$ 之差為 $c$ 的倍數。這使得 $S_{\infty }$ 的元素具有以下對稱性

• 給定列位移 $\Delta x$ 和列 $x_{1},x_{2}$，以及行位移 $\Delta y$ 和行 $y_{1},y_{2}$，則 $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}\equiv s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}\;\;({\text{mod}}\;c)$。具體來說，如果 $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}=0$，則 $s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}=0$，因為 $S_{\infty }$ 中任意兩個元素之間的差值限制在集合 $\{-(c-1),-(c-2),...,-1,0,1,...,c-1\}$ 中。
• 給定列 $x_{1},x_{2}$，和行 $y_{1},y_{2}$，如果 $s_{\infty ,(x_{1},y_{1})}=s_{\infty ,(x_{2},y_{2})}$，那麼將 $S_{\infty }$ 向右平移 $x_{2}-x_{1}$ 列和向下平移 $y_{2}-y_{1}$ 行不會改變 $S_{\infty }$ 的元素。

由於上述對稱性，$S_{\infty }$ 中包含 $1$ 的列是等間距的。令 $m$ 表示最小的正整數，使得每隔 $m^{\text{th}}$ 列都包含 $1$。

• 元素 $s_{\infty ,(1,1)}=1$ 和 $s_{\infty ,(a+1,b)}=1$，因此必須有 $a$ 是週期 $m$ 的整數倍：$m|a$。
• 條目 $s_{\infty ,(1,1)}=1$ 和 $s_{\infty ,(c+1,1)}=1$，因此必須是 $c$ 是週期 $m$ 的整數倍數： $m|c$。

的 $S_{\infty }$ 行最終將重複（不允許任何列移動），週期為 $n$。由於 $S_{\infty }$ 的對稱性，一行在一個週期內不會出現兩次。第 $1$ 行與第 $b+1$ 行相同，因此必須是 $b$ 是週期 $n$ 的整數倍數： $n|b$。

當 a=14; b=15; 且 c=6 時，m=2 且 n=3。任何 2x3 細胞將包含所有 {1, 2, 3, 4, 5, 6}，從而實現所描述的拼貼。

現在將證明 $c=mn$，方法是展示 $S_{\infty }$ 的一個子塊，該子塊包含 $m$ 列和 $n$ 行，包含從 $\{1,2,...,c\}$ 中的每個整數恰好一次。

為了澄清符號，假設列索引為 $x_{1},x_{2}$，其中 $x_{1}\leq x_{2}$，而行索引為 $y_{1},y_{2}$，其中 $y_{1}\leq y_{2}$，則 $S_{\infty }([x_{1},x_{2}]\times [y_{1},y_{2}])$ 表示 $S_{\infty }$ 的子塊，包含從列 $x_{1}$ 到 $x_{2}$ 的所有列，以及從行 $y_{1}$ 到 $y_{2}$ 的所有行。

由於一行可以從單個單元格唯一確定，並且行僅以 $n$ 為週期重複，任何塊 $S_{\infty }([x,x]\times [y,y+(n-1)])$ 將包含恰好 $n$ 個唯一條目。

包含 $1$ 的列以週期為 $m$ 出現。由於 $S_{\infty }$ 的對稱性，對於任何整數 $s\in \{1,2,...,c\}$，包含 $s$ 的列以週期為 $m$ 出現。任何塊 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 將正好包含 $mn$ 個唯一條目。

給定任何整數 $s\in \{1,2,...,c\}$，整數 $s$ 將出現在每一 $m^{\text{th}}$ 列，並在該列中，出現在每一 $n^{\text{th}}$ 個單元格。任何塊 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 將包含 $s$。任何塊 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 將包含從 $\{1,2,...,c\}$ 中的每個整數正好一次。所以，因此 $c=mn$。 $\Box$.

解線性模方程 - 回到貝祖定理

上面的貝祖恆等式為我們提供了求解以下形式方程的關鍵

ax ≡ b (mod m)

互質的情況 - gcd(a, m) 為 1

考慮以下情況

ax ≡ b (mod m)

但 gcd(a, m)=1

由於貝祖恆等式

1 = au+mv

當我們計算u時，這個數字很特別。

假設我們有以下方程

4x=11 (mod 21)

4 和 21 互質，因為 gcd(4,21)=1。現在 1=4*16+(-3)*(21)。在這種情況下，我們的u 是 16。現在觀察 4*16=64。64 (mod 21) = 1。這個數字u 非常特殊 - 它被稱為乘法逆。它是u，在與a 相乘後得到 1 mod m。在計算 gcd(a, m) 時，貝祖恆等式將始終給出a 模m 的乘法逆。a 的乘法逆通常寫為a^-1，但請注意，這並不表示 1/a，因為我們在第一節中已經看到，我們不能總是在整數中進行除法。

請注意，在 Z_p 中，有一個數字沒有乘法逆 - 0。在考慮模運算時，排除 0 可能很有用，因此，為了避免總是說 Z_p\{0}，我們只需寫 Z_p^*。

現在，由於我們有了神奇的乘法逆，我們的問題就變得相對容易解決了。在 Z₂₁ 中，4^-1=16，現在，在整個方程兩邊乘以 16

x = 11 × 16 (mod 21)

（因為 4×16=1，因為 16 是 4 模 21 的乘法逆）。11×16=176，使用計算器或使用除法定理，我們得到

x = 8 (mod 21)

這就是我們的解！驗證 - 8×4 = 32 = 11 (mod 21)。

一般情況

考慮以下一般情況

ax ≡ b (mod m)

對a、b 和m 沒有限制。

首先，我們再次計算 gcd(a, m) 以得到d。現在d 是一個除數，因為 gcd 中的d 表示最大公約數。所以我們現在可以除a 和m - 但b 呢？由於我們計算了a 和m 的 gcd，但沒有計算b，因此我們不能保證d 能整除b。這就會成為方程沒有解的條件。

現在我們已經將問題簡化為之前互質的情況，因為 gcd(a/d, m/d)=1，其中d 如上所示。但是我們不再只有一個解了 - 這是因為我們已經將解簡化為x = c (mod m/d)，並且我們必須將解還原為 mod m。這在示例中會更加清楚。

讓我們來看一些示例。

示例 1. 求解 4x ≡ 3 (mod 20)。首先，gcd(4, 20) = 4。4 不能整除 3，因此沒有解。

示例 2. 求解 9x ≡ 6 (mod 15)。gcd(9, 15) = 3，並且 3 能整除 6，因此有 3 個解。

現在，將整個方程除以 3，得到

3x ≡ 2 (mod 5)

gcd(3, 5) = 1 = 3 × 2 + -1 × 5 因此 3 模 5 的逆是 2。現在我們得到解

x ≡ 4 (mod 5)

現在在 Z₁₅ 中，我們必須得到另外兩個解 9 和 14 模 15 - 9 模 5 = 4，並且 14 模 5 = 4。

通常，我們可以說，如果我們得到了約簡方程的解x，則一般解為x+(m/d)k，其中k={0, 1, .., d-1}。

中國剩餘定理

通常需要同時滿足多個同餘關係。給定正整數底數 $m_{1}$ 和 $m_{2}$ 以及任意整數 $a$ 和 $b$，其中 $0\leq a<m_{1}$ 且 $0\leq b<m_{2}$，一個常見的問題是哪些整數 $x$ 同時滿足以下同餘關係：

$\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$

中國剩餘定理指出，當 ${\text{gcd}}(m_{1},m_{2})=1$ 時，對於任何 $a\in \mathbb {Z} _{m_{1}}=\{0,1,...,m_{1}-1\}$ 和 $b\in \mathbb {Z} _{m_{2}}=\{0,1,...,m_{2}-1\}$ 的選擇，存在唯一的整數 $c\in \mathbb {Z} _{m_{1}m_{2}}=\{0,1,...,m_{1}m_{2}-1\}$ 使得

同時滿足 $\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$ 的所有整數 $x$ 是那些同時滿足 $x\equiv c\;\;({\text{mod}}\;m_{1}m_{2})$ 的整數。

實質上，當 $m_{1}$ 和 $m_{2}$ 互質時，$\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 中的有序對與集合 $\mathbb {Z} _{m_{1}m_{2}}$ 之間存在一一對應關係。

證明 1

證明： 首先觀察到 $|\mathbb {Z} _{m_{1}m_{2}}|=m_{1}m_{2}$ 且 $|\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}|=|\mathbb {Z} _{m_{1}}||\mathbb {Z} _{m_{2}}|=m_{1}m_{2}$，因此可以將每個 $c\in \mathbb {Z} _{m_{1}m_{2}}$ 與一個唯一的有序對 $\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 配對，反之亦然。

給定任意$c\in \mathbb {Z} _{m_{1}m_{2}}$，整數$c$ 可以被 $m_{1}$ 取模，得到一個整數$a\in \mathbb {Z} _{m_{1}}$，也可以被$b$ 取模，得到一個整數$b\in \mathbb {Z} _{m_{2}}$。整數$a$ 和$b$ 滿足：$\forall x\in \mathbb {Z} :(x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))\implies ((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))$

對於任意$\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 的選擇，是否存在唯一的$c\in \mathbb {Z} _{m_{1}m_{2}}$ 使得$\forall x\in \mathbb {Z} :((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))\iff (x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))$，這一點並不明顯。

令 $S$ 表示一個無限陣列，它有兩行，由 $y=1,2$ 索引，以及無限列，由 $x\in \mathbb {Z}$ 索引。 $s_{(x,y)}$ 將表示 $S$ 中第 $x$ 列和第 $y$ 行的條目。 $s_{(x,y)}$ 是從 $\mathbb {Z} _{y}=\{0,1,...,m_{y}-1\}$ 中唯一的整數，其中 $s_{(x,y)}\equiv x\;\;({\text{mod}}\;m_{y})$。

陣列 $S$ 其中 $m_{1}=6$ 且 $m_{2}=5$。列 $x=0$ 到 $x=29$ 如圖所示。

給定列索引 $x_{1},x_{2}$，其中 $x_{1}\leq x_{2}$，則 $S_{1}[x_{1},x_{2}];S_{2}[x_{1},x_{2}];S_{1,2}[x_{1},x_{2}]$ 將分別表示由列 $x_{1}$ 到 $x_{2}$ 和行集 $\{1\};\{2\};\{1,2\}$ 形成的子塊。

將 $S$ 分成一系列 $m_{1}\times 2$ 塊 $...,S_{1,2}[-2m_{1},-m_{1}-1],S_{1,2}[-m_{1},-1],S_{1,2}[0,m_{1}-1],S_{1,2}[m_{1},2m_{1}-1],S_{1,2}[2m_{1},3m_{1}-1],...$，其中塊 $k\in \mathbb {Z}$ 是 $S_{1,2}[km_{1},(k+1)m_{1}-1]$。

塊 $k$ 的第 1 行始終為序列 $0,1,...,m_{1}-1$。塊 $k$ 的第 2 行可以由其第一個元素 $s_{(km_{1},2)}$ 唯一確定，因為 $s_{(km_{1}+r,2)}\equiv s_{(km_{1},2)}+r\;\;({\text{mod}}\;m_{2})$。這些塊僅在第 2 行不同，而每個塊的第 2 行由其第一個元素 $s_{(km_{1},2)}$ 唯一確定。

$s_{(km_{1},2)}\equiv km_{1}\;\;({\text{mod}}\;m_{2})$ 且 $s_{((k+1)m_{1},2)}\equiv (k+1)m_{1}\;\;({\text{mod}}\;m_{2})$，因此 $s_{((k+1)m_{1},2)}\equiv s_{(km_{1},2)}+m_{1}\;\;({\text{mod}}\;m_{2})$。這意味著下一個塊的第 2 行的第一個元素可以從當前塊的第 2 行的第一個元素唯一確定。

Since each block is uniquely determined from the previous block, the row 2 pattern for each block will repeat after a regular period of $p$ blocks: $S_{1,2}[km_{1},(k+1)m_{1}-1]=S_{1,2}[(k+p)m_{1},(k+p+1)m_{1}-1]$. Let set $U\subseteq \mathbb {Z} _{m_{2}}$ denote the total range of values attained by $s_{(km_{1},2)}$. It is the case that $p=|U|$. Let $d$ be the minimum positive difference between any two elements from $U$. The cyclical nature of the elements from $U$ makes it easy to show that any element $t\in U$ is congruent to a multiple of $d$ modulo $m_{2}$. In essence: $U=\{t|t\in \mathbb {Z} _{m_{2}}\;{\text{and}}\;\exists u\in \mathbb {Z} :t\equiv ud\;\;({\text{mod}}\;m_{2})\}$. Since $d$ is the minimum positive difference between any two elements of $U$, both $m_{1}$ and $m_{2}$ are multiples of $d$ (in fact, $m_{2}=pd$). Since ${\text{gcd}}(m_{1},m_{2})=1$, it must be the case that $d=1$. This implies that $U=\mathbb {Z} _{m_{2}}$ and that $p=m_{2}$. A total of $m_{2}$ blocks are encountered before any repetition occurs in array $S$, and therefore all $m_{1}m_{2}$ possible columns occur exactly once in a column period of $m_{1}m_{2}$ in array $S$. This establishes the Chinese Remainder Theorem. $\Box$

證明 2

可以透過構建網格來描述空間 $\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$，從而得到另一個（更直觀的）證明。該網格是一個矩形點陣，有 $m_{1}$ 列和 $m_{2}$ 行。列從左到右按 $0,1,2,...,m_{1}-1$ 索引，行從下到上按 $0,1,2,...,m_{2}-1$ 索引。最重要的是，網格將在水平和垂直方向上“環繞”。這意味著從列 $m_{1}-1$ 向右移動將返回到列 $0$；從列 $0$ 向左移動將把你送到列 $m_{1}-1$；從行 $m_{2}-1$ 向上移動將返回到行 $0$；從行 $0$ 向下移動將把你送到行 $m_{2}-1$。

The mesh has $m_{1}m_{2}$ points, and the horizontal and vertical coordinates of each point are the remainders from dividing an integer $x$ by $m_{1}$ and $m_{2}$ respectively. For convenience, given an arbitrary dividend $x$, $x\;{\text{mod}}\;m_{1}$ and $x\;{\text{mod}}\;m_{2}$ will denote the remainders after $x$ is divided by $m_{1}$ and $m_{2}$ respectively. If the dividend $x$ is incremented by $1$, then the coordinate formed by the remainders moves to the right by one step, and up by one step, wrapping around if necessary. $x=0$ corresponds to the coordinate $(0,0)$. Increasing $x$ in steps of $1$ will trace a ray that originates from $(0,0)$ and moves one step to the right and one step up each interation, wrapping around if necessary. The images below give examples of this ray for $m_{1}=6;m_{2}=5$ and for $m_{1}=6;m_{2}=4$. In the images below, a copy of column 0 and row 0 appears at the right and top of the mesh respectively to illustrate the wrap around property. When $m_{1}=6;m_{2}=4$, $m_{1}$ and $m_{2}$ are not coprime and fail to satisfy the conditions of the Chinese remainder theorem.

展示了一個水平方向每 6 步環繞，垂直方向每 5 步環繞的網格。該網格描述了分別除以 6 和 5 後得到的餘數對的集合。網格外部的數字表示水平和垂直座標，即分別除以 6 和 5 後的餘數。從 (0,0) 開始，發出一條射線（用紅線表示），它在水平和垂直方向上重複向前移動 1 步。該射線表示隨著被除數以 1 步遞增，餘數對的序列。每個紅色條帶上的數字索引射線的每次環繞。射線穿過網格上的每個點，表明任何餘數對都是可能的，這與中國剩餘定理的預測一致。

展示了一個水平方向每 6 步環繞，垂直方向每 4 步環繞的網格。該網格描述了分別除以 6 和 4 後得到的餘數對的集合。網格外部的數字表示水平和垂直座標，即分別除以 6 和 4 後的餘數。從 (0,0) 開始，發出一條射線（用紅線表示），它在水平和垂直方向上重複向前移動 1 步。該射線表示隨著被除數以 1 步遞增，餘數對的序列。每個紅色條帶上的數字索引射線的每次環繞。射線未能穿過網格上的每個點，因為 6 和 4 不是互質的。這與中國剩餘定理相一致。

射線在網格中形成對角線“條紋”，如果這些條紋都等距地由$1$間隔，那麼射線會精確地穿過網格中的每個點一次，證明每對餘數都是可能的，因此中國剩餘定理成立。當$m_{1}=6;m_{2}=4$時，$m_{1}$ 和 $m_{2}$ 不是互質的，並且不滿足中國剩餘定理的條件，因此射線不會擊中網格上的每個點。網格的環繞性質使得網格在水平和垂直方向上都“對稱”，這意味著如果將環繞的“接縫”移動到射線穿過左下角的任何列和行，則射線將完全保持不變。這要求條紋等距。令$d$表示這種等距，並且將證明$d|m_{1}$ 和 $d|m_{2}$。射線每向右移動$d$步就會穿過第$0$行。射線穿過$(0,0)$，並且環繞性質意味著向右移動$m_{1}$步會返回到這個相同的交點。這隻能在$d|m_{1}$時發生。用類似的論證可得$d|m_{2}$。如果$m_{1}$ 和 $m_{2}$ 是互質的，那麼 $d=1$，條紋等距地由$1$間隔，每對餘數都是可能的，因此中國剩餘定理成立。 $\Box$