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

if $p$ is an odd primitive, Prove there are no primitive roots of $\bmod 3p$

Where I'm at: $a^{2(p-1)}=1 \pmod{3p}$ where a is a primitive root of $3p$ (by contradiction) $(a/3p)=(a/3)(a/p)$ are the Legendre symbols, and stuck here..tried a couple of things, but got nowhere, could use a helping hand :]

share|cite|improve this question
So p=3 has a primitive root: 2 generates 2, 4, 8, 7, 5, 1. all the units mod 9. – user58512 Feb 6 '13 at 13:57

is this right? $a^{p-1}=1 \pmod p$ and $a^2=1 \pmod 3$ and thus $a^{\operatorname{lcm}(2,p-1)}=1 \pmod {3p}$ but because $p-1$ is even then $\operatorname{lcm}(2,p-1)<2(p-1)$ and so a is not a primitive root modulo $3p$?..

share|cite|improve this answer
like in the question, $a$ is a primitive root of $3p$ by contradiction – Rachel Bernoulli Feb 6 '13 at 13:38
Spot on! The lcm is of course $p-1$. – Andreas Caranti Feb 6 '13 at 13:39
yeah, and so p-1<2*(p-1) and we have a contradiction – Rachel Bernoulli Feb 6 '13 at 13:39
ok thank you guys :] – Rachel Bernoulli Feb 6 '13 at 13:39
Notice that this argument fails when $p=3$, for then the order of an element is not counted this way, as shown by the examle of user61216. – awllower Feb 6 '13 at 14:03

Counter example: 2 is a primitive root mod (3*3)

share|cite|improve this answer
why is this being upvoted? It doesn't answer the question and I wrote this in my answer first. – user58512 Feb 6 '13 at 14:47
@user58512: some people answer before reading all the other answers. I usually delete my answers that turn out to be duplicates, but evidently not everyone does. However, this would probably serve better as a comment to the question, since it points out that the question needs modification, rather than providing an answer. – robjohn Feb 6 '13 at 17:52

You mean $p$ is an odd prime. (As noted by user58512 one has to take $p > 3$.)

Try and use the Chinese Remainder Theorem to show that the exponent of the group of units of $\mathbf{Z}_{3 p}$ is at most (actually, exactly) $p-1$, while its order is twice as much.

share|cite|improve this answer
But if we use the CRT, we would be able to show that $(Z/{3p})^*$ is not cyclic, hence admitting no primitive roots, right? – awllower Feb 6 '13 at 13:52

Note that when $p=3$ the theorem does not hold! 2 is a primitive root.

So supposing $p$ is not 3...

Since $p$ is odd let $p = 2^r k+1$ with $k$ odd.

The group of units is $\mod {3p}$ is $$(\mathbb Z/(3p))^\times \simeq \mathbb Z/(2) \times \mathbb Z/(2^r) \times (\mathbb Z/(k))^\times$$ by Sun Zi's theorem.

There can be no primitive root for this because of the two $\mathbb Z/(2^i)$ parts.

share|cite|improve this answer
If $k$ is even, you will have only one factor of order two. – Andreas Caranti Feb 6 '13 at 13:44
@AndreasCaranti, I don't understand - I think what I've written is fine whether k is even or odd. – user58512 Feb 6 '13 at 13:53
I assumed p is not 3, but that case........ breaks the theorem.. – user58512 Feb 6 '13 at 13:55
@AndreasCaranti, thanks I added a correction now. – user58512 Feb 6 '13 at 13:58
Thanks to peoplepower for another correction. – user58512 Feb 6 '13 at 15:00

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.