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