The Chinese Remainder Theorem for moduli that aren't relatively prime

In summary, the conversation discusses the Chinese Remainder Theorem and its application to two pairs of congruences. The direction of one solution is shown, but there is difficulty in proving the other direction. The relationship between a and b is explored, but the results are not convincing. It is noted that the solution, if it exists, is unique modulo lcm(m,n) rather than m*n.
  • #1
audiowize
7
0
Hello,
I am looking into proving that the Chinese Remainder Theorem will work for two pairs of congruences IFF a congruent to b modulo(gcd(n,m)) for

x congruent to a mod(n) and x congruent to b mod(m).

I have gotten one direction, that given a solution to the congruences mod(m*n), then a congruent to b mod(gcd(m,n)).

My issue is going the other way, given a congruent to b mod(gcd(m,n)), show a solution to the congruences exists mod(m*n).

Can anybody help me with a start? I tried expressing the relationship between a and b and using that to determine what x would have to be, but I'm not convinced of the results.
 
Physics news on Phys.org
  • #2
OK, I got that the gcd(n,m)|(a-b)-> x==a mod(n) and x==b mod(m) will have a solution, but showing that that solution is restricted to the modulus of m*n is giving me troubles...
 
  • #3
AFAIK, the solution (if it exists) is unique modulo lcm(m,n), not modulo m*n.
 

1. What is the Chinese Remainder Theorem for moduli that aren't relatively prime?

The Chinese Remainder Theorem is a mathematical theorem that helps to solve a system of congruences with moduli that are not relatively prime. It states that if we have a set of congruences with pairwise relatively prime moduli, we can find a unique solution that satisfies all of them simultaneously.

2. How is the Chinese Remainder Theorem used in practical applications?

The Chinese Remainder Theorem has many practical applications, especially in cryptography and data encryption. It is also used in computer science to optimize memory management and in error-correcting codes in communication systems.

3. Can the Chinese Remainder Theorem be used for moduli that are not integers?

Yes, the Chinese Remainder Theorem can be extended to work with moduli that are not integers, such as polynomials or matrices. This allows for its application in a wider range of mathematical problems and fields.

4. What are the limitations of the Chinese Remainder Theorem for moduli that aren't relatively prime?

The main limitation of the Chinese Remainder Theorem for moduli that aren't relatively prime is that it only works for a finite set of congruences. It also requires the moduli to be pairwise relatively prime, which may not always be the case in real-world problems.

5. Are there any alternative theorems to the Chinese Remainder Theorem for moduli that aren't relatively prime?

Yes, there are alternative theorems that can be used to solve systems of congruences with moduli that are not relatively prime. Some examples include the Garner-Hwang theorem and the Dixon-Jacobsthal-McKee algorithm. These theorems may have different requirements and limitations, so it is important to choose the most appropriate one for a given problem.

Similar threads

I Modulo and Modulus in math and computer programming
    • General Math
Replies
5
Views
2K
Chinese Remainder theorem for 2 congruences
    • Calculus and Beyond Homework Help
Replies
2
Views
1K
MHB About a variant of the Chinese Remainder Theorem
    • General Math
Replies
5
Views
2K
How do I use Chinese remainder theorem to solve for x mod 683 in Cryptography?
    • Linear and Abstract Algebra
Replies
12
Views
4K
Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!
    • Linear and Abstract Algebra
Replies
10
Views
5K
Chinese Remainder Theorem, Solving For Multiplicative Inverses
    • Linear and Abstract Algebra
Replies
2
Views
5K
Find and Test Primes using the Chinese Remainder Theorem and Binary Search
    • Linear and Abstract Algebra
Replies
2
Views
5K
Finding Integer with Chinese Remainder Theorem
    • Precalculus Mathematics Homework Help
Replies
3
Views
848
Chinese remainder theorem (CRT) question, flat shapes
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Finding the orders of 1, 2, .... , 16 (mod 17)
    • Calculus and Beyond Homework Help
Replies
1
Views
5K

Hot Threads

Recent Insights

Back
Top