# Is there a prime $p$ such that $4$ has odd order modulo every power of $p$?

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

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

and

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

-
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