I'm trying to prove using induction that $5^{2^{x-2}} \equiv 1 + 2^x \pmod{2^{x+1}}$
So far, I have:
- Base case: $x = 2, 5 \equiv 5 \pmod{8}$, It is true. $x = 3, 25 \equiv 9 \pmod{16}$, It is true.
- Inductive step: let $x = n$ Assume $5^{2^{n-2}} \equiv 1 + 2^n \pmod{2^{n+1}}$ is true, so I need proof, that $5^{2^{n-1}} \equiv 1 + 2^{n+1} \pmod{2^{n+2}}$.
I tried express new equation through the old. But I am getting errors.
$$ \begin{align*}\begin{split} 5^{2^{n-1}} &= (5^{2^{n-2}})^2 \\ &= (1 + 2^{n}+2^{n+1}a)^2 \\ &= 1+ (2^n)^2+(2^{n+1}a)^2+ 2\cdot2^n+2\cdot2^{n+2}a+2\cdot2^{n}\cdot2^{n+1}a\\ &=1+2^{n+1}+2^{n+2}b \end{split}\end{align*}$$