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

AI Thread Summary
The discussion focuses on proving that the order of 5 modulo \(2^k\) is \(2^{k-2}\) for \(k \ge 3\) using mathematical induction. Participants suggest verifying the base case for \(k=3\) and then establishing the inductive step for \(k+1\). Key techniques involve manipulating congruences and applying properties of orders in modular arithmetic, particularly showing that \(5^{2^{k-1}} \equiv 1 \pmod{2^{k+1}}\). The conversation emphasizes the importance of rigor in proving that \(2^{k-1}\) is indeed the smallest integer satisfying the order condition. The discussion concludes with a successful demonstration of the inductive hypothesis and its implications for the order of 5.
Fermat1
Messages
180
Reaction score
0
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}.
 
Mathematics news on Phys.org
Fermat said:
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.
 
Bacterius said:
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?
 
Bacterius said:
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
 
$$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?
 
mathbalarka said:
$$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}$?
 
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 :)
 
mathbalarka said:
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
 
Fermat said:
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$.
 
Back
Top