# Chinese Remainder Theorem

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

## Homework Statement

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

2. The attempt at a solution

now, sm + tn = 1 for some integers s,t. It's obvious that
$$sm\equiv0(mod m)$$ and $$tn\equiv0(mod n)$$

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.

Hurkyl
Staff Emeritus
Gold Member
It's essentially a linear algebra problem -- your "vectors" are the two-tuples whose components are "value mod m" and "value mod n", and you seek to express a particular vector as an integer linear combination of the two vectors you have already considered.

I've tried adding tn to get 1 == tn (mod m) but I'm not sure that's correct.
Well, have you thought about how you might prove it? If not, can you explain why you think it might be true?

gabbagabbahey
Homework Helper
Gold Member
Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that
$$c\equiva(mod m)$$ and $$c\equivb(mod n)$$

Do you mean that you are trying to show that you can always find integer $c$ such that:

$$c \equiv a \quad (\text{mod} \; m)$$ and $$c \equiv b \quad (\text{mod} \; n)$$

?

HallsofIvy
Homework Helper
"Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that $c (mod m)$ and $c (mod n)$" makes no sense. What is supposed to be true of $c (mod m)$ and $c (mod m)$? That they are equal?

yes, gabbagabbahey, sorry that's what I meant:
$$c \equiv a \quad (\text{mod} \; m)$$
$$c \equiv b \quad (\text{mod} \; n)$$

So since $$sm \equiv 0 (\text{mod} \; m)$$ then, I thought
$$tn + sm \equiv tn (\text{mod} \; m)$$
$$1 \equiv tn (\text{mod} \; m)$$

Hurkyl
Staff Emeritus
Gold Member
So since $$sm \equiv 0 (\text{mod} \; m)$$ then, I thought
$$tn + sm \equiv tn (\text{mod} \; m)$$
$$1 \equiv tn (\text{mod} \; m)$$
Yes, this is definitely correct.

hmm, looking at it though, I don't think it would get me anywhere would it? Rather, the congruence also implies

$$tn \equiv 1 (\text{mod} \; m)$$ therefore
$$atn \equiv a (\text{mod} \; m)$$
and in the same way you can get

$$bsm \equiv b (\text{mod} \; n)$$

then, can you say bsm + atn is congruent to both a (mod m) and b (mod n); hence that's the c I'm looking for?

Hurkyl
Staff Emeritus
Gold Member
then, can you say bsm + atn is congruent to both a (mod m) and b (mod n); hence that's the c I'm looking for?
You seem hesitant to assert that -- what might be a problem? If you can indeed prove both of those congruences, it sounds like you've constructively shown the existence of such a c.

I guess I'm convinced; after all if you have
bsm + atn == a (mod m)
0 + atn == a (mod m)
and we've seen tn == 1 (mod m), so
a == a (mod m); similarly for bsm == b (mod n)

If I can ask another question;
What if gcd(m,n)=k for some k>1
Going through similar steps I obtain
$$atn \equiv ak (\text{mod} \; m)$$

I thought, you would need to obtain the inverse of k modulo m (assuming m is prime, and therefore the inverse exists). Let f be the inverse of k (mod m). Then
$$fatn \equiv fak (\text{mod} \; m)$$
$$fatn \equiv a (\text{mod} \; m)$$

Similarly for bsm, you would obtain
$$bsm \equiv bk (\text{mod} \; n)$$
$$gbsm \equiv gbk (\text{mod} \; n)$$ where g is the inverse of k (mod n)
$$gbsm \equiv b (\text{mod} \; n)$$

Therefore our c = fatn + gbsm. Correct?
If either m or n, possibly both, are not prime, then you would you still have a solution for this only if the inverse of k exists for both (mod m) and (mod n). If it doesn't, then is the system not solvable?

Hurkyl
Staff Emeritus