Primitive Root

number-theory

Definition

Primitive Root

A primitive root modulo $n$ is an integer $g$ such that every integer coprime to $n$ is congruent to a power of $g$ modulo $n$. Equivalently, $g$ is a generator of the multiplicative group of integers modulo $n$.

If $g$ is a primitive root modulo $n$, then

$$\{g^1,g^2,\dots ,g^{\phi (n)}\}\equiv \{1,2,\dots ,n-1\}(\mathrm{mod}n)$$

where $\phi$ denotes Euler’s totient function.