proof of properties of primitive roots
The material in the main article is conveniently recast in terms of the groups , the multiplicative group of units in . Note that the order of this group is exactly where is the Euler phi function. Then saying that an integer is a primitive root of is equivalent to saying that the residue class of generates .
Restated, this says that if the residue class of generates , then the set is a complete set of representatives for ; this is obvious.
Restated, this says that generates if and only if has exact order , which is also obvious.
If generates , then has exact order and thus if and only if if and only if .
Suppose generates . Then if and only if if and only if . Clearly we can choose if and only if .
This follows immediately from (4).∎