- #1

- 293

- 31

## 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}##.

## Homework Equations

## 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)##...