Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Ax≡ay (mod m) iff x≡y (mod m/(a,m))

  1. Jan 31, 2010 #1
    note: (a,m)=gcd(a,m)

    Theorem: ax≡ay (mod m) if and only if x≡y (mod m/(a,m))

    And then in the middle of a certain proof later on, my textbook says:
    Suppose (a,m)|b.
    Then BY THE ABOVE THEOREM(?),
    ax≡b (mod m) if and only if (a/(a,m))x ≡ b/(a,m) (mod m/(a,m))?

    But I don't see exactly why the above theorem will give us this result.
    First of all, I don't think on the RHS, b is necessarily a multiple of a.
    Secondly, the theorem says we can divide the LHS and RHS by a (not (a,m)), and divide the modulus by (a,m), NOT a. But in that proof, they divide everything by (a,m) which is not what the theorem says.
    Could someone please show me how to apply the theorem in a way that will lead us to this result? I really don't see how...

    Is it also true that ax≡ay (mod m) if and only if
    (a/(a,m))x ≡ (a/(a,m))y (mod m/(a,m))?

    I'm confused...
    I hope someone can explain this. Any help is much appreciated!
     
    Last edited: Feb 1, 2010
  2. jcsd
  3. Feb 1, 2010 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Apparently you are very confused! Are you clear on what modulo arithmetic itself is? You say " I don't think on the RHS, b is necessarily a multiple of a". Why would you expect it to be? Saying "ax= b (mod m)" does not imply that b is a multiple of 6. Only that ax-b is a multiple of n. For example, if a= 2, b= 5, and m= 7, ax= b (mod m) becomes 2x= 5 (mod 7). That is satisfied by x= 6 because 2(5)= 12= 5+ 7.
     
  4. Feb 1, 2010 #3
    I think you should be aware that if a = 0 or a factor of m, then you cannot divide a out from the equation ax = ay mod m. For instance 0*5 = 0*7 mod 9 because 5 = 7 mod 1 ,i.e. mod (9/(0,9)) = mod (9/9) = mod 1 but 5 <> 7 mod 9
     
    Last edited: Feb 1, 2010
  5. Feb 1, 2010 #4
    I understand what you're saying for sure.

    But the theorem says:
    ax≡ay (mod m) if and only if x≡y (mod m/(a,m)).

    Firstly, our congruence ax≡b (mod m) here is not of the above form, so why is the theorem even applicable?

    Secondly, the theorem doesn't say that we can divide the LHS and RHS and the modulus by (a,m). The theorem says that we can divide the LHS and RHS by "a", and divide the modulus by (a,m).

    I hope this clarifies my quesiton.
     
  6. Feb 1, 2010 #5
    Actually, it is: you just have to write [tex]a=\left(a,m\right)\times a/\left(a,m/right)[/tex] and
    [tex]b=\left(a,m\right)\times b/\left(a,m/right)[/tex].

    And we may assume that b is divisible by (a,m) because, otherwise, the congruence

    [tex]ax\equiv b\left({\rm mod}m)[/tex]

    will not have solutions.
     
  7. Feb 1, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Actually, it is of that form. It's a little confusing because we're using the same variable names for multiple purposes, so let me color them:
    ax=ay (mod m)
    ax=b (mod m)​

    One way to get a match is by assigning
    a = 1
    x = ax
    y = b


    There are lots of trivial modifications you could make to allow you to match the desired form in other ways too.
     
    Last edited: Feb 1, 2010
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Ax≡ay (mod m) iff x≡y (mod m/(a,m))
Loading...