1
$\begingroup$

If $ab \equiv 1 \pmod {m}$ and if $ord_ma=10$, find $ord_mb^2$.

Could somebody give me a hint? What I know is that $ab \equiv 1 \pmod {m}$ can be used when finding the multiplicative inverse. Would this mean that $10$ is the multiplicative inverse, so $b=10$? If so, what does this tell me, and how does it help me find $ord_mb^2$?

Thanks.

4 Answers 4

0

Hint $ $ Note $\rm\:b \equiv a^{-1} $ so $\rm\, 1 \equiv b^{2n}\! \equiv a^{-2n}\!\iff a^{2n} \equiv 1\iff \color{#C00}{10}\:|\:2n\iff 5\:|\:n,\:$ by $\rm\ ord(a) = \color{#C00}{10}.$

1

If $ord_ma=d, ord_m(a^k)=\frac{d}{(d,k)}$ (Proof @Page#95)

$b\equiv a^{-1}\implies k=-1\implies (d,k)=(d,-1)=1$

So, $ord_mb=d=10$

Now, $ord_m(b^2)=\frac{d}{(d,2)}=\frac{10}{(10,2)}=5$

1

$\newcommand{\ord}{\operatorname{ord}}$No, $\ord_ma=10$ says that $a^{10}\equiv 1\pmod m$, but if $1\le n < 10$, then $a^n\not\equiv 1\pmod m$. That is, $10$ is the smallest positive integer $n$ such that $a^n\equiv 1\pmod m$. Similarly, $\ord_mb^2$ is the smallest positive integer $n$ such that $\left(b^2\right)^n\equiv 1\pmod m$, i.e., such that $b^{2n}\equiv 1\pmod m$.

You know that $ab\equiv 1\pmod m$. Clearly this implies that $(ab)^n\equiv 1\pmod m$ for all $n$, and in particular, $(ab)^{10}\equiv 1\pmod m$. But $1\equiv (ab)^{10}=a^{10}b^{10}\equiv 1\cdot b^{10}\pmod m$, so $b^{10}\equiv 1\pmod m$, and therefore $\left(b^2\right)^5\equiv 1\pmod m$. Thus, $\ord_mb^2\le 5$.

Is it possible that $\ord_mb^2<5$? No: it’s a basic theorem that if $c^n\equiv 1\pmod m$, then $\ord_mc\mid n$. We know that $\left(b^2\right)^5\equiv 1\pmod m$, so $\ord_mb^2\mid 5$. $5$ is prime, so $\ord_mb^2$ must be either $1$ or $5$. If it were $1$, that would mean that $b^2\equiv 1\pmod m$. What would that tell you about $a^2$? And why is that impossible?

0

No, $b\not=10$ in general. What $\mathrm{ord}_m a=10$ tells you is that $a^{10}\equiv 1$ (modulo $m$). We know $ab\equiv 1$. By taking powers on both sides we see $a^kb^k\equiv 1$ for all $k\in\mathbb{N}$.

In particular for $k=10$ we get $b^{10}\equiv 1$ (because $a^{10}\equiv 1$). This shows $\mathrm{ord}_m b \le 10$.

Now we have to show $\mathrm{ord}_m b \ge 10$, so that we can conclude $\mathrm{ord}_m b=10$. So suppose $b^{k}\equiv 1$ would hold for some $k<10$, then it would follow that $a^k\equiv 1$, but this is a contradiction since the order of $a$ is $10 > k$. So $\mathrm{ord}_m b=10$. (What we have shown here also holds in general: the order of $a$ is equal to that of $a^{-1}$.)

This implies $\mathrm{ord}_m b^2=5$.