# Finding primitive root modulo 27

I came across a problem regarding primitive roots. It asks to find all primitive roots modulo 27. I know by general theorem, there are $$\phi(\phi(27)) = 6$$ of them.

In order to find them all explicitly, I first find 2 is a primitive root mod 3, then using the theorem "for prime $$p$$, if $$b$$ is a primitive root mod $$p$$, then either $$b$$ or $$b+p$$ is a primitive root mod $$p^2$$", I find 2 and 5 are primitive root mod 9. These will stay as primitive root mod $$3^n$$ for $$n>2$$, but I do not know how to find the others.

To be more precise, I know 2,11,20,5,14,23 will be all primitive roots modulo 27, how could I come up with those? Also, I notice $$11 = 2+1\cdot 9$$ and $$20 = 2+2\cdot 9$$, does that mean they can be found as soon as I find 2 is a primitive root modulo 27? Why?

Thank you very much in advance.

• See for a similar question, also for $n=3^3=27$, here. Commented Apr 20, 2023 at 19:19
• If you know that $2$ is a primitive root mod $27$, then all others are $2^k$ for $\gcd(k,\phi(27))=1$.
– lhf
Commented Apr 20, 2023 at 19:37
• @DietrichBurde, thank you for the reference!
– hmm1
Commented Apr 20, 2023 at 20:32
• @lhf, thank you. I think your suggestion makes use of the fact that "if $g$ has order $d$, then $ord(g^i) = d/\gcd(i,d)$". That works! I have asked this before and the explanation is "for $j\geq 0$, $2+9j$ is a primitive root mod 9, so that 2,11,20 will be primitive root mod 27". I do not quite understand the statement, but again thank you for your answer.
– hmm1
Commented Apr 20, 2023 at 20:33

It sounds like the question you're asking is: if $$g$$ is a primitive root modulo $$p^2$$ (for some odd prime $$p$$), then why do we automatically know that $$g$$, $$g+p^2$$, and $$g+2p^2$$ are primitive roots modulo $$p^3$$?
I think the missing step is: being or not being a primitive root modulo $$q$$ is a property shared by every integer in a residue class modulo $$q$$; in other words, if $$n$$ is a primitive root modulo $$q$$, then so is $$n+kq$$ for every integer $$k$$. The reason this is true is that being a primitive root depends only on the outcome of modular arithmetic (mod $$q$$).
So $$g$$ being a primitive root modulo $$p^2$$ implies that $$g+3^2$$ and $$g+2\cdot3^2$$ are also primitive roots modulo $$p^2$$; thus every one of these integers is also a primitive root modulo $$p^3$$. (So are $$g+3\cdot3^2$$, $$g+4\cdot3^2$$, $$g-3^2$$, and so on; but each of those is congruent modulo $$3^3$$ to one of the known primitive roots, so there's no need to list them separately.)
More generally: Really residue classes, not integers, are primitive roots; and each residue class modulo $$p^2$$ consists of $$p$$ disjoint residue classes modulo $$p^3$$.