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!

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

Have something to add?



Similar Discussions: Congruence proof
  1. Congruence sum proof (Replies: 9)

  2. Congruence proof (Replies: 8)

Loading...