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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 -> 9.1.9. at page 79. Because $\bar{a}$ is the inverse of a modulo m <=> $a\bar{a} \equiv 1 \pmod n$.

share|cite|improve this question
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|cite|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|cite|improve this answer

Your Answer


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.