This doesn't actually require the use of the CRT, since it actually wants you to sort of derive it for a system of two equations. So while using the CRT will help me solve this fairly quickly and easily, that's not what I'm after(adsbygoogle = window.adsbygoogle || []).push({});

1. The problem statement, all variables and given/known data

Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that

[tex]c\equiva(mod m)[/tex] and [tex]c\equivb(mod n)[/tex]

2. The attempt at a solution

now, sm + tn = 1 for some integers s,t. It's obvious that

[tex]sm\equiv0(mod m)[/tex] and [tex]tn\equiv0(mod n)[/tex]

I know I'm suppose to use sm and tn as coefficients to combine a and b, but I'm not really sure how to go about it. I've tried adding tn to get 1 == tn (mod m) but I'm not sure that's correct. And even if it is, I multiply by a or by b and can still not figure it out. I end up in circles and get c == a (mod m). -_- Can you lend me hand? Remember, don't give me the chinese remainder theorem, because that's not what the excercise is about.

**Physics Forums | Science Articles, Homework Help, Discussion**

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!

# Homework Help: Chinese Remainder Theorem

**Physics Forums | Science Articles, Homework Help, Discussion**