離散數學/模運算

介紹

我們已經在數論中考慮過模和模運算，但是在這個部分我們將更深入地瞭解模運算。

為了複習，如果您選擇的話，您應該回顧數論中的內容。

聯立方程

當我們談到與模運算相關的聯立方程時，我們指的是以下形式的一組方程的聯立解

x ≡ a₁ (mod m₁)

:

:

x ≡ a_k (mod m_k)

我們將考慮兩種主要方法，逐次替換和中國剩餘定理。

逐次替換

逐次替換法是指我們利用模的定義來重寫這些聯立方程，然後進行逐次替換。

用一個例子來激發這個想法可能會更好。

例：使用逐次替換法解 3x ≡ 10 (mod 19) 和 x ≡ 19 (mod 21)。

首先

3x ≡ 10 (mod 19)

在Z₁₉中找到3的逆元；3^-1=-6，然後

x ≡ -60 (mod 19)

x ≡ 16 (mod 19)

x = 16 + 19j ∃ j∈Z (*)

代入第二個方程

(16+19j) ≡ 19 (mod 21)

19j ≡ 3 (mod 21)

在Z₂₁中找到19的逆元；19^-1=10

j = 30 (mod 21)

j = 9 (mod 21)

寫成等價形式

j = 9 + 21k ∃ k∈Z

將j代回(*)

x = 16 + 19(9+21k)

x = 187+399k

寫回第一種形式

x ≡ 187 (mod 399)

這就是我們的解。

中國剩餘定理

中國剩餘定理是一種解聯立線性同餘方程的方法，當模數互素時。

給定方程

x ≡ a₁ (mod m₁)

:

:

x ≡ a_k (mod m_k)

將模數相乘，即 N=m₁m₂...m_k，然後寫 n₁=N/m₁， ..., n_k=N/m_k。

然後我們令 y_i 為 n_i 模 m_i 的逆元，對於所有的 i，所以 y_in_i=1 模 m_i。

我們的解將是

x ≡ a₁y₁n₁+...+a_ky_kn_k (mod N)

要理解為什麼這有效，請考慮 x 模 m_k 取什麼值。項 a_ky_kn_k 模 m_k 等於 a_k，因為 y_kn_k=1 模 m_k，並且所有項 a_jy_jn_j 模 m_k 等於零，因為當 $j\neq k$ m_k 是 n_j 的因數。

中國剩餘定理具有極大的實際應用，因為如果我們希望解出一個模 M 的方程，對於某個很大的 M，我們可以將其分解成模 p 的方程，其中 p 是 M 的每個素因數，並使用 CRT 獲得模 M 的解。

冪和根

本節討論的是模某個模數的數的冪。我們尋找計算

a^b (mod m)

的有效方法。如果我們嘗試用普通方法計算 - 透過計算a^b然後取模 - 這將花費大量時間。然而，模運算背後的某些理論允許我們使用一些捷徑。

我們將研究其中的一些以及相關的理論。

費馬小定理

費馬小定理使我們能夠了解a^b (mod m) 等於 1 的情況。這在反駁素數性方面有應用。

它指出

如果 p 是素數，且 gcd(a,p)=1，則在Z_p中

a^p-1=1。

例如，13¹⁰=1 在Z₁₁中。

本原元素

如果在Z_n中，我們可以將某些元素寫成某個元素的冪嗎？這在理論上是可能的。

讓我們看看Z₃。

2⁰=1

2¹=2

2²=1

元素{1,2}實際上構成：Z₃^*。

一般來說，我們有

如果p是素數，則存在一個元素g∈Z_p^*，使得Z_p^*中的每個元素都是g的冪。

階

我們可以用階的概念以不同的方式表達這個想法。我們將a ∈ Z_n^* 的階表示為最小的整數k，記為 O_n(a)，使得

a^k=1 在Z_n中。

例如，O_n(-1)=2 對於所有 n 除了 2，因為

(-1)²=1

除了 n = 2 時，因為在這個域中 -1 = 1 並且因此階為 1。

注意如果 gcd(a,n)≠1，也就是說，a ∉ Z_n^*，則階沒有定義。

階的性質

階滿足一些性質，其中第一個最初由拉格朗日證明

如果 p 是素數，gcd(a,p)=1，

• O_p(a) 整除 p-1
• a 是本原元素當且僅當 O_p(a)=p-1

階和尋找本原元素

根據以上事實，我們可以很容易地找到Z_p中p > 2 的本原元素。

