# Chinese Remainder theorem for 2 congruences

## Homework Statement

Let ##a, b, m, n## be integers with ##\gcd(m,n) = 1##. Let $$c \equiv (b-a)\cdot m^{-1} (\operatorname{mod} n)$$
Prove that ##x = a + cn## is a solution to ##x \equiv a (\operatorname{mod} m)## and ##x \equiv b (\operatorname{mod} n)##, (2.24).

and that every solution to (2.24) has the form ##x = a + cn + ymn## for some ##y \epsilon \mathbb{Z}##.

## The Attempt at a Solution

Since ##\gcd(m,n) = 1## I tried following CRT..

##x \equiv a (\operatorname{mod} m)##
##x = a + mk##, for some integer ##k##.

Substituting into second congruence,
##a + mk \equiv b (\operatorname{mod} n)##
##mk \equiv b - a (\operatorname{mod} n)##
##k \equiv (b-a)\cdot m^{-1} (\operatorname{mod} n)##
##k = (b-a) \cdot m^{-1} + nl##, for some integer ##l##.
Substituting ##k## into ##x##,
##x = a + mk##
##x = a + m((b-a)\cdot m^{-1} + nl)##

But we're given ##c = (b-a)\cdot m^{-1}##
So ##x = a + mc + mnl## but they have ##nc## instead of ##mc## as the second term of ##x##

Also, I tried to check that this ##x## satisfied both congruences but i have a problem:

We have ##x \equiv a + mc \equiv a + m(b-a)\cdot m^{-1} \equiv a + b - a \equiv b (\operatorname{mod} mn)##.

So this satisifes ##x = b \equiv b (\operatorname{mod} n)##
But i don't see how ##x = b \equiv a (\operatorname{mod} m)## is true unless ##a \equiv b (\operatorname{mod} m)##...

Related Calculus and Beyond Homework Help News on Phys.org
I like Serena
Homework Helper
It's a typo. The solution should be x=a+cm.
Then the first equation is satisfied trivially, and c cancels neatly in the 2nd equation.

Alternatively the typo could be in the given equations, meaning m and n should be swapped.

Ok, thank you.

I like Serena