Solve System of Congruences Using CRT

  • Thread starter Thread starter needmathshelp
  • Start date Start date
  • Tags Tags
    Crt System
Click For Summary
SUMMARY

The Chinese Remainder Theorem (CRT) does not apply directly to the system of congruences x = 5 mod 6 and x = 17 mod 21 due to the lack of coprimality between the moduli 6 and 21. For CRT to be applicable, the moduli must be pairwise coprime. To solve this system, one must first transform it into an equivalent system where the moduli are coprime, such as x = 5 mod 6 and x = 17 mod 3. This allows for the application of CRT to find a solution.

PREREQUISITES
  • Understanding of the Chinese Remainder Theorem (CRT)
  • Knowledge of modular arithmetic
  • Familiarity with coprime numbers
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the conditions for applying the Chinese Remainder Theorem
  • Learn how to transform non-coprime systems into coprime systems
  • Explore examples of solving systems of congruences using CRT
  • Investigate applications of CRT in computer science and cryptography
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or modular arithmetic who are looking to deepen their understanding of the Chinese Remainder Theorem and its applications.

needmathshelp
Messages
1
Reaction score
0
Hi, i know how to do the CRT but I'm kind at a loss with this one. Can anyone help me please?

Explain why the Chinese Remainder Theorem does not apply directly to the following
system.
x = 5 mod 6
x = 17 mod 21

Determine an equivalent system of equations to which the CRT applies and hence solve this
system of congruences.

Cheers.
 
Physics news on Phys.org
What does the Chinese remainder theorem state? In particular, what conditions must be satisfied before it can be applied? Which condition or conditions aren't satisfied by this example?
 

Similar threads

Find the solutions of the system of congruences
  • · Replies 1 ·
Replies
1
Views
2K
Solve the simultaneous linear congruences
  • · Replies 4 ·
Replies
4
Views
2K
Solve ##x\equiv 1\pmod {3},x\equiv 2\pmod {5},x\equiv 3\pmod 7 ##
  • · Replies 1 ·
Replies
1
Views
2K
[IntroNumTheory] Determining the remainder by using congruence
  • · Replies 1 ·
Replies
1
Views
1K
Obtain the two incongruent solutions modulo 210 of the system
  • · Replies 7 ·
Replies
7
Views
3K
Solve ##x\equiv 5\pmod{11},x\equiv 14\pmod{29},x\equiv 15\pmod{31}##
  • · Replies 3 ·
Replies
3
Views
3K
Relevance of CRT to this question
  • · Replies 2 ·
Replies
2
Views
3K
Internet Infrastructure Security
  • · Replies 2 ·
Replies
2
Views
2K
How to Solve Mixed Number Multiplication in Fractions?
  • · Replies 10 ·
Replies
10
Views
3K
System of Simultaneous Congruences
  • · Replies 11 ·
Replies
11
Views
6K