Primitive Roots

A primitive root modulo $n$ is a generator of the multiplicative group modulo $n$. It is an element $g$ such that its powers $g,g^2,\dots ,g^{\varphi (n)}$ cover all coprime residues.

Definition

Existence Theorem

Primitive roots exist only for moduli of the form: where $p$ is an odd prime and $k\ge 1$.

• Notably, no primitive roots for $n=8,12,15,\dots$ (composites divisible by two primes, or powers of 2 $\ge 8$).

Index (Discrete Logarithm)

If $g$ is a primitive root, any $a$ coprime to $n$ can be written as $a\equiv g^k(\mathrm{mod}n)$. $k={\text{ind}}_g(a)$ is called the index or discrete logarithm.

• Properties like logarithms: $\text{ind}(ab)\equiv \text{ind}(a)+\text{ind}(b)(\mathrm{mod}\varphi (n))$.

Practice Problems