## The Product of a Reduced Set of Residues

\[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)\]

.