Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|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 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 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 Oct 22 '11 at 2:39
add comment

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

share|improve this answer
    
I don't have that book, but thank you for giving a positive answer. –  Mike 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
add comment

Your Answer

 
discard

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.