利用以上事實，我們只需要檢查a^(p-1)/p_i=x_i 在Z_p中是否成立，對於所有的i，其中p_i是p-1的質因子。如果任何一個x_i等於1，則a不是本原元；如果所有x_i都不等於1，則a是本原元。

示例： 找到Z₁₁中的本原元。

嘗試2。p-1 = 10 = 2 . 5 檢查

2^10/2=2⁵=10

2^10/5=2²=4

兩者都不等於1，因此我們可以說2是Z₁₁中的本原元。

問題集

根據以上內容，回答以下問題。（偶數編號問題的答案在後面）

1. 4 在Z₁₃中是本原元嗎？
2. 5 在Z₂₃中是本原元嗎？
3. 找到Z₅中的一個本原元。
4. 找到Z₁₉中的一個本原元。

答案

2. 是：在Z₂₃中，(23-1)=2*11，並且5^22/11=2，5^22/2=22，然後5²²=1。沒有更小的基數能給出這個結果。

4. 2. 檢查：(19-1) 有不同的質因子 2 和 3。在Z₁₉中，2^18/2≠1 並且 2^18/3≠1，但 2¹⁸=1，所以 2 是本原元。

尤拉函式

尤拉函式是一個特殊的函式，它允許我們推廣上述費馬小定理。

它定義為

φ(n) = |Z_n^*|

=|{a∈Z|1 ≤ a ≤ n 並且 gcd(a,n) = 1}|

即在Z_n中具有逆元的元素的數量

一些結果

我們從前面的定義中得到以下結果。

1. φ(p) = p - 1
2. φ(p^k) = p^k-p^k-1
3. φ(mn)=φ(m)φ(n) 對於 gcd(m,n)=1
4. 對於任何整數 n，其每個因子的尤拉函式值的總和等於 n。

用符號表示： $\sum _{d\ divisor\ of\ n}\phi (d)=n$.

2 的證明： 在Z_p^k中有p^k個元素。Z_p^k中不可逆的元素是p的倍數，它們有p^k-1個：p，2p，3p，…，(p^k-1-1)p，p^k。從可逆元素中移除不可逆元素，剩下p^k-p^k-1個。 ∎

1、2 和 3 的推論： 如果n有不同的質因子（即不計算冪）p_i，對於 i=1,...,r，我們有

$\phi (n)=n\prod _{i=1}^{r}(1-{\frac {1}{p_{i}}})$

例如

16=2⁴，所以 φ(16)=(16)(1-1/2)=16/2=8

φ(11)=(11)(1-1/11)=(11)(10/11)=10

(從前面確認 11 是素數，所以 φ(11)=11-1=10).

3 的證明： 我們可以使用中國剩餘定理的一個特例來證明這個等式，其中中國剩餘定理現在只是一個包含兩個同餘式的系統，即

x == a₁ (mod m)

x == a₂ (mod n)

(記住，中國剩餘定理在這裡適用，因為 m 和 n 在等式中被假設為互質的)。

注意 a₁ 可以取 m 個值（從 0 到 m-1），a₂ 可以取 n 個值（從 0 到 n-1）。還要注意，對於每個 m*n 個 (a₁, a₂) 元組，都存在一個唯一的解 x，它嚴格小於 m*n。此外，對於每個嚴格小於 m*n 的 x，存在一個唯一的元組 (a₁, a₂) 驗證同餘式系統（這兩個斷言是中國剩餘定理的一部分：同餘式系統的解在模 m*n 下是唯一的）。

有了這個雙射唯一性屬性，證明就很簡單了。遍歷每個 x，從 0 到 m*n-1，並證明如果 x 是 m*n 的尤拉函式（即 gcd (x,m*n) = 1），則 a₁ 是 m 的尤拉函式，a₂ 是 n 的尤拉函式。此外，你還必須證明，如果 a₁ 和 a₂ 分別是 m 和 n 的尤拉函式，那麼 x 必須是 m*n 的尤拉函式。

如果 gcd (x,m*n) = 1，那麼根據貝祖等式，存在整數 X 和 Y 使得 x*X + m*n*Y = 1。此外，我們有

x = a₁ + k*m

x = a₂ + q*n

因此，a₁*X + m*(k + n*Y) = 1,
這應該是 a₁*X + m*(k*X + n*Y) = 1 ??
所以 gcd (a₁,m) = 1，因此 a₁ 是 m 的尤拉函式。類似地證明 a₂ 是 n 的尤拉函式。

證明另一個方向非常類似，它需要一些簡單的替換代數。

