2
$\begingroup$

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.

2 Answers 2

4

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

  • 0
    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.2011-10-21
  • 0
    What is the order of the multiplicative group modulo $7^n$? The order of $2$ must divide it.2011-10-22
  • 0
    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$?2011-10-22
  • 0
    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?2011-10-22
  • 0
    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.2011-10-22
3

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

  • 0
    I don't have that book, but thank you for giving a positive answer.2011-10-21
  • 0
    Search "Leveque primitive root" on google. The google books link (first as I write this) links to the right chapter.2011-10-21