離散數學/數論

介紹

'數論'本身就是一個龐大而全面的學科。在這裡，我們將考察數論的關鍵概念。

與處理實數稠密集的實分析和微積分不同，數論考察了離散集中的數學，例如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 的元素。

我們可以透過使用除數定理找到 a 模 n（或者說 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)$.

進位制

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

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

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

也有大於 10 的進位制。對於這些進位制，通常使用字母來表示大於 10 的數字。例如，十六進位制 (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 是素數，因為唯一能被 17 整除的正整數是 1 和 17。數字 6 不是素數，因為除了 1、2、3、6 以外，還有其他除數能被 6 整除。另外，請注意，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 中的任何一個數字整除。考慮一下如果你嘗試用 p₁、p₂、...、p_n 列表中的任何素數來除 M 會發生什麼。從 M 的定義中，你可以知道你會得到餘數 1。這意味著 p——能夠整除 M 的素數——必須大於 p₁、...、p_n 中的任何一個。

因此，我們已經證明 M 可以被一個素數 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 的冪是 1，而在數字 450 中，質因數 11 的冪是 0。由於質因數 11 的冪 1 和 0 中的最大值為 1，我們使用 1 作為最後一個質因數 11 的冪。

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

GCD

兩個數字 a 和 b 的最大公約數是能同時整除數字 a 和數字 b 的最大數字，用 GCD(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)

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

44 = 18 × k + r

44 = 18 × 2 + 8

重複此過程；不斷用前一個餘數除以前一個除數

18 = 8 × 2 + 2

8 = 2 × 4 + 0

我們的 gcd 是最後一個餘數，在零之前，在本例中為 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}$中的任何因子，因此p不能整除該乘積（根據逆否命題）。令$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$，對於一些小於n的正整數a和b。由於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}$ 的唯一方法是當 $p_{1}=q_{i}$ 對於某些 i 成立。將方程兩邊的 $p_{1}$ 消去，得到另一個相同形式的方程。因此，同樣可以證明 $p_{2}=q_{i}$ 對於其他 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 非常特殊 - 它被稱為乘法逆元。它是乘以a 後得到模m 為 1 的數字u。計算 gcd(a, m) 的貝祖恆等式總是會給你a 模m 的乘法逆元。a 的乘法逆元通常寫成a^-1，但請注意這不代表 1/a，因為我們在第一部分已經看到，我們不能總是在整數中進行除法。

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

現在，由於我們有了神奇的乘法逆元，我們的問題就變得相對容易解決了。4^-1=16 在Z₂₁ 中，現在，在整個等式兩邊乘以 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)，我們必須將解還原為模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$ 的第一行始終是序列 $0,1,...,m_{1}-1$。塊 $k$ 的第二行可以透過其第一個元素 $s_{(km_{1},2)}$ 唯一確定，因為 $s_{(km_{1}+r,2)}\equiv s_{(km_{1},2)}+r\;\;({\text{mod}}\;m_{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})$。這意味著下一個塊的第二行的第一個元素可以由當前塊的第二行的第一個元素唯一確定。

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$