Hello,(adsbygoogle = window.adsbygoogle || []).push({});

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 Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Loading...

Similar Threads - Chinese Remainder Theorem | Date |
---|---|

Generalization of Chinese Remainder Theorem | Apr 1, 2013 |

Find and Test Primes using the Chinese Remainder Theorem and Binary Search | Sep 20, 2010 |

Chinese Remainder Theorem, Solving For Multiplicative Inverses | Mar 10, 2010 |

Chinese remainder theorem (Gaussian ints) | Nov 23, 2009 |

Chinese remainder theorem | Dec 6, 2008 |

**Physics Forums - The Fusion of Science and Community**