$5^{2^{n-3}}\not \equiv -1 \mod 2^n$ for any $n\geq 3$

Question

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.

Answer 1

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.

Answer 2

mod $2^n:$ $5^{2^{n-3}}\equiv$ $(-3,-7,-15,-31,\cdots)$ for $n=(3,4,\cdots)$

The remainders follow the pattern $-2^k+1$ where $k=2,3,\cdots$ and therefore will never be $-1$

Answer 3

Let's try induction:

$n = 3$:

$6\equiv 6 mod 8$

Hence true for $n=3$

Assume that: $5^{2^{n-3}} + 1 \not\equiv 0 mod 2^{n}$

Required to prove: $5^{2^{n-2}} + 1 \not\equiv 0mod2^{n+1}$

Suppose for contradiction that $5^{2^{n-2}} + 1 \equiv 0mod2^{n+1}$

$\Rightarrow 5^{2^{n-2}} + 1 = k2^{n+1}$ for some $k \in \mathbb{Z}$

$\Rightarrow(5^{2^{n-3}})^{2} + 1 = 2k2^{n}$

$\Rightarrow (5^{2^{n-3}})^{2} \equiv -1mod2^{n}$

Ok I'm stuck at this point, if anyone sees how to finish this please feel free to edit.

Answer 4

Mod $2^n$, powers reduce mod $\phi(2^n)=2^{n-1}$.
$$ 5^4*5^{2^{n-3}}=5^{2^{n-1}}\equiv1\pmod{2^n}$$ If $5^4(-1)\equiv1\pmod{2^n}$, then $0\equiv5^4+1\pmod{2^n}$, i.e. $2^n\mid5^4+1=2*313$.

If you're not sure why powers reduce in the way cited, check out some proofs of Fermat's Little Theorem and the definition of Euler's $\phi$ function.

Answer 5

We use a proof by contradiction to prove a more general statement.

Suppose that $5^k \equiv -1 \mod 2^n$ for any natural $k$ and any natural $n \geq 2$. Then we have that $2^n \mid 5^k+1$, so certainly $4 \mid 5^k+1$, or $5^k \equiv -1 \mod 4$.

However, for any $k$ we have $5^k \equiv 1^k =1 \mod 4$, contradiction.

Your statement follows with $k=2^{n-3}$.

Answer 6

prove $5^{2^{n-3}}\not\equiv -1$ mod $2^{n}$, $n\ge 3$

for $n=3$:$\space 2^3=8\nmid 5^{2^0}+1=6$

for $n=4$:$\space 2^4=16\nmid 5^{2^1}+1=26$

for $n\ge 5$: let $m=n-3$:$\space$show that $5^{2^m}\not\equiv -1$ mod $2^{m+3}$, $m\ge 2$

that is, show $2^m2^3\nmid 5^{2^m}+1$

$2^m\nmid 5^{2^m}+1\Longrightarrow 2^m2^3\nmid 5^{2^m}+1$

$5^{2^m}+1=(4+1)^{2^m}+1=\sum_{k=0}^{2^m}{{2^m}\choose k}4^k1^{2^m-k}+1\space$ per binomial theorem.

$=1+{{2^m}\choose 1}4+{{2^m}\choose 2}4^2+\dots +{{2^m}\choose {2^m-1}}4^{2^m-1}+4^{2^m}+1$

$=1+\underbrace{{{2^m}\choose 1}4+{{2^m}\choose 2}4^2+\dots +{{2^m}\choose {2^m-1}}4^{2^m-1}+2^{2^m}2^{2^m}}_{divisible\space by\space 2^m}+1$

$=2^mk+2$ which is not divisible by $2^m$ for $m\gt 1$

therefore $5^{2^m}\not\equiv -1$ mod $2^{m+3}$, $m\ge 2$ and thus $5^{2^{n-3}}\not\equiv -1$ mod $2^{n}$, $n\ge 3$