- #1
Math100
- 756
- 202
- 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} ##.
## 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} ##.