# Chinese remainder theorem

1. Dec 6, 2008

### Daveyboy

Hi,

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

2. Dec 6, 2008

### Hurkyl

Staff Emeritus
Well, the previous step in the proof was to get the equation
rm + sn = 1,​
(and some of those variables didn't appear beforehand) so I bet that's important....

3. Dec 6, 2008

### Daveyboy

... I'm not sure what your getting at but I think your question is why is

rm + sn = 1

true

and it follows from the Euclidean algorithm, which I understand.

Last edited: Dec 6, 2008
4. Dec 6, 2008

### Hurkyl

Staff Emeritus
Well, what do you know about modular arithmetic?

5. Dec 6, 2008

### Daveyboy

I have some exposure to modular arithmetic, I should know this and understand it clearly but, I have been struggling with it for a while now.

I understand that if x = a (mod n) and x = b (mod m) with gcd(n,m) = 1

they we can find x if we can find integers y and z such that

y = 1 (mod n) and y = 0 (mod m)
and
z = 0 (mod n) and z = 1 (mod m)

with x = ya + zb

because

ya + zb = 1a + 0b = a (mod n)
and
ya + zb = 0a + 1b = b (mod m)

6. Dec 7, 2008

### dodo

If you have an initial equation rm + sn = 1, and you want to arrive to rm = 1 (mod n), what can you notice in the initial equation regarding divisibility by n?

7. Dec 7, 2008

### mathwonk

here is a less constructive proof. you want to show the map Z--Z/n x Z/m is surjective.

first find the kernel. i.e. which x in Z go to zero in both Z/n and Z/m? such x are divisible by both n and m so are divisible by the product nm (why?).

thus the induced map Z/nm --> Z/n x Z/m is injective since we have set the things that go to zero, themselves equal to zero. but now we have an injective map betwe two sets of the same cardinality, hence it must be surjective.

8. Dec 7, 2008

### Daveyboy

I notice that n|sn --> sn is congruent to 0 mod n
and rm is congruent to 1 mod n iff rm = 4n + 3 for q an integer, by the division theorem.

but I still am not really seeing anything from this...

This is a little too funny, this is almost what I am trying to prove. It is nice because I think I am on the right track, maybe I should take a different approach.

I am trying to show ZmnX is isomorphic to ZmXXZnX given that the gcd(m,n) is 1.

I will post my work soon.

Last edited: Dec 7, 2008
9. Dec 7, 2008

### Daveyboy

I want to find an isomorphism between the groups as described above.
So, I want f to be bijective and to also satisfy, for [a]mn, mn elements of ZmnX,

I want to show this --> direction, (doest the other way look easier or clearer)

f([a]mnmn) = f([a]mn)f(mn)

... I really don't know how to construct f, I have no idea how to create a bijection even going the other way

for elements [a]m, n of ZmX and ZnX respectively construct a bijection such that

f([a]mn) = f([a]m)f(n)

but the elements look like [a]mn--->([ab]mn)

I have the ker(f) = {([1]m,[1]n)} or {[1]mn} depending on the way I end up going.

I know that Eulers totient function, phi, gives phi(mn)=phi(m)phi(n). All that really gives is equal cardinality though.

WLOG I can claim m>=n.

So, I think I want,

f: [a]mn to ([a]m,[a]n).

So then we have

f([a]mnmn) = f([a]mn)f(mn)

LHS gives
f([a]mnmn) = f([ab]mn) = ([ab]n,[ab]n)

and the RHS gives
f([a]mn)f(mn) = ([a]m,[a]n)(m,n) = ([ab]n,[ab]n)

So the LHS = RHS and that shows this is a homomorphism,

Now for the bijection, using the ker(f) gives the trivial solution this is injective, and with the totient function give that the cardinality is equal, f must also be surjective.

So, does this look right?

10. Dec 18, 2008

### Take_it_Easy

If I understand well, if is VERY EASY! So easy that it could be even confusing.

Definition say that $$a \cong b$$ mod $$n$$ IF and ONLY IF $$n$$ divides $$b-a$$. Is that right???
So if you have
$$rm + sn = 1$$
then you have
$$sn - 1 = rm$$ and $$m$$ divides obviously $$rm$$. So you get that $$m$$ divides $$sn- 1$$ and this is by definition equivalent to say that $$sn \cong 1$$ mod $$m$$.

The next result is similar. $$rm + sn = 1$$ means $$rm -1 = sn$$ so $$n$$ divides $$rm - 1$$ and you get
$$rm \cong 1$$ mod $$n$$.

Was this the thing you couldn't get????? Or there is something more????

Last edited: Dec 18, 2008
11. Dec 18, 2008

### Take_it_Easy

Can't understand why the TeX writings don't quite work good so I rewrite everuthing in normal text mode.

If I understand well, if is VERY EASY! So easy that it could be even confusing.

Definition say that a = b mod n IF and ONLY IF n divides b-a. Is that right???
So if you have

rm + sn = 1

then you have

sn - 1 = rm

and m divides obviously rm.

So you get that m divides sn - 1 and this is by definition equivalent to say that

sn = 1 mod m.

The next result is similar.

rm + sn = 1

means

rm -1 = sn

so n divides rm - 1 and you get

rm = 1 mod n.

Was this the thing you couldn't get????? Or there is something more????