The proof depends on the fact that for . This shows that the order of is .
Once you established that prove that are all incongruent with eachother. Then are all incrongruent with eachother. And finally each element in is incongruenct with each element of .
With those two facts the proof is almost complete. Because there are a total of in and . Which means is a reduced system of residues. And each element does not have order . Which means it has no primitive root.