# $5^{2^{a-3}} \equiv 1+2^{a-1}\pmod{2^a}$

Here's a tricky question I have in a homework problem:

Via induction, show

$5^{2^{a-3}} \equiv 1+2^{a-1}\pmod{2^a}$

and then deduce that $5\pmod{2^a}$ has order $2^{a-2}$ for $a \ge 3$

Help please I'm so lost with this question!!!

-
I'm sure this has been covered here many times. Hint: $$5^{2^{k+1}}-1=(5^{2^k}-1)(5^{2^k}+1).$$ The latter factor is always even but never divisible by four. – Jyrki Lahtonen Nov 5 '12 at 18:54
Are you sure you copied this correctly: $$5^{2^{a-3}} \equiv 1+2^{a-1}\pmod{2^{a-1}}$$ Because that seems equivalent to $$5^{2^{a-3}} \equiv 1\pmod{2^{a-1}}$$ – Thomas Andrews Nov 5 '12 at 18:56

Let $a^{2^b}=1+c2^{b+2}$ where $a=2d+1$ is odd
So,$a^{2^{b+1}}=(a^{2^b})^2=(1+c2^{b+2})^2=1+c2^{b+3}+2^{2(b+2)}c^2\equiv1\pmod {2^{b+3}}$ if $2b+4\ge b+3$ or if $b\ge 0$
Now, for $b=1,a^{2^1}=a^2=(2d+1)^2=1+8\frac{d(d+1)}2\equiv 1\pmod{2^{1+2}}$--> this is base case for the induction.
So, using induction we can prove the proposition for any odd number with the power of $2>1$.