# $p$ is an odd primitive, Show why there are no primitive roots of $\bmod 3p$

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 :]

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

-
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)

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

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

-
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