# Homework Help: Congruence proof

1. Feb 3, 2009

### dancergirlie

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. Feb 3, 2009

### Dick

It looks like you have that (a-b) is divisible by ALL primes. How many numbers have that property?

3. Feb 3, 2009

### dancergirlie

I think only zero has that property since all numbers divide zero. However, how am I supposed to show that in my proof?

4. Feb 3, 2009

### Dick

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.

5. Feb 3, 2009

### dancergirlie

ok, i'll do that, thanks so much for the help!