Does there exist a prime $p \geq 7$ such that the order of $4$ in the multiplicative group of units in $\mathbb{Z}/p^n$ is odd for every positive integer $n$?

It would be nice if $7$ was already an example. I computed the order of $4$ modulo $7^n$ for $n=1,2,\ldots,12$ and it came out odd, but that's not particularly compelling evidence I guess.


Hint: $4$ is always a square modulo $p^n$. What can you say about the order of its square root (whatever that is) modulo $7^n$? What does this imply about the order of $4$?

  • $\begingroup$ I don't understand... If $k$ is the order of $4$ modulo $7^n$, then $2^{2k}=1$ modulo $7^n$. Hence the order of $2$ modulo $7^n$ divides $k$ I guess. Could you maybe give a little more information? I know little to no number theory. $\endgroup$ – Mike F Oct 21 '11 at 23:51
  • $\begingroup$ What is the order of the multiplicative group modulo $7^n$? The order of $2$ must divide it. $\endgroup$ – Henning Makholm Oct 22 '11 at 1:20
  • $\begingroup$ Okay well the numbers among $1,2,3,\ldots,7^n$ not relatively prime to $7^n$ are just $1 \cdot 7,2 \cdot 7, 3 \cdot 7, \ldots, 7^{n-1} \cdot 7$ so the order of the group is $7^n - 7^{n-1} = 6 \cdot 7^{n-1}$... which means the order of $2$ in the group has one of the forms $7^r,2\cdot 7^r, 3 \cdot 7^r$ or $6 \cdot 7^r$ for appropriate $r$? $\endgroup$ – Mike F Oct 22 '11 at 2:17
  • $\begingroup$ Yes -- in particular it's either odd or 2 times an odd number. What can you say about the order of $4$ in each of those cases? $\endgroup$ – Henning Makholm Oct 22 '11 at 2:18
  • $\begingroup$ Ohhhhhhh I had it backward in my first comment. It's the order of $4$ which should divide the order of $2$! So yes, if the $2$ has odd order, then so does $4$. If $2$ has order $2k$ where $k$ is odd, then $4^k = 2^{2k} = 1$ modulo $7^n$, so the order of $4$ divides the odd number $k$ and is odd. Thanks, it makes sense now. $\endgroup$ – Mike F Oct 22 '11 at 2:39

Use Theorem 4.4 in Leveque, Fundamentals of Number Theory:

"Suppose $p$ is a prime and $p \nmid a$. Let $\mathrm{ord}_p a = t$ and let $p^z$ be [the exact power of $p$ dividing $a^t-1$]. Then if $p>2$ or $z>1$,

$$ t_n = \mathrm{ord}_{p^n} a = t, \quad \text{for $n \leq z$}$$


$$ t_n = t p^{n-z}, \quad \text{for $n \geq z$}"$$

So if the order of $4$ modulo $p$ is odd, then the order of $4$ is odd modulo every power of $p$.

  • $\begingroup$ I don't have that book, but thank you for giving a positive answer. $\endgroup$ – Mike F Oct 21 '11 at 23:53
  • $\begingroup$ Search "Leveque primitive root" on google. The google books link (first as I write this) links to the right chapter. $\endgroup$ – Barry Smith Oct 21 '11 at 23:54

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.