- #1

Math100

- 756

- 205

- 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} ##.