Chinese Remainder Theorem

[Bleys]

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]

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]

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]

"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?

 

[Bleys]

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]

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.

 

[Bleys]

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]

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.

 

[Bleys]

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]

I believe you know exactly when k, as defined, is invertible modulo m...

I believe it might be better to first work through the case where you have many different relatively prime moduli. Once you understand that, you can then reduce to it the case where you have two moduli that are not relatively prime.

Alternatively, you might first try to work out exactly when a single linear modular equation does and does not have a solution (and if it does, how many).