1

写出模 $3,5,11,13,19$ 的指数表，并指出它们的所有原根。

解：

1. 模 3 的指数表

$(\mathbb{Z}/3\mathbb{Z})^*$ 的元素 $a$ 及其阶 $\operatorname{ord}_3(a)$ 如下：

$a=1$	$a=2$
$\operatorname{ord}_3(1)=1$	$\operatorname{ord}_3(2)=2$

原根: 2.

2. 模 5 的指数表

$(\mathbb{Z}/5\mathbb{Z})^*$ 的元素 $a$ 及其阶 $\operatorname{ord}_5(a)$ 如下：

$a=1$	$a=2$	$a=3$	$a=4$
$\operatorname{ord}_5(1)=1$	$\operatorname{ord}_5(2)=4$	$\operatorname{ord}_5(3)=4$	$\operatorname{ord}_5(4)=2$

原根: 2, 3.

3. 模 11 的指数表

$(\mathbb{Z}/11\mathbb{Z})^*$ 的元素 $a$ 及其阶 $\operatorname{ord}_{11}(a)$ 如下：

1	2	3	4	5	6	7	8	9	10
1	10	5	5	5	10	10	10	5	2

原根: 2, 6, 7, 8.

4. 模 13 的指数表

$(\mathbb{Z}/13\mathbb{Z})^*$ 的元素 $a$ 及其阶 $\operatorname{ord}_{13}(a)$ 如下：

1	2	3	4	5	6	7
1	12	3	6	4	12	12

8	9	10	11	12
4	3	6	12	2

原根: 2, 6, 7, 11.

5. 模 19 的指数表

$(\mathbb{Z}/19\mathbb{Z})^*$ 的元素 $a$ 及其阶 $\operatorname{ord}_{19}(a)$ 如下：

1	2	3	4	5	6	7	8	9
1	18	18	9	9	9	3	6	9

10	11	12	13	14	15	16	17	18
18	3	6	18	18	18	9	9	2

原根: 2, 3, 10, 13, 14, 15.

2

求 $\delta_{43}(7), \delta_{41}(10).$

解：$\delta_{43}(7) = 6$, $\delta_{41}(10) = 5$

3

设 $p$ 为素数，$n \geqslant 1,(n, p-1)=1$。证明：当 $x$ 通过模 $p$ 的完全系时，$x^n$ 亦通过模 $p$ 的完全系。

证明：

设 $f: (\mathbb{Z}/p\mathbb{Z})^* \longrightarrow (\mathbb{Z}/p\mathbb{Z})^*, \quad x \mapsto x^n$.

即证 $f$ 为双射.

取 $(\mathbb{Z}/p\mathbb{Z})^*$ 的一个原根 $g$, 则

$$f(g^k) = (g^k)^n = g^{kn}$$

由于 $(n, p-1)=1$, 设

$$h: \mathbb{Z}/(p-1)\mathbb{Z} \longrightarrow \mathbb{Z}/(p-1)\mathbb{Z}, \quad k \mapsto kn$$

则 $h \in \text{Aut}(\mathbb{Z}/(p-1)\mathbb{Z})$.

因此, $f$ 为双射. 证毕.

5

设素数 $p>2$，证明：$\delta_p(a)=2$ 的充要条件是 $a \equiv-1(\bmod p).$

证明：

1. "$\implies$"

若 $\delta_p(a) = 2$, 则

$$\begin{align} a^2 &\equiv 1 \pmod p \\ &\iff (a-1)(a+1) \equiv 0 \pmod p \\ &\iff p \mid (a-1) \lor p \mid (a+1) \end{align}$$

若 $p \nmid (a+1)$, 则 $\delta_p(a)=1$, 矛盾, 故

$$p \mid a-1$$

即

$$a \equiv -1 \pmod p$$

2. "$\Longleftarrow$"

若 $a \equiv -1 \pmod p$, 则

$$a^2 \equiv 1 \pmod p$$

故

$$\delta_p(a)=2$$

9

设 $n=2^k, k > 3$，证明：$\delta_n(a)=2^{k-2}$ 的充要条件是 $a \equiv \pm 3(\bmod 8)$。

