Primitive Roots and Sets of Residues

Theorem
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.

You have no rights to post comments