What is the solution expressed in the Chinese Remainder Theorem?

In summary, the conversation is about understanding the Chinese Remainder Theorem and its application to solving systems of congruences. The person is confused about why the end result is expressed as a linear congruence and asks if it would be wrong to only give one solution on a test. The other person explains that giving only one solution may show a general understanding, but not precise formulation. They also give an example using quadratic residues to further illustrate the concept.
  • #1
squaremeplz
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 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
  • #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.
 

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that provides a solution for simultaneous congruences with different moduli. It states that if the moduli are pairwise relatively prime, then there exists a unique solution to the system of congruences.

How is the Chinese Remainder Theorem used?

The Chinese Remainder Theorem is used in number theory, algebra, and cryptography. It is often used in encryption algorithms, such as the RSA algorithm, to efficiently solve large modular equations.

Who discovered the Chinese Remainder Theorem?

The Chinese Remainder Theorem was first discovered by Chinese mathematician Sun Tzu in the 3rd century AD. However, it was later rediscovered and popularized by French mathematician Joseph-Louis Lagrange in the 18th century.

What are the applications of the Chinese Remainder Theorem?

Apart from its use in encryption algorithms, the Chinese Remainder Theorem has various other applications. It is used in fields such as coding theory, signal processing, and error-correcting codes.

What are the limitations of the Chinese Remainder Theorem?

The Chinese Remainder Theorem can only be applied if the moduli are pairwise relatively prime. If the moduli are not relatively prime, then the theorem cannot be used. Additionally, the theorem only provides a solution for congruences and not for equations involving real numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
4K
Replies
1
Views
2K
  • General Math
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top