我們證明了什麼？在上面，我們證明了，對於 m*n 的每個尤拉函式 x，都存在一個唯一的元組，一個是 m 的尤拉函式，另一個是 n 的尤拉函式。此外，對於 m 的尤拉函式元組和 n 的尤拉函式元組，都存在一個唯一的 m*n 的尤拉函式。因此，phi(m*n) = phi(m)*phi(n)。

4 的證明： 令 Q(g) 是所有介於 1 和 n 之間（包括 1 和 n）的整數的集合，使得 gcd(x,n) = g。Q(g) 非空當且僅當 g 整除 n。如果 g 不整除 n，那麼就很難找到一個 x，使得 g 是 x 和 n 的最大公約數。其次，如果 x 屬於給定 g 的 Q(g)，那麼它就不可能屬於另一個 Q(...)，因為如果 n 固定，那麼根據最大公約數的定義，gcd(x,n) 是唯一的。第三，對於 1 和 n 之間的每個 x（包括 1 和 n），都存在一個 g 使得 gcd (x,n) = g（在 "最壞" 的情況下，它是 1）。把這三點放在一起，這些屬性意味著所有 Q(g) 集合（對於 n 的每個因數 g）的並集（它們是成對互斥的）是集合 {1,2,3,...,n}。因此，每個 Q(g) 的基數之和等於 n。

現在我們證明 |Q(g)| = φ(n/g)。

一個方向：設 x 是某個 g 的 Q(g) 中的任意成員。因此，我們有 gcd (x,n) = g => gcd (x/g, n/g) = 1 => x/g 屬於與 n/g 互質的數字集合（其基數當然是 φ(n/g)）。對於不同的 x，兩個值 x₁/g 和 x₂/g 是不同的。因此，對於 Q(g) 中的每個 x，都存在一個與之對應的唯一 x/g 屬於與 n/g 互質的數字集合。

另一個方向：設 x 是與 n/g 互質的數字集合中的任意成員。這意味著 gcd (x,n/g) = 1 => gcd (xg,n) = g => xg 屬於 Q(g)。對於不同的 x，兩個值 x₁g 和 x₂g 是不同的。因此，對於與 n/g 互質的數字集合中的每個 x，都存在一個與之對應的唯一 xg 屬於 Q(g)。

因此，|Q(g)| = φ(n/g)。

尤拉定理

現在我們可以推廣費馬定理，使其超越Z_n。

尤拉定理說

如果 a ∈ Z_n^*，在 Z_n^*中，

a^φ(n)=1

等價於如果 gcd(a,n)=1，

a^φ(n)≡1 (mod n)

示例： 找到Z₁₄中的 3²¹⁶。我們需要首先計算 φ(14)=φ(7)φ(2)=(7-1)(2-1)=6。然後將指數寫成：216 = 6 × 36 所以：3²¹⁶=(3⁶)³⁶

但尤拉定理告訴我們 3⁶=1 在 Z₁₄ 中（即，模 14），因為 3^φ(14)=1 在 Z₁₄ 中，如上所示。所以我們有：3²¹⁶=1³⁶=1。

有效地計算大冪

當尤拉定理或費馬定理在計算高次冪時對我們失效時，有一種方法可以將指數分解，以便計算仍然很容易。

讓我們透過一個例子來作為動機。

示例。 5²⁸ 在 Z₄ 中。

首先將 28 寫成二進位制 = (11100)₂ = 2⁴+2³+2² = 16 + 8 + 4

現在 5²⁸ = 5¹⁶⁺⁸⁺⁴ = 5¹⁶ 5⁸ 5⁴ 現在將這些 2 的冪重寫為重複的指數

(((5²)²)²)² × ((5²)²)² × (5²)²

當你計算每個指數時，每次都對 4 取模。

問題集

鑑於上述，計算以下冪。（偶數題答案如下）

1. 3¹² (mod 13)
2. 2⁴² (mod 43)
3. 6¹⁶⁸ (mod 30)
4. 2²⁵² (mod 19)
5. 2⁶¹ (mod 22)
6. 8¹³ (mod 5)
7. 11¹⁰ (mod 11) (棘手！)

答案

2. 由於 gcd(2,43)=1 且指數比模數小 1，使用費馬定理 - 答案是 1

4. 觀察 φ(19)=18 且 18|252。252/18=14。然後將指數分解為 2^18×14=(2¹⁸)¹⁴=1。

6. 使用快速平方求冪：答案是 3