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

Chinese Remainder Theorem

  • #1
124
0

Homework Statement



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

http://www.libraryofmath.com/chinese-remainder-theorem.html

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.
 

Answers and Replies

  • #2
614
0
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.
 

Related Threads on Chinese Remainder Theorem

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
980
Replies
2
Views
502
Replies
0
Views
2K
Replies
1
Views
2K
Replies
0
Views
3K
Replies
1
Views
542
Replies
1
Views
1K
Top