• Support PF! Buy your school textbooks, materials and every day products Here!

Chinese Remainder theorem for 2 congruences

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

Answers and Replies

  • #2
I like Serena
Homework Helper
6,577
176
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
293
31
Ok, thank you.
 
  • Like
Likes I like Serena

Related Threads on Chinese Remainder theorem for 2 congruences

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
977
Replies
0
Views
2K
Replies
1
Views
2K
Replies
0
Views
3K
Replies
1
Views
535
Replies
1
Views
1K
Top