证明：

对于 $(\mathbb{Z}/2^k\mathbb{Z})^*, k \ge 3$, 有

$$(\mathbb{Z}/2^k\mathbb{Z})^* = \{(-1)^a 5^b \mid a=0,1, 0 \le b < 2^{k-2}\}$$

即

$$(\mathbb{Z}/2^k\mathbb{Z})^* \cong C_2 \times C_{2^{k-2}}$$

对于 $\forall a \in (\mathbb{Z}/2^k\mathbb{Z})^*$, 设

$$a \equiv (-1)^u 5^v \pmod{2^k}$$

其中 $u=0,1, 0 \le v < 2^{k-2}$.

于是

$$\delta_{2^k}(a) = \left[2^u, \frac{2^{k-2}}{(v, 2^{k-2})}\right]$$

1. "$\implies$"

   2. 若 $u=0$, 则 $\delta_{2^k}(a) = \frac{2^{k-2}}{(v, 2^{k-2})} = 2^{k-2}$，故 $v \equiv 1 \pmod 2$.
   3. 若 $u=1$, 则 $\delta_{2^k}(a) = \left[2, \frac{2^{k-2}}{(v, 2^{k-2})}\right] = 2^{k-2}$，故 $v \equiv 1 \pmod 2$.

由于 $v \equiv 1 \pmod 2$, 因此

$$5^v \equiv 5 \pmod 8$$

于是

$$a \equiv (-1)^u 5^v \equiv (-1)^u 5 \equiv \pm 5 \equiv \pm 3 \pmod 8$$

2. "$\Longleftarrow$"

若 $a \equiv \pm 3 \pmod 8$, 则 $v \equiv 1 \pmod 2$, 于是

$$\delta_{2^k}(a) = \left[2^u, \frac{2^{k-2}}{(v, 2^{k-2})}\right] = \left[2^u, 2^{k-2}\right] = 2^{k-2}$$

10

设 $m>2$ 并有原根存在，证明：

1. $a$ 是模 $m$ 的二次剩余的充要条件是 $a^{\varphi(m) / 2} \equiv 1(\bmod m)$；
2. 若 $a$ 是 $m$ 的二次剩余，则 $x^2 \equiv a(\bmod m)$ 恰有二解；
3. 模 $m$ 恰有 $\frac{1}{2} \varphi(m)$ 个二次剩余。

证明：

设 $g$ 为 $m$ 的一个原根, 则 $(\mathbb{Z}/m\mathbb{Z})^* = \langle g \rangle$.

1. 设 $a \equiv g^k \pmod m$, $0 < k \le \varphi(m)$.

则

$$\begin{align} & \exists x : x^2 \equiv a \pmod m \\ \iff & \exists 0 < j \le \varphi(m) : g^{2j} \equiv g^k \pmod m \\ \iff & \exists 0 < j \le \varphi(m) : 2j \equiv k \pmod{\varphi(m)} \\ \iff & (2, \varphi(m)) \mid k \end{align}$$

而 $2 \mid \varphi(m)$, 故 $2 \mid k$. 设 $k=2t$, 于是

$$a^{\frac{\varphi(m)}{2}} \equiv (g^{2t})^{\frac{\varphi(m)}{2}} \equiv g^{t\varphi(m)} \equiv (g^{\varphi(m)})^t \equiv 1 \pmod m$$

2. 设 $a = g^{2t}$, $x = g^j \pmod m$ 为其中一解, 则

$$\begin{align} & x^2 \equiv a \pmod m \\ \iff & \exists 0 < j \le \varphi(m) : j \equiv t \pmod{\frac{\varphi(m)}{2}} \\ \iff & x \equiv g^j \pmod m \lor x \equiv g^{j+\frac{\varphi(m)}{2}} \pmod m \end{align}$$

恰有二解.

3. 即在 $1, 2, 3, \dots, \varphi(m)$ 中的偶数个数

$$\frac{\varphi(m)}{2}$$

11

设素数 $p>2$，若 $g$ 为模 $p$ 的原根，且

