1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can someone explain this to me?

  1. Apr 11, 2013 #1
    1. The problem statement, all variables and given/known data
    If gcd(a,m) > 1, then ax [itex]\equiv[/itex] 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. jcsd
  3. Apr 11, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Apr 11, 2013 #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?
     
  5. Apr 11, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted