Primitive Roots - Key Properties

When primitive roots exist, they satisfy remarkable properties that facilitate computations and reveal deep structure in modular arithmetic. Understanding these properties is essential for applications in cryptography and computational number theory.

TheoremNumber of Primitive Roots

If primitive roots exist modulo $n$ , then there are exactly $\phi(\phi(n))$ incongruent primitive roots modulo $n$ .

These are precisely the powers $g^k$ where $\gcd(k, \phi(n)) = 1$ and $g$ is any primitive root modulo $n$ .

This formula follows from the structure of cyclic groups: a generator raised to a power coprime to the group order remains a generator.

ExampleCounting Primitive Roots

For $n = 7$ , we have $\phi(7) = 6$ and $\phi(\phi(7)) = \phi(6) = 2$ .

So there are exactly $2$ primitive roots modulo $7$ in the range $1$ to $6$ .

Since $3$ is a primitive root, the primitive roots are $3^k$ where $\gcd(k, 6) = 1$ :

$k = 1$ : $3^1 \equiv 3 \pmod{7}$
$k = 5$ : $3^5 \equiv 5 \pmod{7}$

Indeed, $\{3, 5\}$ are the only primitive roots modulo $7$ in $\{1, 2, \ldots, 6\}$ .

TheoremProperties of Indices

Let $g$ be a primitive root modulo $n$ . The index function satisfies:

Homomorphism: $\text{ind}_g(ab) \equiv \text{ind}_g(a) + \text{ind}_g(b) \pmod{\phi(n)}$
Power rule: $\text{ind}_g(a^k) \equiv k \cdot \text{ind}_g(a) \pmod{\phi(n)}$
Uniqueness: Each $a$ coprime to $n$ has a unique index modulo $\phi(n)$
Inverse: $\text{ind}_g(a^{-1}) \equiv -\text{ind}_g(a) \pmod{\phi(n)}$

These properties make indices behave like logarithms, converting multiplication to addition.

ExampleUsing Index Properties

With base $g = 2$ modulo $11$ (primitive root), we have $\phi(11) = 10$ .

Compute powers of $2$ modulo $11$ : $2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 8, \quad 2^4 \equiv 5, \quad 2^5 \equiv 10$ $2^6 \equiv 9, \quad 2^7 \equiv 7, \quad 2^8 \equiv 3, \quad 2^9 \equiv 6, \quad 2^{10} \equiv 1$

So $\text{ind}_2(6) = 9$ and $\text{ind}_2(3) = 8$ .

Verify: $\text{ind}_2(18) = \text{ind}_2(7) = 7 \equiv 9 + 8 = 17 \equiv 7 \pmod{10}$ . ✓

TheoremSolving Exponential Congruences

Using indices, the congruence $a^x \equiv b \pmod{p}$ (where $p$ is prime with primitive root $g$ ) transforms to: $x \cdot \text{ind}_g(a) \equiv \text{ind}_g(b) \pmod{p-1}$

This linear congruence can be solved using techniques from modular arithmetic.

ExampleExponential Congruence

Solve $3^x \equiv 5 \pmod{7}$ using $g = 3$ as primitive root modulo $7$ .

Taking indices: $x \cdot \text{ind}_3(3) \equiv \text{ind}_3(5) \pmod{6}$ .

Since $\text{ind}_3(3) = 1$ and $\text{ind}_3(5) = 5$ : $x \equiv 5 \pmod{6}$

So $x = 5, 11, 17, \ldots$ are solutions.

Verify: $3^5 = 243 = 34 \cdot 7 + 5 \equiv 5 \pmod{7}$ . ✓

TheoremQuadratic Residues via Primitive Roots

Let $p$ be an odd prime with primitive root $g$ , and let $a \equiv g^k \pmod{p}$ . Then: $\left(\frac{a}{p}\right) = (-1)^k$

Thus, $a$ is a quadratic residue modulo $p$ if and only if $k$ is even.

This provides an alternative characterization of quadratic residues using the parity of indices.

ExampleQuadratic Residues via Indices

Modulo $7$ with primitive root $g = 3$ :

$2 \equiv 3^2$ , so $\left(\frac{2}{7}\right) = (-1)^2 = 1$ (quadratic residue)
$3 \equiv 3^1$ , so $\left(\frac{3}{7}\right) = (-1)^1 = -1$ (nonresidue)
$4 \equiv 3^4$ , so $\left(\frac{4}{7}\right) = (-1)^4 = 1$ (quadratic residue)

Indeed: $3^2 = 9 \equiv 2 \pmod{7}$ and $2^2 = 4 \pmod{7}$ , confirming they are quadratic residues.

Remark

Primitive roots provide computational advantages: once a table of indices is constructed, multiplication modulo $n$ reduces to addition, and exponentiation reduces to multiplication. This logarithmic approach was historically important before modern computers and remains useful in certain cryptographic contexts.

These properties demonstrate how primitive roots impose elegant structure on modular arithmetic when they exist.