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

Click For Summary
SUMMARY

The discussion centers on the application of the Chinese Remainder Theorem (CRT) for moduli that are not relatively prime. The user seeks to prove that the CRT holds for two pairs of congruences if and only if \( a \equiv b \mod(\gcd(n,m)) \) for the congruences \( x \equiv a \mod(n) \) and \( x \equiv b \mod(m) \). The user has established one direction of the proof but is struggling to demonstrate the reverse implication. Key insights include the relationship \( \gcd(n,m) | (a-b) \) and the uniqueness of solutions modulo \( \text{lcm}(m,n) \) rather than \( m*n \).

PREREQUISITES
  • Understanding of the Chinese Remainder Theorem
  • Knowledge of modular arithmetic
  • Familiarity with greatest common divisor (gcd) and least common multiple (lcm)
  • Basic proof techniques in number theory
NEXT STEPS
  • Study the implications of the Chinese Remainder Theorem for non-relatively prime moduli
  • Explore proofs involving gcd and lcm in modular arithmetic
  • Investigate the uniqueness of solutions in modular systems
  • Learn about the properties of congruences and their applications in number theory
USEFUL FOR

This discussion is beneficial for mathematicians, students of number theory, and anyone interested in advanced modular arithmetic concepts, particularly those exploring the nuances of the Chinese Remainder Theorem.

audiowize
Messages
6
Reaction score
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
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...
 
AFAIK, the solution (if it exists) is unique modulo lcm(m,n), not modulo m*n.
 

Similar threads

MHB About a variant of the Chinese Remainder Theorem
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Yes, that was exactly what I couldn't get. Thank you for clarifying it for me!
  • · Replies 10 ·
Replies
10
Views
6K
Graduate Chinese Remainder Theorem, Solving For Multiplicative Inverses
  • · Replies 2 ·
Replies
2
Views
6K
Graduate Find and Test Primes using the Chinese Remainder Theorem and Binary Search
  • · Replies 2 ·
Replies
2
Views
6K
Graduate How do I use Chinese remainder theorem to solve for x mod 683 in Cryptography?
  • · Replies 12 ·
Replies
12
Views
4K
Chinese Remainder theorem for 2 congruences
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Solving Systems of Congruences when mods not pairwise relatively prime
  • · Replies 1 ·
Replies
1
Views
5K
Graduate Number of quadratic residues mod N>1
  • · Replies 3 ·
Replies
3
Views
4K
Finding the orders of 1, 2, .... , 16 (mod 17)
  • · Replies 1 ·
Replies
1
Views
6K
Graduate Chinese Remainder Theorem: A Powerful Tool in Number Theory
  • · Replies 5 ·
Replies
5
Views
7K