1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Congruence proof

  1. Feb 3, 2009 #1
    1. The problem statement, all variables and given/known data

    If a and b are integers and a is congruent to b(mod p) for every positive prime p, prove that a=b

    2. Relevant equations

    p divides (a-b) if a is congruent to b modulo p
    if p divides ab then p divides a or p divides b (if p is prime)

    3. The attempt at a solution

    Suppose a is congruent to b(mod p)
    so, p divides (a-b)
    which means, there exists an integer c so that (a-b)=pc
    where a=pc+b
    (pc+b) is congruent to b(mod p)
    so, p divides (pc+b-b)= (pc)
    p divides (pc)

    This is where i get stuck, i dont know if i should say since p is prime, p divides p or p divides c, or i don't know if i did this completely wrong. Any help would be appreciated =)
  2. jcsd
  3. Feb 3, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    It looks like you have that (a-b) is divisible by ALL primes. How many numbers have that property?
  4. Feb 3, 2009 #3
    I think only zero has that property since all numbers divide zero. However, how am I supposed to show that in my proof?
  5. Feb 3, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    It's pretty easy to show zero is the only number with that property. Suppose you have a nonzero number n which is divisible by all primes. But you can always find a prime p>|n| (why?). So p doesn't divide n (why?). That's a contradiction. So there is no such n.
  6. Feb 3, 2009 #5
    ok, i'll do that, thanks so much for the help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook