A Modular Arithmetic Proof Problem

In summary, the conversation discusses the conditions that must be satisfied by integers s and t if the statement "If a = b (mod s) and a = b (mod t), then a = b (mod st)" is true. The conclusion is that s and t must be relatively prime for the statement to be true.
  • #1
e(ho0n3
1,357
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
  • #2
The statement is equivalent to s | (b-a) and t | (b-a) -> st | (b-a).
 
  • #3
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.
 

Related to A Modular Arithmetic Proof Problem

1. What is modular arithmetic?

Modular arithmetic is a mathematical system that deals with integers and their remainders when divided by a fixed number, known as the modulus. It is often used in cryptography and computer science.

2. What is a modular arithmetic proof problem?

A modular arithmetic proof problem is a problem that requires the use of modular arithmetic to prove a statement or theorem. It usually involves manipulating integers and their remainders to arrive at a solution.

3. How do you approach a modular arithmetic proof problem?

To approach a modular arithmetic proof problem, you should first understand the properties of modular arithmetic, such as the modulus operator and the rules for addition, subtraction, multiplication, and division. Then, you can use these properties to manipulate the given integers and arrive at a solution.

4. What are some common mistakes when solving a modular arithmetic proof problem?

Some common mistakes when solving a modular arithmetic proof problem include forgetting to apply the modulus operator, using incorrect rules for addition, subtraction, multiplication, or division, and not simplifying the final solution to its remainder form.

5. How can modular arithmetic be applied in real-world scenarios?

Modular arithmetic can be applied in real-world scenarios such as calculating time and date, determining the day of the week, encrypting and decrypting messages, and solving problems in computer science and engineering. It is also used in various fields of mathematics, such as number theory and algebra.

Similar threads

U(n) as an External Direct Product
    • Calculus and Beyond Homework Help
Replies
11
Views
1K
Prove that sup(ST) = sup(S)sup(T)
    • Calculus and Beyond Homework Help
Replies
7
Views
2K
Prove 9 is eigenvalue of ##T^2\iff## 3 or -3 eigenvalue of ##T##.
    • Calculus and Beyond Homework Help
Replies
5
Views
637
Direct Proof that every zero of p(T) is an eigenvalue of T
    • Calculus and Beyond Homework Help
Replies
24
Views
1K
I On Laplace transform of derivative
    • Differential Equations
Replies
17
Views
958
I Proof for subgroup -- How prove it is a subgroup of Z^m?
    • Linear and Abstract Algebra
Replies
11
Views
1K
I Question on Primitive Roots and GCDs
    • Linear and Abstract Algebra
Replies
2
Views
956
Can Discrete Logarithms Be Added in Modular Arithmetic?
    • Calculus and Beyond Homework Help
Replies
16
Views
1K
Tricky Problem: Prove range T = null ##\phi## when null T' has dim 1
    • Calculus and Beyond Homework Help
Replies
8
Views
728
Proof of Chinese Remainder Theory
    • Calculus and Beyond Homework Help
Replies
1
Views
984

Hot Threads

Recent Insights

Back
Top