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

1. ## 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.

2. 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)?

3. 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).

4. Let us say that,
$ab\equiv 1$

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

Then, $(ab)^k=a^kb^k=b^k \equiv 1$
Thus, $b^k=1$.
Let us assume there is a smaller $j such as,
$b^j\equiv 1$
Then,
$(ab)^j= a^jb^j\equiv a^j\equiv 1$
Which contradicts the assumption that $k$ was the smallest.

5. 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!