Congruence Proof: Prove a=b if a is congruent to b for every prime p

  • Thread starter dancergirlie
  • Start date
  • Tags
    Proof
In summary, the conversation discusses how to prove that if a and b are integers and a is congruent to b(mod p) for every positive prime p, then a=b. The conversation also mentions the properties of divisibility by primes and how to show that zero is the only number with the given property.
  • #1
dancergirlie
200
0

Homework Statement



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

Homework 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)


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 don't 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 =)
 
Physics news on Phys.org
  • #2
It looks like you have that (a-b) is divisible by ALL primes. How many numbers have that property?
 
  • #3
I think only zero has that property since all numbers divide zero. However, how am I supposed to show that in my proof?
 
  • #4
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
ok, i'll do that, thanks so much for the help!
 

Related to Congruence Proof: Prove a=b if a is congruent to b for every prime p

1. What is congruence proof?

Congruence proof is a mathematical method used to prove that two numbers, known as the bases a and b, are equal if they are congruent to each other for every prime number p. This method is commonly used in number theory and algebra to demonstrate the relationship between two numbers.

2. How does congruence proof work?

Congruence proof works by showing that the remainders of a and b when divided by any prime number p are equal. This is done by using the fundamental theorem of arithmetic, which states that every integer can be uniquely factored into a product of primes. By showing that the prime factorization of a and b are the same, we can prove that they are equal.

3. What is the importance of using prime numbers in congruence proof?

Prime numbers are important in congruence proof because they are the building blocks of all other numbers. Every integer can be expressed as a product of prime numbers, and by using the fundamental theorem of arithmetic, we can prove the congruence of two numbers. Additionally, using prime numbers ensures that the proof is valid for all integers, not just a specific set.

4. Can congruence proof be used to prove other types of equations?

Yes, congruence proof can be used to prove other types of equations, such as quadratic equations or polynomial equations. However, the method may be more complex and may require additional techniques, such as modular arithmetic. Congruence proof is most commonly used to prove relationships between two numbers, but it can be adapted for other types of equations.

5. Are there any limitations to using congruence proof?

Like any mathematical proof, there are limitations to using congruence proof. It can only be used to prove relationships between two numbers and may not be applicable to more complex equations. Additionally, it may not be the most efficient method for proving certain types of equations. It is important to consider the specific problem and determine if congruence proof is the best approach.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
988
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top