Exercise 2.8.2 (Primitive root modulo 23)

Find a primitive root of $23$ .

Answers

Proof. $2^{11} \equiv 1 \equiv 3^{11} (\mod 223)$ so $2, 3$ are not primitive roots modulo $23$ .

$5^{22} \equiv 1 (\mod 23)$ (Fermat’s Theorem). For $p = 23$ , $p - 1 = 2 \times 11$ , and

5^{(p - 1) ∕ 2} = 5^{11} \equiv - 1 ≢ 1 (\mod 23), 5^{(p - 1) ∕ 11} = 5^{2} = 2 ≢ 1 (mod 23) .

This shows that the order of $5$ is $p - 1 = 22$ , thus

$5$ is a primitive root modulo $23$ . □

Note: The set of primitive roots modulo $23$ is

A = {5, 7, 10, 11, 14, 15, 17, 19, 20, 21} .

Here $| A | = ϕ (22) = 10$ .

2024-09-11 09:18