What is the solution expressed in the Chinese Remainder Theorem?

Click For Summary
SUMMARY

The Chinese Remainder Theorem (CRT) provides a method for solving systems of linear congruences. In the discussion, the user questions why solutions are expressed in terms of congruences, such as 53 (mod 84) and 263 (mod 105), despite these values being valid solutions. The consensus is that while providing a single solution demonstrates understanding, expressing the solution in congruence form is essential for clarity and completeness, especially in academic settings. The discussion also touches on the concept of quadratic residues, emphasizing the importance of understanding the full set of solutions.

PREREQUISITES
  • Understanding of linear congruences
  • Familiarity with the Chinese Remainder Theorem
  • Basic knowledge of modular arithmetic
  • Concept of quadratic residues
NEXT STEPS
  • Study the proofs and applications of the Chinese Remainder Theorem
  • Explore examples of linear congruences and their solutions
  • Learn about quadratic residues and their implications in number theory
  • Investigate the relationship between modular arithmetic and cryptography
USEFUL FOR

Students of mathematics, particularly those studying number theory, educators teaching modular arithmetic, and anyone preparing for exams involving the Chinese Remainder Theorem.

squaremeplz
Messages
114
Reaction score
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 don't 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.
 
Physics news on Phys.org
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.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
3K
Replies
9
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
  • · Replies 5 ·
Replies
5
Views
12K
Replies
1
Views
2K
Replies
10
Views
3K
  • · Replies 7 ·
Replies
7
Views
6K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K