Solving Congruences: Proving a=b

  • Context: Graduate 
  • Thread starter Thread starter ninjagod123
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the mathematical statement that if \( a \equiv b \mod p \) for all primes \( p \), then it follows that \( a = b \). Participants explore the implications of this congruence relation and the conditions under which it holds, focusing on the nature of divisibility by primes.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant suggests that if \( a - b \) is divisible by all primes \( p \), then it must be zero, questioning how to formally express this idea.
  • Another participant notes that every nonzero integer can only be divisible by a finite number of primes, implying a limitation on the divisibility of \( a - b \).
  • A further contribution states that if \( a > b \), then \( a - b \) is positive, and there exists a prime \( p > a - b \) that cannot divide \( a - b \), leading to the conclusion that \( a \neq b \mod p \). This reasoning is mirrored for the case when \( b > a \).

Areas of Agreement / Disagreement

Participants express differing views on the implications of divisibility by primes, with some proposing that \( a - b \) must be zero, while others challenge this by discussing the limitations of divisibility by an infinite set of primes. The discussion remains unresolved regarding the formal proof of the initial statement.

Contextual Notes

Participants highlight the assumption that \( a - b \) must be zero if it is divisible by all primes, but this leads to questions about the nature of divisibility and the infinite nature of primes, which are not fully resolved.

ninjagod123
Messages
7
Reaction score
0
Show that if a [tex]\equiv[/tex] b mod p for all primes p, then a = b.
 
Physics news on Phys.org
Well, a - b must be divisible by all primes p. What is the only way for this to happen?
 
JSuarez said:
Well, a - b must be divisible by all primes p. What is the only way for this to happen?

Oh hmmm...

The only way is if (a - b) is zero. How would I formally write this up? I guess a - b can't be the product of all primes?
 
Every nonzero integer can only be divisible by a finite number of primes.
 
ninjagod123 said:
I guess a - b can't be the product of all primes?

In a sense, that's what 0 is. It's the "infinity" of the divisibility relation.
 
If [itex]a> b[/itex] then a- b is a positive number. Since there are an infinite number of primes, there exist a prime, p> a- b. Then p cannot divide a- b so [itex]a\ne b (mod p)[/itex].

If [itex]b> a[/itex] just use b- a instead of a- b.
 

Similar threads

Undergrad ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K
Undergrad Proof regarding congruence relation
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
MHB About a variant of the Chinese Remainder Theorem
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad ##(A/\mathfrak{a})_{\mathfrak{p}/\mathfrak{a}}## and its isomorphism?
  • · Replies 31 ·
2
Replies
31
Views
3K
Verify that ## x\equiv a^{p-2}b\pmod {p} ## is a solution
  • · Replies 6 ·
Replies
6
Views
2K
[IntroNumTheory] Determining the remainder by using congruence
  • · Replies 1 ·
Replies
1
Views
1K
MHB Solving Congruences with Polynomials: A Prime Challenge
  • · Replies 5 ·
Replies
5
Views
3K