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.
 

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

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
Replies
5
Views
2K
Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!
Replies
10
Views
5K
Chinese Remainder Theorem, Solving For Multiplicative Inverses
Replies
2
Views
5K
How do I use Chinese remainder theorem to solve for x mod 683 in Cryptography?
Replies
12
Views
4K
Find and Test Primes using the Chinese Remainder Theorem and Binary Search
Replies
2
Views
5K
Chinese Remainder theorem for 2 congruences
Replies
2
Views
1K
MHB About a variant of the Chinese Remainder Theorem
Replies
5
Views
2K
Solving Systems of Congruences when mods not pairwise relatively prime
Replies
1
Views
5K
Number of quadratic residues mod N>1
Replies
4
Views
3K
Chinese remainder theorem (CRT) question, flat shapes
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top