3
$\begingroup$

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!!!

  • 1
    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}}$2012-11-05

1 Answers 1

1

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