existence of primitive roots for powers of an odd prime
The following theorem gives a way of finding a primitive root^{} for ${p}^{k}$, for an odd prime $p$ and $k\ge 1$, given a primitive root of $p$. Recall that every prime has a primitive root.
Theorem.
Suppose that $p$ is an odd prime. Then ${p}^{k}$ also has a primitive root, for all $k\mathrm{\ge}\mathrm{1}$. Moreover:

1.
If $g$ is a primitive root of $p$ and ${g}^{p1}\ne 1mod{p}^{2}$ then $g$ is a primitive root of ${p}^{2}$. Otherwise, if ${g}^{p1}\equiv 1mod{p}^{2}$ then $g+p$ is a primitive root of ${p}^{2}$.

2.
If $k\ge 2$ and $h$ is a primitive root of ${p}^{k}$ then $h$ is a primitive root of ${p}^{k+1}$.
Title  existence of primitive roots for powers of an odd prime 

Canonical name  ExistenceOfPrimitiveRootsForPowersOfAnOddPrime 
Date of creation  20130322 16:21:01 
Last modified on  20130322 16:21:01 
Owner  alozano (2414) 
Last modified by  alozano (2414) 
Numerical id  4 
Author  alozano (2414) 
Entry type  Theorem 
Classification  msc 1100 
Related topic  EveryPrimeHasAPrimitiveRoot 