Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.