Primitive Root is Generator of Reduced Residue System

Theorem

Let $a$ be a primitive root of $n$.

Then:

$\left\{{a, a^2, a^3, \ldots, a^{\phi \left({n}\right)}}\right\}$

where $\phi \left({n}\right)$ is the Euler phi function of $n$, is a reduced residue system of $n$.

Thus the first $\phi \left({n}\right)$ powers of $a$ "generates" $R$.

We say that $a$ is a generator of $R$.

Proof

Let $R = \left\{{a, a^2, a^3, \ldots, a^{\phi \left({n}\right)}}\right\}$.

Each element of $R$ is coprime to $n$ as $a \perp n$.

Suppose $a^r \equiv a^s \pmod n$ where $1 \le r \le s \le \phi \left({n}\right)$.

Then $a^{r-s} \equiv 1 \pmod n$.

From the definition of primitive root, the order of $a$ modulo $n$ is $\phi \left({n}\right)$.

So from Integer to Power of Multiple of Order $\phi \left({n}\right)$ divides $r - s$ and so $r = s$.

So no two elements are congruent modulo $n$.

So as $R$ contains $\phi \left({n}\right)$ integers none of which are congruent modulo $n$ to any of the others, $R$ is a reduced residue system of $n$.

$\blacksquare$