$$g^{p-1} \equiv 1\left(\bmod p^2\right)$$

则 $g$ 不是 $p^k$ 的原根，$k \geqslant 2$。

证明：

使用反证法.

若 $g$ 为 $p^k$ 的原根, 则 $g+p$ 亦为 $p^k$ 的原根. $g$ 为 $p$ 的原根.

若 $g^{p-1} \equiv 1 \pmod{p^2}$, 则

$$\begin{align} (g+p)^{p-1} &\equiv g^{p-1} + \binom{p-1}{1} g^{p-2} p \pmod{p^2} \\ &\equiv 1 + (p-1)g^{p-2}p \pmod{p^2} \end{align}$$

由于 $p^2 \nmid (p-1)g^{p-2}p$, 故

$$(g+p)^{p-1} \not\equiv 1 \pmod{p^2}$$

因此存在 $p^k$ 的原根 $g$ 使之为 $p$ 的原根且 $g^{p-1} \not\equiv 1 \pmod{p^2}$.

12

1. 若 $q=4 k+1, p=2 q+1$ 均为素数，则 2 是 $p$ 的原根；
2. 若 $q=2 k+1(k>1), p=2 q+1$ 均为素数，则 $-3,-4$ 均为 $p$ 的原根。

证明：

1. 对于 $2^2$, 由于 $p=2q+1 = 8k+3 \ge 11$, 故 $2^2 \not\equiv 1 \pmod p$.

而

$$2^q \equiv 2^{\frac{p-1}{2}} \equiv \left(\frac{2}{p}\right) \pmod p$$

其中

$$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = -1$$

故

$$2^q \not\equiv 1 \pmod p$$

又由 Lagrange 定理知 $\operatorname{ord}(2) \mid \varphi(p) = 2q$, 故 $\operatorname{ord}(2) = 2q$.

故 2 是 $p$ 的原根.

2. 3. $-3$ 为 $p$ 的原根

对于 $(-3)^2$, 由于 $p=2q+1 = 4k+3 \ge 11$, 故 $(-3)^2 \not\equiv 1 \pmod p$.

若 $(-3)^q \equiv (-3)^{\frac{p-1}{2}} \equiv \left(\frac{-3}{p}\right) \equiv 1 \pmod p$, 则 $p \equiv 1 \pmod 6$.

而 $p = 4k+3 \not\equiv 1 \pmod 6$.

故 $\left(\frac{-3}{p}\right) \not\equiv 1 \pmod p$.

由 Lagrange 定理知 $\operatorname{ord}(-3) \mid \varphi(p)=2q$, 故 $\operatorname{ord}(-3)=2q$.

即 $-3$ 为 $p$ 的原根.

2. $-4$ 为 $p$ 的原根

对于 $(-4)^2$, 由于 $p=2q+1 = 4k+3 \ge 11$, 故 $(-4)^2 \not\equiv 1 \pmod p$.

若 $(-4)^q \equiv (-4)^{\frac{p-1}{2}} \equiv \left(\frac{-4}{p}\right) \equiv 1 \pmod p$.

而

$$\begin{align} \left(\frac{-4}{p}\right) &= \left(\frac{-1}{p}\right) \left(\frac{2}{p}\right)^2 \\ &= (-1)^{\frac{p-1}{2}} \cdot 1 \\ &= (-1)^q \cdot 1 \\ &= -1 \end{align}$$

故 $(-4)^q \not\equiv 1 \pmod p$.

由 Lagrange 定理知 $\operatorname{ord}(-4) \mid \varphi(p)=2q$, 故 $\operatorname{ord}(-4)=2q$.

即 $-4$ 为 $p$ 的原根.

参考

• https://zhuanlan.zhihu.com/p/543010816

• https://zhuanlan.zhihu.com/p/544792225

• https://zhuanlan.zhihu.com/p/545595129

• https://zhuanlan.zhihu.com/p/546385318

• https://zhuanlan.zhihu.com/p/547333984

• https://zhuanlan.zhihu.com/p/548061254

贡献者: Ming Wei

上一页潘承洞《数论基础》选解：第三章

下一页潘承洞《数论基础》选解：第二章