## Primitive Roots and Sets of Residues

If

\[a\]

is a primitive root of \[n\]

, so that the order of \[a\]

is \[\phi (n)\]

then \[a^{\phi (n)} \equiv 1 \; (mod \; n)\]

and this is not true for any smaller power than \[\phi (n)\]

then \[\{ a, \; a^2, ..., \; a^{\phi (n)} \}\]

is a reduced set of residues (mod n).Certainly all the

\[a^i, \; 1 \le a^i \le \phi (n)\]

in the above set are all distinct, since if \[a^i \equiv a^j \; (mod \; n), \; i \gt j\]

then \[a^i a^{\phi (n)} \equiv a^j \; (mod \; n) \rightarrow a^{i-j+ \phi (n)} \equiv 1 \; (mod \; n) \rightarrow i =j\]

.Also

\[gcd(a, n) =1 \rightarrow gcd(a^i,n)=1\]

so there are \[\phi (n)\]

elements in the above set.Example:

\[\phi (14)=6\]

.Take

\[a=3\]

then a complete set of residues (mod 14) is \[\{ 3^1, \; 3^2, \; 3^3, \; 3^4, \; 3^5, \; 3^6 \}\]

which reduced (mod 14) is the set \[\{ 3, \; 9, \; 13, \; 11, \; 5, \; 1 \}\]

, each element of which is relatively prime to 14.