2
$\begingroup$

Given $n>2$, by calculation or otherwise deduce that $5^{2^{n-3}} \neq -1 \pmod {2^n}$

Note:The problem arose when I tried to deduce $\langle5\rangle \cap \langle2^n-1\rangle=\{1\}$ in the group $\mathbb{Z}^{*}_{2^n}$, I have showed $\operatorname{ord}(5)=2^{n-2}$

  • 0
    $a \not\equiv b$2012-08-14

1 Answers 1

3

We show by induction that if $n \ge 3$, then $5^{2^{n-3}}\equiv 1+2^{n-1}\pmod{2^n}$. And it is clear that $1+2^{n-1}\not\equiv -1 \pmod{2^n}$ if $n \ge 3$.

The result holds when $n=3$. Now we do the induction step. Suppose that we know that for a certain $k$, we have $5^{2^{k-3}}\equiv 1+2^{k-1}\pmod{2^k}$. We show that $5^{2^{k-2}}\equiv 1+2^{k}\pmod{2^{k+1}}$.

By assumption, $5^{2^{k-3}}=1+2^{k-1} +t2^k$ for some integer $t$. Square both sides, and simplify modulo $2^{k+1}$. We get $5^{2^{k-2}}\equiv (1+2^{k-1})^2=1+2^k+2^{2k-2}\pmod{2^{k+1}}.$ But $2^{2k-2}$ is divisible by $2^{k+1}$, since $2k-2 \ge k+1$ when $k \ge 3$. The result follows.