A Modular Arithmetic Proof Problem

  • Thread starter Thread starter e(ho0n3
  • Start date Start date
  • Tags Tags
    Arithmetic Proof
Click For Summary
SUMMARY

The discussion centers on the proof of a modular arithmetic statement: if \( a \equiv b \mod s \) and \( a \equiv b \mod t \), then \( a \equiv b \mod st \) holds true under the condition that \( s \) and \( t \) are relatively prime integers. The user confirms that if \( s \) divides \( (b-a) \) and \( t \) divides \( (b-a) \), then \( st \) must also divide \( (b-a) \). The conclusion drawn is that the necessary condition for the statement to hold is that \( s \) and \( t \) must be relatively prime.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with divisibility concepts
  • Knowledge of relatively prime integers
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the properties of modular arithmetic in depth
  • Learn about the Euclidean algorithm for finding the greatest common divisor
  • Explore the Chinese Remainder Theorem and its applications
  • Investigate proofs involving divisibility and congruences
USEFUL FOR

Students studying number theory, mathematicians interested in modular arithmetic, and educators teaching concepts of divisibility and congruences.

e(ho0n3
Messages
1,349
Reaction score
0
Homework Statement
Let a, b, s, t be integers with s, t > 0. What conditions must s, t satisfy if the following statement is true:

If a = b (mod s) and a = b (mod t), then a = b (mod st).

The attempt at a solution
If s | a, s | b, t | a and t | b, then st | a and st | b if and only if s, t are relatively prime. This is as far as I've gone. How should I continue?
 
Physics news on Phys.org
The statement is equivalent to s | (b-a) and t | (b-a) -> st | (b-a).
 
Oh, that's right! I completely forgot about that. And by using what I have, I can conclude that s and t must be relatively prime.

Thanks again.
 

Similar threads

U(n) as an External Direct Product
  • · Replies 11 ·
Replies
11
Views
2K
Prove that sup(ST) = sup(S)sup(T)
  • · Replies 7 ·
Replies
7
Views
3K
How should I find ## x_{2}(t) ## for this nonlinear integro-differential equation?
  • · Replies 6 ·
Replies
6
Views
3K
Prove 9 is eigenvalue of ##T^2\iff## 3 or -3 eigenvalue of ##T##.
  • · Replies 5 ·
Replies
5
Views
2K
Direct Proof that every zero of p(T) is an eigenvalue of T
  • · Replies 24 ·
Replies
24
Views
4K
Undergrad On Laplace transform of derivative
  • · Replies 17 ·
Replies
17
Views
4K
Proof of Chinese Remainder Theory
  • · Replies 1 ·
Replies
1
Views
1K
Modular Arithmetic Proof: How to Solve with Help | Homework Statement
  • · Replies 7 ·
Replies
7
Views
3K
Can Discrete Logarithms Be Added in Modular Arithmetic?
  • · Replies 16 ·
Replies
16
Views
2K
Prove that for a,b,c > 0, geometric mean <= arithmetic mean
  • · Replies 11 ·
Replies
11
Views
2K