- #1
Bleys
- 74
- 0
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
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.
Homework Statement
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.