Chinese Remainder theorem for 2 congruences

  • #1
fishturtle1
394
81

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

Answers and Replies

  • #2
I like Serena
Homework Helper
MHB
16,346
250
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.
 
  • #3
fishturtle1
394
81
Ok, thank you.
 
  • Like
Likes I like Serena

Suggested for: Chinese Remainder theorem for 2 congruences

Replies
1
Views
866
  • Last Post
Replies
12
Views
694
Replies
27
Views
1K
Replies
4
Views
59
  • Last Post
Replies
7
Views
174
Replies
1
Views
172
Replies
2
Views
352
  • Last Post
Replies
5
Views
329
Replies
3
Views
373
Top