# Congruence inequality

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

-
Notice that if you write (mod 2^n) in LaTeX, it looks like this: $(mod 2^n)$; whereas if you write \pmod{2^n}, it looks like this: $\pmod{2^n}$. Also, instead of $<5>$, you can write $\langle5\rangle$. I did those and a couple of other $\TeX$ improvements. Also you need backslashes in \{5\} in order to get this: $\{5\}$. – Michael Hardy Aug 14 '12 at 1:46
Thanks! Do you also know how to type "not congruent to"? I tried both "\not\equiv" and "\cancel\equiv" but neither works here. – user31899 Aug 14 '12 at 2:06
a\not\equiv b $a\not\equiv b$. Seems to work. Is it possible that you typed a\not\equivb, with no space between \equiv and b? If you do that, it sees "\equivb" rather than "\equiv" and then "b". – Michael Hardy Aug 14 '12 at 2:11
$a \not\equiv b$ – user31899 Aug 14 '12 at 2:14

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.