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!

Discrete Math - a modulus proof

  1. Sep 15, 2008 #1
    1. The problem statement, all variables and given/known data

    I have to prove the following claim.

    Claim: For any positive integers m and n, m and n both greater than 1, if n|m and a≡b(mod m), then a≡b(mod n).


    2. Relevant equations

    n/a


    3. The attempt at a solution

    so i first changed each equation (ex: a≡b(mod m)) to a=b+qm and a=b+qn

    I figured in these forms I could show that the equations are equal.

    so I eventually get (a-b)/q=m or =n respectively. So I believe this shows their equality, but i am completely unsure because it won't always work I don't think. I need to also show that n|m. So tired dividing the m=(a-b)/q by the n= equation and of course I just get 1...

    To be completely honest I am not quite sure how to prove this. I am not quite familiar with the mod function and I am incredibly weak with proofs. If anyone can give me insight into solving this problem I would great appreciative.

    also note that this should be able to be done with a direct proof.

    thanks!
     
  2. jcsd
  3. Sep 15, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    a=b(mod m) means m|(a-b). a=b(mod n) means n|(a-b). If n|m what can you conclude from this?
     
  4. Sep 15, 2008 #3
    I guess you could conclude that (m|(a-b)) / (n|(a-b)). Or I guess that's like m|n? Actually I'm not really sure. I'm not sure if that's correct. If it is, I'm not really sure if that proves the statement. If m|n is true, does that mean they're the same integer? In which case I assume that would prove it.
     
  5. Sep 15, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    m|(a-b) and n|(a-b) are true/false statements. You can't DIVIDE them. Think about this. If a|b and b|c then a|c, right?
     
  6. Sep 15, 2008 #5
    Right, i mean that makes sense, but that's just reiterating the claim isn't it?

    If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c.

    I think that there is some constant k so that kn=m? Then in this case, because they're modular, they come up with the same answer. Is that any more correct?
     
  7. Sep 16, 2008 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. I just really didn't like (m|(a-b)) / (n|(a-b)). Didn't make much sense to me. Maybe it did to you.
     
    Last edited: Sep 16, 2008
  8. Sep 16, 2008 #7
    I see, but this is where my weak point is. I'm not sure how I write a proof for that.
     
  9. Sep 16, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    "If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c." That's the basis of the proof. Can you just flesh that out into a full proof? Start with "if n|m and a≡b(mod m)" and conclude with "then a≡b(mod n)".
     
  10. Sep 16, 2008 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    If a= b mod m, then m divides a- b so a-b= km for some integer k. If n divides m then m= pn for some integer p. Put those together to get that a-b= ?n.
     
  11. Sep 16, 2008 #10
    alright, thanks you two. Hopefully that'll help. I'll let you know if I have any further questions. Thanks! :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Discrete Math - a modulus proof
  1. Discrete Math Proof (Replies: 3)

  2. Discrete Math Proof (Replies: 2)

  3. Discrete Math Proof (Replies: 4)

Loading...