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^{p-1}\ne 1mod{p}^2$ then $g$ is a primitive root of $p^2$. Otherwise, if $g^{p-1}\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	2013-03-22 16:21:01
Last modified on	2013-03-22 16:21:01
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	4
Author	alozano (2414)
Entry type	Theorem
Classification	msc 11-00
Related topic	EveryPrimeHasAPrimitiveRoot