Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Chinese Remainder Theorem

  1. Dec 16, 2008 #1
    1. The problem statement, all variables and given/known data

    I am trying to learn the Chinese Remainder Theorem from the following website:


    The only thing I dont understand is why the end result is expressed as another linear congruence. In the first example, the solution is expressed as 53(mod 84). But x = 53 solves all the equations. Similarly, in the third example, they give the solution as 263 is congruent to 233(mod105) yet x = 263 solves the system. If on tomorrows final I only gave the numbers x = 53 or x = 263 as solutions to systems of congruences, would that be wrong? Thanks and sorry for redirecting you to a different site.
  2. jcsd
  3. Dec 17, 2008 #2
    I could not find the examples that you were mentioning, but if there were infinitely many solutions to the problem, then giving only one solution will show that you understand the general method but you don't know how to precisely forumulate your answer.

    If you are familiar with quadratic residues then consider the set of primes such that 3 is a quadratic residue mod p. 1 and 11 work fine but the correct answer would be all primes congruent to 1 or 11 mod 12. If you didn't understand that then you can also think it as having infinitely many solutions to a system of linear equations.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook