# Congruence Proof

• January 20th 2010, 12:20 PM
FatherMike
Congruence Proof
Prove that if m and n are positive integers and if ab ≡ 1 (mod m) and
a^n ≡ 1 (mod m), then b^n ≡ 1 (mod m).

Any help would be greatly appreciated! I am lost with this one but I probably am just missing a very simple step. Thanks!
• January 20th 2010, 01:30 PM
Dinkydoe
Given is $ab\equiv 1$ mod m. This implies that $(ab)^n\equiv 1$ mod m.

Thus if $a^n\equiv 1$ mod n what does this say about $(ab) ^n\equiv b^n$ mod m?
• January 20th 2010, 01:30 PM
Drexel28
Quote:

Originally Posted by FatherMike
Prove that if m and n are positive integers and if ab ≡ 1 (mod m) and
a^n ≡ 1 (mod m), then b^n ≡ 1 (mod m).

Any help would be greatly appreciated! I am lost with this one but I probably am just missing a very simple step. Thanks!

We have that $1\equiv a^n\equiv \left(ab\right)^n=a^nb^n\equiv 1\cdot b^n=b^n\text{ mod }m$