Results 1 to 3 of 3

Math Help - Basic Chinese Remainder Theorem Problem

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by 1337h4x View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Thanks ! I'll go and work those out!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The chinese remainder theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 12th 2011, 07:52 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  3. Chinese Remainder Theorem Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 21st 2009, 01:49 PM
  4. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 09:01 PM
  5. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum