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

    Dick

    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

    Dick

    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