This article is translated by AI.

1

Write out the index tables modulo $3,5,11,13,19$, and point out all their primitive roots.

Solution:

1. Index table modulo 3

The element $a$ of $(\mathbb{Z}/3\mathbb{Z})^*$ and its order $\operatorname{ord}_3(a)$ are as follows:

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

Primitive root: 2.

2. Index table modulo 5

The element $a$ of $(\mathbb{Z}/5\mathbb{Z})^*$ and its order $\operatorname{ord}_5(a)$ are as follows:

$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$

Primitive roots: 2, 3.

3. Index table modulo 11

The element $a$ of $(\mathbb{Z}/11\mathbb{Z})^*$ and its order $\operatorname{ord}_{11}(a)$ are as follows:

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

Primitive roots: 2, 6, 7, 8.

4. Index table modulo 13

The element $a$ of $(\mathbb{Z}/13\mathbb{Z})^*$ and its order $\operatorname{ord}_{13}(a)$ are as follows:

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

8	9	10	11	12
4	3	6	12	2

Primitive roots: 2, 6, 7, 11.

5. Index table modulo 19

The element $a$ of $(\mathbb{Z}/19\mathbb{Z})^*$ and its order $\operatorname{ord}_{19}(a)$ are as follows:

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

Primitive roots: 2, 3, 10, 13, 14, 15.

2

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

Solution:$\delta_{43}(7) = 6$, $\delta_{41}(10) = 5$

3

Let $p$ be a prime number, $n \geqslant 1,(n, p-1)=1$. Prove: When $x$ passes through the complete residue system modulo $p$, $x^n$ also passes through the complete residue system modulo $p$.

Proof:

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

We need to prove that $f$ is a bijection.

Take a primitive root $g$ of $(\mathbb{Z}/p\mathbb{Z})^*$, then

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

Since $(n, p-1)=1$, let

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

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

Therefore, $f$ is a bijection. Q.E.D.

5

Let prime $p>2$, prove: The necessary and sufficient condition for $\delta_p(a)=2$ is $a \equiv-1(\bmod p).$

Proof:

1. "$\implies$"

If $\delta_p(a) = 2$, then

$$\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}$$

If $p \nmid (a+1)$, then $\delta_p(a)=1$, contradiction, so

$$p \mid a-1$$

That is

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

2. "$\Longleftarrow$"

If $a \equiv -1 \pmod p$, then

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

So

$$\delta_p(a)=2$$

9

Let $n=2^k, k > 3$, prove: The necessary and sufficient condition for $\delta_n(a)=2^{k-2}$ is $a \equiv \pm 3(\bmod 8)$.

Proof:

For $(\mathbb{Z}/2^k\mathbb{Z})^*, k \ge 3$, we have

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

That is

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

For $\forall a \in (\mathbb{Z}/2^k\mathbb{Z})^*$, let

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

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

Thus

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

1. "$\implies$"

   2. If $u=0$, then $\delta_{2^k}(a) = \frac{2^{k-2}}{(v, 2^{k-2})} = 2^{k-2}$, so $v \equiv 1 \pmod 2$.
   3. If $u=1$, then $\delta_{2^k}(a) = \left[2, \frac{2^{k-2}}{(v, 2^{k-2})}\right] = 2^{k-2}$, so $v \equiv 1 \pmod 2$.

Since $v \equiv 1 \pmod 2$, therefore

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

Thus

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

2. "$\Longleftarrow$"

If $a \equiv \pm 3 \pmod 8$, then $v \equiv 1 \pmod 2$, thus

$$\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

Let $m>2$ and a primitive root exists, prove:

1. The necessary and sufficient condition for $a$ to be a quadratic residue modulo $m$ is $a^{\varphi(m) / 2} \equiv 1(\bmod m)$;
2. If $a$ is a quadratic residue of $m$, then $x^2 \equiv a(\bmod m)$ has exactly two solutions;
3. Modulo $m$ has exactly $\frac{1}{2} \varphi(m)$ quadratic residues.

Proof:

Let $g$ be a primitive root of $m$, then $(\mathbb{Z}/m\mathbb{Z})^* = \langle g \rangle$.

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

Then

$$\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}$$

And $2 \mid \varphi(m)$, so $2 \mid k$. Let $k=2t$, thus

$$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. Let $a = g^{2t}$, $x = g^j \pmod m$ be one solution, then

$$\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}$$

Exactly two solutions.

3. That is the number of even numbers in $1, 2, 3, \dots, \varphi(m)$

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

11

Let prime $p>2$, if $g$ is a primitive root modulo $p$, and

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

Then $g$ is not a primitive root of $p^k$, $k \geqslant 2$.

Proof:

Use proof by contradiction.

If $g$ is a primitive root of $p^k$, then $g+p$ is also a primitive root of $p^k$. $g$ is a primitive root of $p$.

If $g^{p-1} \equiv 1 \pmod{p^2}$, then

$$\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}$$

Since $p^2 \nmid (p-1)g^{p-2}p$, so

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

Therefore there exists a primitive root $g$ of $p^k$ such that it is a primitive root of $p$ and $g^{p-1} \not\equiv 1 \pmod{p^2}$.

12

1. If $q=4 k+1, p=2 q+1$ are both prime numbers, then 2 is a primitive root of $p$;
2. If $q=2 k+1(k>1), p=2 q+1$ are both prime numbers, then $-3,-4$ are both primitive roots of $p$.

Proof:

1. For $2^2$, since $p=2q+1 = 8k+3 \ge 11$, so $2^2 \not\equiv 1 \pmod p$.

And

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

Where

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

So

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

Also by Lagrange's Theorem $\operatorname{ord}(2) \mid \varphi(p) = 2q$, so $\operatorname{ord}(2) = 2q$.

So 2 is a primitive root of $p$.

2. 3. $-3$ is a primitive root of $p$

For $(-3)^2$, since $p=2q+1 = 4k+3 \ge 11$, so $(-3)^2 \not\equiv 1 \pmod p$.

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

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

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

By Lagrange's Theorem $\operatorname{ord}(-3) \mid \varphi(p)=2q$, so $\operatorname{ord}(-3)=2q$.

That is $-3$ is a primitive root of $p$.

2. $-4$ is a primitive root of $p$

For $(-4)^2$, since $p=2q+1 = 4k+3 \ge 11$, so $(-4)^2 \not\equiv 1 \pmod p$.

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

And

$$\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}$$

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

By Lagrange's Theorem $\operatorname{ord}(-4) \mid \varphi(p)=2q$, so $\operatorname{ord}(-4)=2q$.

That is $-4$ is a primitive root of $p$.

References

• 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

Contributors: Ming Wei

Previous pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 3

Next pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 2