<s>[INST] $5^{2^{n-3}}\not \equiv -1 \mod 2^n$ for any $n\geq 3$ I am in the middle of solving an abstract algebra problem and I have narrowed it down to showing that
$$5^{2^{n-3}}\not \equiv -1 \mod 2^n \quad \text{ for any } \quad n\geq 3. $$
I am not very good with congruences. I know this is equivalent to showing that $5^{2^{n-3}}+1\not \equiv 0\mod 2^n$, i.e., $5^{2^{n-3}}$ is not a multiple of $2^n$, but I am still not sure how to prove this.
Thank you for your help.
 [/INST] First we check this for $n = 3$. We have $5 \not\equiv -1 \mod{8}$. Thus let $n \geq 4$ and suppose $5^{2^{n - 3}} \equiv -1 \mod{2^n}$ so $5^{2^{n - 3}} + 1 = a2^n$ for some $a \in \mathbb{Z}$. We then have $5^{2^{n - 3}} + 1 = 4a2^{n - 2}$ with $2^{n - 2} \in \mathbb{Z}$ since $n \geq 4$ so $5^{2^{n - 3}} \equiv -1 \mod{2^{n-2}}$. We have $\phi(2^{n - 2}) = 2^{n - 2} - 2^{n - 3} = 2^{n - 3}$ and $\gcd(5,2^{n-2}) = 1$. But then by Euler's Theorem
\begin{align}
-1 \equiv 5^{2^{n - 3}} \equiv 5^{\phi(2^{n - 2})} \equiv 1 \mod{2^{ n - 2}}
\end{align}
which is a contradiction since $-1 \equiv 1 \mod{q}$ iff $q = 2$, and since $n \geq 4$ we have $2^{n - 2} \neq 2$. Thus the supposition was false and $5^{2^{n - 3}} \not\equiv - 1 \mod{2^n}$ for $n \geq 4$. Combining this with our base case we have the result holding for $n \geq 3$ as required.
</s>