Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.