Can someone explain this to me?

[countzander]

Homework Statement

If gcd(a,m) > 1, then ax \equiv 1 (mod m) is impossible.

Homework Equations

N/A

The Attempt at a Solution

There is no solution per se, only an explanation. I know that m would have to divide ax and 1. Since only 1 divides 1, the statement is impossible. But that doesn't explain how the condition, gcd(a,m) > 1, is relevant. Furthermore, if the gcd(a,m) were 1, the statement would be true. Why is it that when the gcd > 1 that the congruence is impossible?

 

[Dick]

Homework Statement

If gcd(a,m) > 1, then ax \equiv 1 (mod m) is impossible.

Homework Equations

N/A

The Attempt at a Solution

There is no solution per se, only an explanation. I know that m would have to divide ax and 1. Since only 1 divides 1, the statement is impossible. But that doesn't explain how the condition, gcd(a,m) > 1, is relevant. Furthermore, if the gcd(a,m) were 1, the statement would be true. Why is it that when the gcd > 1 that the congruence is impossible?

No, m doesn't have to divide ax and 1. m would have to divide ax-1. If gcd(a,m)=k then k would divide m and a. Think this through again.

 

[countzander]

Yes, m most certainly does divide ax and 1. It's a modular congruence relation. Because m divides the difference it must also divide the minuend and the subtrahend. At least, that should be true. But for some reason, the gcd's being greater than 1 prevents that because the congruence relationship is impossible.

Can no one explain this?

 

[haruspex]

Yes, m most certainly does divide ax and 1. It's a modular congruence relation. Because m divides the difference it must also divide the minuend and the subtrahend.

7 divides 10-3. That doesn't mean 7 divides 10 and 3.
m has a factor in common with a, but bit need not divide a.