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

I can not see how this is implied...

Let m and n be positive integers, with gcd(m, n) = 1. The the system of congruences

x = a (mod m) and x = b (mod n ) has a solution. Moreover, any two solutions are congruent modulo mn.

pf.

Since gcd(m,n) = 1, there exist integers r and s such that rm + sn = 1. Then rm=1 mod n and sn = 1 mod m. And the proof goes on.

I just do not understand how "Then rm=1 mod n and sn = 1 mod m." is true.

Can anyone clarify. Thanks

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

Dismiss Notice

Join Physics Forums Today!

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

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

# Chinese remainder theorem

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 |

The Chinese Remainder Theorem for moduli that aren't relatively prime | Nov 22, 2009 |

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