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.

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

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

Let us say that,


And that is smallest positive integer (its order).

Then,
Thus, .
Let us assume there is a smaller such as,

Then,

Which contradicts the assumption that was the smallest.

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! :)