MATH Day 02 Applications Practice

阶与指数方程 (Order and Exponential Equations)

前提条件： 设 \(m\) 为正整数，且模 \(m\) 的乘法群 \(\mathbb{Z}_m^\times\) 是循环群（即 \(m\) 存在原根）。

命题：
设 \(\gcd(a, m) = 1\)，记 \(d = \operatorname{ord}_m(a)\) 为 \(a\) 模 \(m\) 的阶。对于指数方程：

\[a^x \equiv b \pmod m \]

1. 存在性判别： 该方程有解当且仅当：

   \[b^d \equiv 1 \pmod m \]

   这等价于 \(b\) 属于由 \(a\) 生成的循环子群，即 \(b \in \langle a \rangle\)。

2. 解的结构： 若 \(x_0\) 是该方程的一个特解，则该方程的所有整数解可表示为：

   \[x \equiv x_0 \pmod d \]

---

数论习题集：升幂定理与原根

1. 计算 \(v_5(3^{100} - 1)\)

分析： 我们寻找 \(3\) 模 \(5\) 的阶。
显然 \(3^1 \equiv 3, 3^2 \equiv 4, 3^3 \equiv 2, 3^4 \equiv 1 \pmod 5\)，故 \(\text{ord}_5(3) = 4\)。
因为 \(4 \mid 100\)，我们可以应用 LTE 定理。

解：

\[v_5(3^{100} - 1) = v_5((3^4)^{25} - 1) \]

由于 \(5 \mid (3^4 - 1)\) 且 \(5 \nmid 25\)（注：此处应为 \(5 \mid 25\)），应用 LTE 定理：

\[v_5((3^4)^{25} - 1) = v_5(3^4 - 1) + v_5(25) \]

计算项：

• \(3^4 - 1 = 81 - 1 = 80 = 5^1 \times 16\)，故 \(v_5(3^4 - 1) = 1\)。
• \(v_5(25) = 2\)。

\[\therefore v_5(3^{100} - 1) = 1 + 2 = 3 \]

---

2. 计算 \(v_7(2^{1000} + 1)\)

分析： 注意 LTE 的加法形式 \(v_p(a^n + b^n)\) 要求 \(n\) 为奇数。此处 \(1000\) 为偶数，LTE 失效。

解：
考查 \(2\) 模 \(7\) 的幂次循环：

• \(2^1 \equiv 2 \pmod 7\)
• \(2^2 \equiv 4 \pmod 7\)
• \(2^3 \equiv 1 \pmod 7\)
  由于 \(1000 = 333 \times 3 + 1\)，则：

\[2^{1000} \equiv (2^3)^{333} \cdot 2^1 \equiv 1^{333} \cdot 2 \equiv 2 \pmod 7 \]

因此：

\[2^{1000} + 1 \equiv 2 + 1 \equiv 3 \pmod 7 \]

因为 \(2^{1000} + 1\) 不能被 \(7\) 整除，所以：

\[v_7(2^{1000} + 1) = 0 \]

---

3. 证明：\(\forall n \geq 1, v_3(2^{3^n} + 1) = n + 1\)

证明：
使用 LTE 定理的加法形式。条件检查：

• \(p = 3\) 是奇素数。
• \(3 \mid (2 + 1)\)。
• 指数 \(3^n\) 是奇数。

直接应用 LTE：

\[v_3(2^{3^n} + 1) = v_3(2 + 1) + v_3(3^n) = v_3(3) + n = 1 + n \]

证毕。

---

4. 证明：若 \(p \mid a-b\)，则 \(v_p(a^p - b^p) \geq v_p(a-b) + 1\)，并说明取等条件。

证明：
设 \(S = \frac{a^p - b^p}{a-b} = a^{p-1} + a^{p-2}b + \dots + b^{p-1}\)。
若 \(p \mid a-b\)，则 \(a \equiv b \pmod p\)。

