Prove that the order of 5 modulo 2^k is 2^(k-2)

[Fermat1]

Prove that the order of 5 modulo $2^k$ is $2^{k-2}$ where $k$ is at least 3.
I thought probably induction is best bet.

For k=3 we can verify.

So for inductive step we need to show the order of 5 modulo $2^{k+1}$ is $2^{k-1}.

 

[Nono713]

Prove that the order of 5 modulo $2^k$ is $2^{k-2}$ where $k$ is at least 3.
I thought probably induction is best bet.

For k=3 we can verify.

So for inductive step we need to show the order of 5 modulo $2^{k+1}$ is $2^{k-1}.

Induction will work. Try to use the fact that $a \equiv b \pmod{n} ~ \iff ~ a = b + kn$ for some $k \in \mathbb{Z}$. Applying this to the congruences obtained by the knowledge that $5$ has order $2^{k - 2}$ modulo $2^k$, you can derive equivalent congruences modulo $2^{k + 1}$ (hint: square both sides) and can then conclude.

Remember that $a$ has order $m$ modulo $n$ if and only if $m$ is the smallest positive integer such that $a^m \equiv 1 \pmod{n}$, so make sure you prove this carries over modulo $2^{k + 1}$, i.e. make sure show that the order of $5$ modulo $2^{k + 1}$ is exactly $2^{k - 1}$. Be rigorous.

 

[Fermat1]

Induction will work. Try to use the fact that $a \equiv b \pmod{n} ~ \iff ~ a = b + kn$ for some $k \in \mathbb{Z}$. Applying this to the congruences obtained by the knowledge that $5$ has order $2^{k - 2}$ modulo $2^k$, you can derive equivalent congruences modulo $2^{k + 1}$ (hint: square both sides) and can then conclude.

Remember that $a$ has order $m$ modulo $n$ if and only if $m$ is the smallest positive integer such that $a^m \equiv 1 \pmod{n}$, so make sure you prove this carries over modulo $2^{k + 1}$, i.e. make sure show that the order of $5$ modulo $2^{k + 1}$ is exactly $2^{k - 1}$. Be rigorous.

I got $5^{2^{k-1}}=5^2^{k-2}5^2^{k-2}$ mod($2^k$) but how do I get it mod $2^{k+1}$?

Also how to prove it is the smallest?

 

[Fermat1]

Induction will work. Try to use the fact that $a \equiv b \pmod{n} ~ \iff ~ a = b + kn$ for some $k \in \mathbb{Z}$. Applying this to the congruences obtained by the knowledge that $5$ has order $2^{k - 2}$ modulo $2^k$, you can derive equivalent congruences modulo $2^{k + 1}$ (hint: square both sides) and can then conclude.

Remember that $a$ has order $m$ modulo $n$ if and only if $m$ is the smallest positive integer such that $a^m \equiv 1 \pmod{n}$, so make sure you prove this carries over modulo $2^{k + 1}$, i.e. make sure show that the order of $5$ modulo $2^{k + 1}$ is exactly $2^{k - 1}$. Be rigorous.

sorry i can't get my code to work. Hopefully you can work it out

 

[mathbalarka]

$$5^{2^{k-1}} = 5^{2^{k-2} \cdot 2} = \left ( 5^{2^{k-2}} \right)^2$$

What is $5^{2^{k-2}}$ modulo $2^k$ by hypothesis? Write it up as $5^{2^k} = a + b \cdot 2^k$. Substitute in above. What do you get?

 

[Fermat1]

$$5^{2^{k-1}} = 5^{2^{k-2} \cdot 2} = \left ( 5^{2^{k-2}} \right)^2$$

What is $5^{2^{k-2}}$ modulo $2^k$ by hypothesis? Write it up as $5^{2^k} = a + b \cdot 2^k$. Substitute in above. What do you get?

yes I get about the inductive hypothesis but how do I move to mod $2^{k+1}$?

 

[mathbalarka]

Did you even try out what I suggested?

$$5^{2^{k-1}} = \left ( 5^{2^{k-2}} \right) = \left ( 1 + 2^k \cdot l \right )^2 = 1 + 2^{k+1} \cdot l + 2^{2k} \cdot l^2$$

Which is 1 modulo $2^{k+1}$. I'd prefer you to carefully read over suggestions before asking questions. It's better to figure stuff out by yourself rather than asking people to do it for you :)

 

[Fermat1]

Did you even try out what I suggested?

$$5^{2^{k-1}} = \left ( 5^{2^{k-2}} \right) = \left ( 1 + 2^k \cdot l \right )^2 = 1 + 2^{k+1} \cdot l + 2^{2k} \cdot l^2$$

Which is 1 modulo $2^{k+1}$. I'd prefer you to carefully read over suggestions before asking questions. It's better to figure stuff out by yourself rather than asking people to do it for you :)

ok thanks, I've now shown that. I'm struggling to show that it is in fact the order. I assume that $5^{2^{k-1}}=1+am$ for some $m$ less than $5^{2^{k+1}}$ and try and get a contradiction but I'm stuck trying that

 

[Euge]

ok thanks, I've now shown that. I'm struggling to show that it is in fact the order. I assume that $5^{2^{k-1}}=1+am$ for some $m$ less than $5^{2^{k+1}}$ and try and get a contradiction but I'm stuck trying that

Hi Fermat,

I suggest showing (by induction on $k$) that $5^{2^{k-3}} \equiv 1 + 2^{k-1} \pmod{2^k}$ for all $k \ge 3$. In particular, this justifies $5^{2^{k-3}} \not\equiv 1 \pmod{2^k}$ for all $k \ge 3$. Assuming this assertion, if $k\ge 3$,

$$5^{2^{k-2}} = (5^{2^{k-3}})^2 \equiv (1 + 2^{k-1})^2\pmod{2^k} = 1 + 2^k + 2^{2k-2}\pmod{2^k} = 1 \pmod{2^k}.$$

The last congruence follows since $2k - 2 \ge k + 1$ for $k \ge 3$. Therefore, $5$ has order $2^{k-2}$ modulo $2^k$ for all $k\ge 3$.