Primitive Roots - Main Theorem

The existence and structure of primitive roots modulo prime powers and special moduli form one of the cornerstones of elementary number theory. These results reveal precisely when the multiplicative group modulo $n$ has maximal cyclic structure.

TheoremPrimitive Roots Modulo Primes

Let $p$ be a prime number. Then there exist $\phi(p-1)$ primitive roots modulo $p$ .

Moreover, for any prime $p$ , the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic of order $p-1$ .

This fundamental result guarantees that every prime has primitive roots. The cyclicity of $(\mathbb{Z}/p\mathbb{Z})^*$ makes modular arithmetic modulo primes particularly well-behaved.

ExamplePrimitive Roots Modulo 17

For $p = 17$ , we have $\phi(p-1) = \phi(16) = 8$ primitive roots.

Since $3$ is a primitive root modulo $17$ , all primitive roots are $3^k$ where $\gcd(k, 16) = 1$ : $k \in \{1, 3, 5, 7, 9, 11, 13, 15\}$

Computing: $3^1 = 3, 3^3 = 27 \equiv 10, 3^5 \equiv 5, 3^7 \equiv 11, 3^9 \equiv 14, 3^{11} \equiv 7, 3^{13} \equiv 12, 3^{15} \equiv 6 \pmod{17}$ .

So the primitive roots modulo $17$ are: $\{3, 5, 6, 7, 10, 11, 12, 14\}$ .

TheoremStructure of $(\mathbb{Z}/p^k\mathbb{Z})^*$

Let $p$ be an odd prime and $k \geq 1$ . Then $(\mathbb{Z}/p^k\mathbb{Z})^*$ is cyclic of order $\phi(p^k) = p^{k-1}(p-1)$ .

In particular, primitive roots exist modulo $p^k$ for all odd primes $p$ and all $k \geq 1$ .

The cyclicity of $(\mathbb{Z}/p^k\mathbb{Z})^*$ for odd prime powers is remarkable and contrasts sharply with the behavior for powers of $2$ .

ExamplePrimitive Roots Modulo 25

We have $\phi(25) = \phi(5^2) = 20$ . Since $2$ is a primitive root modulo $5$ , we check if it works modulo $25$ .

Compute $2^{\phi(5)} = 2^4 = 16 \pmod{25}$ . Since $16 \not\equiv 1 \pmod{25}$ , the element $2$ is a primitive root modulo $25$ (and modulo all $5^k$ ).

The order is $\text{ord}_{25}(2) = 20$ , confirming it generates all $\phi(25) = 20$ units.

TheoremStructure of $(\mathbb{Z}/2^k\mathbb{Z})^*$ for $k \geq 3$

For $k \geq 3$ , the group $(\mathbb{Z}/2^k\mathbb{Z})^*$ is not cyclic. Instead: $(\mathbb{Z}/2^k\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{k-2}\mathbb{Z}$

The group has exponent $2^{k-2}$ , not $\phi(2^k) = 2^{k-1}$ .

This explains why primitive roots don't exist modulo powers of $2$ greater than $4$ . The multiplicative group factors as a product of two cyclic groups rather than being cyclic itself.

ExampleNo Primitive Root Modulo 16

For $n = 16$ , we have $\phi(16) = 8$ . The group $(\mathbb{Z}/16\mathbb{Z})^* = \{1, 3, 5, 7, 9, 11, 13, 15\}$ .

Every element has order dividing $4$ :

$3^2 = 9, 3^4 = 81 \equiv 1 \pmod{16}$ , so $\text{ord}_{16}(3) = 4$
$5^2 = 25 \equiv 9, 5^4 \equiv 1 \pmod{16}$ , so $\text{ord}_{16}(5) = 4$
$7^2 = 49 \equiv 1 \pmod{16}$ , so $\text{ord}_{16}(7) = 2$

No element has order $8$ , confirming the group is not cyclic.

The structure is $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}$ with generators $\{-1, 3\}$ .

TheoremComplete Classification

Primitive roots modulo $n$ exist if and only if: $n \in \{1, 2, 4, p^k, 2p^k : p \text{ odd prime}, k \geq 1\}$

For all other moduli, $(\mathbb{Z}/n\mathbb{Z})^*$ is not cyclic.

This complete classification tells us exactly when we can find generators for the multiplicative group modulo $n$ .

Remark

For composite $n$ not of the specified forms, the group $(\mathbb{Z}/n\mathbb{Z})^*$ decomposes as a product of cyclic groups by the Chinese Remainder Theorem. For instance: $(\mathbb{Z}/12\mathbb{Z})^* \cong (\mathbb{Z}/4\mathbb{Z})^* \times (\mathbb{Z}/3\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$

This product structure explains why primitive roots don't exist modulo such $n$ .

These structural theorems completely characterize when primitive roots exist and provide the foundation for discrete logarithm-based cryptography.