• Case 1: \(p\) 为奇素数
  由 LTE 定理知：\(v_p(a^p - b^p) = v_p(a-b) + v_p(p) = v_p(a-b) + 1\)。
  此时等号恒成立。

• Case 2: \(p = 2\)
  \(a^2 - b^2 = (a-b)(a+b)\)。
  \(v_2(a^2 - b^2) = v_2(a-b) + v_2(a+b)\)。
  欲使 \(v_2(a^2 - b^2) \geq v_2(a-b) + 1\)，只需 \(v_2(a+b) \geq 1\)，即 \(2 \mid a+b\)。
  由于 \(2 \mid a-b\)，这总是成立的。

取等条件：

1. \(p\) 为奇素数；
2. 若 \(p=2\)，则要求 \(v_2(a+b) = 1\)，即 \(a+b \equiv 2 \pmod 4\)。

---

5. 求 \(\text{ord}_{13}(2)\)

解：
计算 \(2^k \pmod{13}\)：
\(2^1=2, 2^2=4, 2^3=8, 2^4=16 \equiv 3, 2^5 \equiv 6, 2^6 \equiv 12 \equiv -1 \pmod{13}\)。
既然 \(2^6 \equiv -1 \pmod{13}\)，则 \(2^{12} \equiv 1 \pmod{13}\)。
由于阶必须整除 \(\phi(13)=12\)，可能的阶为 \(1, 2, 3, 4, 6, 12\)。经检验，最小的 \(k\) 为 \(12\)。

\[\therefore \text{ord}_{13}(2) = 12 \]

(这也说明 \(2\) 是模 \(13\) 的一个原根)。

---

6. 证明：若 \(\text{ord}_p(a) = p-1\)，则 \(a\) 是模 \(p\) 的原根。

证明：
根据原根的定义：若一个整数 \(a\) 模 \(m\) 的阶等于 \(\phi(m)\)，则称 \(a\) 为模 \(m\) 的原根。
此处 \(m=p\) 为素数，\(\phi(p) = p-1\)。
既然题目给定 \(\text{ord}_p(a) = p-1 = \phi(p)\)，根据定义，\(a\) 显然是模 \(p\) 的原根。
在群论视角下，\(\mathbb{Z}_p^*\) 是一个 \(p-1\) 阶的循环群，\(a\) 是该群的一个生成元。

---

7. 设 \(p\) 是奇素数，\(\text{ord}_p(a) = d\)。证明：\(\text{ord}_{p^2}(a) = d\) 或 \(pd\)。

证明：
令 \(q = \text{ord}_{p^2}(a)\)。

1. 由 \(a^q \equiv 1 \pmod{p^2} \implies a^q \equiv 1 \pmod p\)。根据阶的性质，有 \(d \mid q\)。
2. 由费马小定理及欧拉定理可知 \(q \mid \phi(p^2) = p(p-1)\)。
3. 结合 \(d \mid p-1\)（由 \(\text{ord}_p(a)=d\) 得出），可知 \(q\) 的形式必然是 \(d\) 或 \(pd\)。

另一种论证：
考虑 \(v_p(a^q - 1)\)。由 LTE 定理，若 \(d \mid q\)，设 \(q = m \cdot d\)：

\[v_p(a^{md} - 1) = v_p(a^d - 1) + v_p(m) \]

我们要求 \(a^q \equiv 1 \pmod{p^2}\)，即 \(v_p(a^q - 1) \geq 2\)。

• 若 \(v_p(a^d - 1) \geq 2\)，则 \(a^d \equiv 1 \pmod{p^2}\)，此时 \(q=d\)。
• 若 \(v_p(a^d - 1) = 1\)，则必须有 \(v_p(m) \geq 1\)，最小的 \(m\) 为 \(p\)，此时 \(q=pd\)。

综上所述，\(\text{ord}_{p^2}(a) \in \{d, pd\}\)。