# Can someone explain this to me?

1. Apr 11, 2013

### countzander

1. The problem statement, all variables and given/known data
If gcd(a,m) > 1, then ax $\equiv$ 1 (mod m) is impossible.

2. Relevant equations
N/A

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

2. Apr 11, 2013

### Dick

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.

3. Apr 11, 2013

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

4. Apr 11, 2013

### haruspex

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.