\[n\]
has a primitive root \[a\]
so that \[a^{\phi (n)} \equiv 1 \; (mod \; n)\]
but for no smaller power than \[\phi (n)\]
where \[\phi (n)\]
is the number of integers less than \[n\]
which are relatively prime to \[n\]
. The set of reduced residues of \[n\]
are powers of a primitive root, and if \[a \; (mod \; n)\]
is a primitive root, then the set of reduced residues is \[\{ a, \; a^2,..., \; a^{\phi (n)-2}, \; a^{\phi (n)-1} \; a^{\phi (n)} \}\]
. There are \[ \frac{\phi (n)}{2}\]
pairs \[( a^j, \; a^{\phi (n)-j} )\]
. Multiplying the elements of the set together gives \[a^{1+ \phi (n)-1}...a^{j+ \phi (n)-j} = a^{\frac{\phi (n)}{2}} \equiv -1 \; (mod \; n)\]
since \[a\]
is a primitive root of \[n\]
.If
\[n\]
does not have a primitive root then \[a^{\frac{phi (n)}{2}} \equiv 1 \; (mod \; n)\]
since the power must divide \[\phi (n)\]
.