Looking at the Wikipedia entry for Primitive roots modulo $n$, I noticed that for some $n$, they came in pairs:

When $n=p^k$ or $2p^k$ and $p\equiv1 \mod{4}$, then $r$ is a primitive root iff $n-r$ is.

I found a proof for this when $n=p$, but not in general. (Exercise online)

Also, when $n=3^k$ or $2(3^k)$ and $k>1$, then $r$ is a primitive root iff $n-r-2$ is.

Finally, when $n=7^k$, then $r$ is a primitive root iff $n-r+1$ is.

Of course, there may be more patterns like these, but these are the ones I've noticed, and I'm sure they've been noticed before, so I'm wondering if anyone can point me in the direction of a general proof here.


Answer for the case $n=p^k$ and $p\equiv 1\ (\ mod\ 4\ )$ :

We have $$(p^k-r)^m\equiv r^m\ (\ mod\ p^k\ )$$ for every even number $m$


$$(p^k-r)^m\equiv -r^m\ (\ mod\ p^k\ )$$

for every odd $m$. If $r$ has order $\phi(p^k)$ and $n-r$ not (or vice versa), then the order of $r$ or the order of $n-r$ must be odd. Denote this order with $o$. Then, we have $r^o\equiv\ -1\ (\ mod\ p^k)$ or $(n-r)^o\equiv -1\ (\ mod\ p^k)$. So, $r$ or $n-r$ has order $2o$. Because of $4|p^{k-1}(p-1)$ , we can conclude $2o\ne \phi(n)$, so neither $r$ nor $n-r$ is a primitve root.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.