1
$\begingroup$

How to show that $\bar{a}^t \equiv (\bar{a}^ta^t)(a^t)$? The idea is to show that $ord_m a= ord_m \bar{a}$. It is in the following sequence of modulo's?

$ord_m a$ exists => $a^t \equiv 1 \pmod n$. Then $\bar{a}^t \equiv (\bar{a}^ta^t)(a^t) \equiv (\bar{a}a)^t a^t \equiv 1^t \cdot 1 \equiv 1 \pmod n$.

Another possibility is that it is an error there. You can check whole proof from http://www.aw-bc.com/rosen/Rosen_NumTheory5_SSM.pdf -> 9.1.9. at page 79. Because $\bar{a}$ is the inverse of a modulo m <=> $a\bar{a} \equiv 1 \pmod n$.

2 Answers 2

0

I think that the author first assumes that $a^t\equiv 1\pmod n$. Given this, then $x=x\cdot1\equiv xa^{t}$ for any integer (or residue class) $x$. Here $x=\overline{a}^t$.

0

You’ve misunderstood the logic of the argument. Remember, you’re trying to prove that $\operatorname{ord}_na=\operatorname{ord}_n\bar a$. (Note that you wrote subscripts $m$ where you need $n$.) Start by assuming that $\operatorname{ord}_na=t$. Then $a^t\equiv 1\pmod n$, so the calculation $\bar a^t \equiv \bar a^t\cdot 1\equiv\bar a^t a^t\equiv(\bar a^t a^t)\cdot 1 \equiv (\bar a^t a^t)a^t \equiv (\bar aa)^t a^t \equiv 1^t \cdot 1^t\pmod n$ is fine, albeit unnecessarily long; it could be shortened to $\bar a^t \equiv \bar a^t\cdot q \equiv \bar a^ta^t\equiv(\bar a a)^t \equiv 1^t \equiv 1\pmod n\;.$

At any rat this shows that $\bar a^t\equiv 1\pmod n$, which in turn implies that $\operatorname{ord}_n\bar a\le t$, i.e., that $\operatorname{ord}_n\bar a\le \operatorname{ord}_na$. Now use the same argument, but with $a$ and $\bar a$ interchanged, to show that $\operatorname{ord}_na\le \operatorname{ord}_n\bar a$, and conclude that $\operatorname{ord}_n\bar a = \operatorname{ord}_na$.