# Thread: Basic Chinese Remainder Theorem Problem

1. ## Basic Chinese Remainder Theorem Problem

Okay, my book has been focusing on the Chinese Remainder Theorem and how Relatively Prime Numbers pertain to it. According to my book, there exists an example of three positive integers m, n, and r, and three integers a, b, and c where GCD[m,n,r]=1, but there is no simultaneous solution to:

x = a (mod m)
x = b (mod n)
x = c (mod r):

Can anyone think of an example ? I know that the important thing to note is that the Chines Remainder Theorem requires relatively prime numbers...

2. Originally Posted by 1337h4x
Okay, my book has been focusing on the Chinese Remainder Theorem and how Relatively Prime Numbers pertain to it. According to my book, there exists an example of three positive integers m, n, and r, and three integers a, b, and c where GCD[m,n,r]=1, but there is no simultaneous solution to:

x = a (mod m)
x = b (mod n)
x = c (mod r):

Can anyone think of an example ? I know that the important thing to note is that the Chines Remainder Theorem requires relatively prime numbers...

No. The CRT requires pairwise co-prime numbers, i.e.: every two of them must be co-prime.
Counterexample: $n=2,\,m=4,\,r=3\,,\,\,a=0,\,b=1,\,c=0$

Tonio

3. Thanks ! I'll go and work those out!