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. 
