Solve System of Congruences Using CRT

  • Thread starter Thread starter needmathshelp
  • Start date Start date
  • Tags Tags
    Crt System
AI Thread Summary
The Chinese Remainder Theorem (CRT) cannot be applied directly to the system x = 5 mod 6 and x = 17 mod 21 because the moduli 6 and 21 are not coprime. For CRT to be applicable, the moduli must be pairwise coprime, meaning their greatest common divisor must be 1. In this case, the common divisor is 3, which violates the necessary condition. An equivalent system can be derived by reducing the congruences to a compatible set of moduli that are coprime, allowing for a solution to be found. Understanding the conditions for CRT is essential for solving systems of congruences effectively.
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
Views
2K
Solve the simultaneous linear congruences
Replies
4
Views
2K
Solve ##x\equiv 1\pmod {3},x\equiv 2\pmod {5},x\equiv 3\pmod 7 ##
Replies
1
Views
2K
[IntroNumTheory] Determining the remainder by using congruence
Replies
1
Views
1K
Obtain the two incongruent solutions modulo 210 of the system
Replies
7
Views
3K
Solve ##x\equiv 5\pmod{11},x\equiv 14\pmod{29},x\equiv 15\pmod{31}##
Replies
3
Views
3K
Relevance of CRT to this question
Replies
2
Views
3K
Internet Infrastructure Security
Replies
2
Views
2K
System of Simultaneous Congruences
Replies
11
Views
6K
Solving Systems of Congruences when mods not pairwise relatively prime
Replies
1
Views
5K

Hot Threads

Recent Insights

Back
Top