3
$\begingroup$

if $3^k \equiv \ 1\pmod{2^n}$ then $2^{n-2} | k$. I got this Number Theory problem and I'm stuck. The solution has to be proven without the use of Hensel's Lemma, and might require the LTE lemma. But I'm not familiar with those tools.

  • 0
    A near duplicate of [this question.](http://math.stackexchange.com/q/95808/11619) The answers given there work here as well with the minor exception of $n=2$.2012-06-20

1 Answers 1

2

Make a separate calculation for $n=2$ and $n=3$.

We will prove that if $n \ge 4$, then $3^{2^{n-3}}\equiv 1+2^{n-1} \pmod{2^n}.\tag{$1$}$
This implies that the order of $3$ modulo $2^n$ is greater than $2^{n-3}$. Since the order of $3$ divides $\varphi(2^n)$, it is at least $2^{n-2}$. And since $3^k\equiv 1\pmod{2^n}$, the order of $3$ modulo $2^n$ must divide $k$. It follows that $2^{n-2}$ divides $k$.

The proof of $(1)$ is by induction on $n$. The base case $n=4$ is easy to verify, since $3^{2^1}\equiv 1+8\pmod{16}$.

Suppose now that $3^{2^{n-3}}\equiv 1+2^{n-1} \pmod{2^n}$. So $3^{2^{n-3}}=1+2^{n-1}+q2^n$ for some integer $q$. Square both sides. On the left we get $3^{2^{n-2}}$. On the right, we get $1+2^n$ plus terms divisible by $2^{n+1}$. This completes the induction step.