Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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. – Mike F Oct 21 '11 at 23:51
What is the order of the multiplicative group modulo $7^n$? The order of $2$ must divide it. – Henning Makholm Oct 22 '11 at 1:20
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$? – Mike F Oct 22 '11 at 2:17
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? – Henning Makholm Oct 22 '11 at 2:18
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. – 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$.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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