Can someone explain this to me?

  • #1

Homework Statement


If gcd(a,m) > 1, then ax [itex]\equiv[/itex] 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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619

Homework Statement


If gcd(a,m) > 1, then ax [itex]\equiv[/itex] 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.
 
  • #3
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,562
5,969
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.
 

Related Threads on Can someone explain this to me?

  • Last Post
Replies
2
Views
832
Replies
1
Views
1K
Replies
2
Views
640
Replies
2
Views
458
Replies
2
Views
2K
Replies
5
Views
811
Replies
3
Views
4K
Replies
0
Views
2K
Replies
5
Views
1K
Replies
4
Views
1K
Top