# Can someone explain this to me?

## Homework Statement

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

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?

Related Calculus and Beyond Homework Help News on Phys.org
Dick
Homework Helper

## Homework Statement

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

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.

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