离散数学/模运算

介绍

我们已经在数论中考虑过模和模运算，但是在这个部分我们将更深入地了解模运算。

为了复习，如果您选择的话，您应该回顾数论中的内容。

联立方程

当我们谈到与模运算相关的联立方程时，我们指的是以下形式的一组方程的联立解

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