1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ See for a similar question, also for $n=3^3=27$, here. $\endgroup$
    – Dietrich Burde
    Apr 20 at 19:19
  • $\begingroup$ If you know that $2$ is a primitive root mod $27$, then all others are $2^k$ for $\gcd(k,\phi(27))=1$. $\endgroup$
    – lhf
    Apr 20 at 19:37
  • $\begingroup$ @DietrichBurde, thank you for the reference! $\endgroup$
    – hmm1
    Apr 20 at 20:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – hmm1
    Apr 20 at 20:33

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Great! Thank you so much for clarifying the missing step. I understand now. $\endgroup$
    – hmm1
    Apr 20 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .