# Primitive roots of odd primes

The following facts about primitive roots of an odd prime seem to be well known. For example, they both appear as exercises in Burton's Elementary Number Theory.

Let $p$ be an odd prime. Then:
(1) Any primitive root of $p^2$ is a primitive root of $p^k$ for every positive integer $k$.
(2) Any odd primitive root of $p^k$ is a primitive root of $2p^k$.

I thought these facts might be from Gauss' Disquisitiones Arithmeticae, but I couldn't find them there. Does anyone know the origin of these two facts?

## 2 Answers

For what it's worth, Dickson, in his History of the Theory of Numbers, Chapter VII, page $186$, credits Jacobi (Canon Arithmeticus, $1839$) with the result that if $p$ is an odd prime, a primitive root of $p^2$ is a primitive root of $p^k$ for all $k> 2$.

• Dickson says: Jacobi proved that, if $n$ is an odd prime, any primitive root of $n^2$ is a primitive root of any higher power of $n$. That gives us most of (1). I'm going to have to take a closer look at that chapter in Dickson to see if the rest is there. Thanks for this. – Anononym Jan 13 '12 at 7:31
• @Anononym: Yes, I only saw the prime power part in Dickson. The fact that it is also a primitive root of $p$ is barely worth noting, since it is clear that we can always go down. – André Nicolas Jan 13 '12 at 7:44
• Dear André: Your answer looks convincing to me. I think $(2)$ is an almost trivial consequence of $(1)$. +1! – Pierre-Yves Gaillard Jan 13 '12 at 8:06

See page 23 and page 24 of Alan Baker's A Concise Introduction to the Theory of Numbers, or see this answer.

• Thanks for the response, but I'm not looking for a proof of those two facts about primitive roots. I'm looking for their origin. Specifically, I'd like to know who first proved these results. – Anononym Jan 13 '12 at 6:24
• Dear @Anononym: Sorry, I didn't read your question carefully enough. It's a good question: +1. I'll still leave my "answer" because, even if it doesn't answer the question, it adds a tiny bit to it (at least I hope so) by providing explicit references. – Pierre-Yves Gaillard Jan 13 '12 at 6:47