Prove: If ab congruent to 1 (mod m), then o(a) equals o(b).

• Nov 12th 2006, 03:26 PM
Geoffrey
Prove: If ab congruent to 1 (mod m), then o(a) equals o(b).
So far, all I can figure out is that a and b are units (mod m). Also, a is the inverse of b, and b is the inverse of a. Say o(a) = c and o(b) = d. I want to show that c = d. I am unsure on how to do this.

I also know:
a^c is congruent to 1 (mod m)
b^d is congruent to 1 (mod m)
ab is congruent to 1 (mod m)

...and I'm lost from here on.
• Nov 12th 2006, 03:30 PM
ThePerfectHacker
Quote:

Originally Posted by Geoffrey
So far, all I can figure out is that a and b are units (mod m). Also, a is the inverse of b, and b is the inverse of a. Say o(a) = c and o(b) = d. I want to show that c = d. I am unsure on how to do this.

I also know:
a^c is congruent to 1 (mod m)
b^d is congruent to 1 (mod m)
ab is congruent to 1 (mod m)

...and I'm lost from here on.

What does it mean o(a) and o(b)?
• Nov 12th 2006, 03:32 PM
Geoffrey
o(a) means the order of some integer a in (mod m). In other words, the order is the least positive integer power k such that a^k is congruent to 1 (mod m).
• Nov 12th 2006, 03:52 PM
ThePerfectHacker
Let us say that,
$\displaystyle ab\equiv 1$

And that $\displaystyle a^k\equiv 1$ is smallest positive integer (its order).

Then, $\displaystyle (ab)^k=a^kb^k=b^k \equiv 1$
Thus, $\displaystyle b^k=1$.
Let us assume there is a smaller $\displaystyle j<k$ such as,
$\displaystyle b^j\equiv 1$
Then,
$\displaystyle (ab)^j= a^jb^j\equiv a^j\equiv 1$
Which contradicts the assumption that $\displaystyle k$ was the smallest.
• Nov 12th 2006, 05:09 PM
Geoffrey
I see, so that makes sense. If o(a) is not equal to o(b), there is a contradiction. Thank you so much for your time! :)