Obtain the two incongruent solutions modulo 210 of the system

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    System
AI Thread Summary
The discussion revolves around solving a system of congruences to find two incongruent solutions modulo 210. The congruences are derived from equations involving x, leading to specific modular results. The Chinese Remainder Theorem is applied to calculate the solutions, resulting in x congruent to 59 and 164 modulo 210. A typo is identified, where 64 is mistakenly noted as a solution, but it is clarified that 64 is not valid. The conversation highlights the importance of careful verification in mathematical problem-solving.
Math100
Messages
813
Reaction score
229
Homework Statement
Obtain the two incongruent solutions modulo ## 210 ## of the system
## 2x\equiv 3\pmod {5} ##
## 4x\equiv 2\pmod {6} ##
## 3x\equiv 2\pmod {7} ##.
Relevant Equations
None.
Consider the following system of congruences:
## 2x\equiv 3\pmod {5} ##
## 4x\equiv 2\pmod {6} ##
## 3x\equiv 2\pmod {7} ##.
Then
\begin{align*}
&2x\equiv 3\pmod {5}\implies 6x\equiv 9\pmod {5}\implies x\equiv 4\pmod {5}\\
&4x\equiv 2\pmod {6}\implies 2x\equiv 1\pmod {3}\\
&3x\equiv 2\pmod {7}\implies 6x\equiv 4\pmod {7}\implies -x\equiv 4\pmod {7}\implies x\equiv 3\pmod {7}.\\
\end{align*}
Note that ## 2x\equiv 1\pmod {3}\implies x\equiv 2\pmod {6} ## or ## x\equiv 5\pmod {6} ## because
## gcd(4, 6)=2 ##, which implies that there are two incongruent solutions ## x_{0}, x_{0}+\frac{6}{2} ## where ## x_{0}=2 ##.
Applying the Chinese Remainder Theorem produces:
## n=5\cdot 6\cdot 7=210 ##.
This means ## N_{1}=\frac{210}{5}=42, N_{2}=\frac{210}{6}=35 ## and ## N_{3}=\frac{210}{7}=30 ##.
Observe that
\begin{align*}
&42x_{1}\equiv 1\pmod {5}\implies 2x_{1}\equiv 1\pmod {5}\\
&\implies 6x_{1}\equiv 3\pmod {5}\implies x_{1}\equiv 3\pmod {5}\\
&35x_{2}\equiv 1\pmod {6}\implies -x_{2}\equiv 1\pmod {6}\\
&\implies x_{2}\equiv -1\pmod {6}\implies x_{2}\equiv 5\pmod {6}\\
&30x_{3}\equiv 1\pmod {7}\implies 2x_{3}\equiv 1\pmod {7}\\
&\implies 8x_{3}\equiv 4\pmod {7}\implies x_{3}\equiv 4\pmod {7}.\\
\end{align*}
Now we have ## x_{1}=3, x_{2}=5 ## and ## x_{3}=4 ##.
Thus
\begin{align*}
&x\equiv (4\cdot 42\cdot 3+2\cdot 35\cdot 5+3\cdot 30\cdot 4)\pmod {210}\equiv 1214\pmod {210}\equiv 164\pmod {210}\\
&x\equiv (4\cdot 42\cdot 3+5\cdot 35\cdot 5+3\cdot 30\cdot 4)\pmod {210}\equiv 1739\pmod {210}\equiv 59\pmod {210}.\\
\end{align*}
Therefore, the two incongruent solutions modulo ## 210 ## are ## x\equiv 59, 64\pmod {210} ##.
 
Physics news on Phys.org
Looks good, except for the typo at the end.
 
fresh_42 said:
Looks good, except for the typo at the end.
What's the typo at the end?
 
Math100 said:
What's the typo at the end?
##64## is no solution.
 
  • Haha
Likes Math100
fresh_42 said:
##64## is no solution.
I was careless.
 
Math100 said:
I was careless.
I have made mistakes worse than that!
 
fresh_42 said:
I have made mistakes worse than that!
Really? That's difficult to imagine.
 
Math100 said:
Really? That's difficult to imagine.
In chess speak, I'd say: you look at the position, into the position, and do not see the obvious. Even grandmasters have run into knight forks. Not that I am one, but **** happens.
 
  • Like
  • Haha
Likes SammyS and Math100
Back
Top