- #1

Math100

- 773

- 219

- Homework Statement
- Solve the following set of simultaneous congruences:

## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.

- Relevant Equations
- None.

Consider the following set of simultaneous congruences:

## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.

Applying the Chinese Remainder Theorem produces:

## n=3\cdot 5\cdot 7=105 ##.

Now we define ## N_{k}=\frac{n}{n_{k}} ## for ## k=1, 2,..., r ##.

Observe that ## N_{1}=\frac{105}{3}=35, N_{2}=\frac{105}{5}=21 ## and ## N_{3}=\frac{105}{7}=15 ##.

Then

\begin{align*}

&35x_{1}\equiv 1\pmod {3}\\

&21x_{2}\equiv 1\pmod {5}\\

&15x_{3}\equiv 1\pmod {7}.\\

\end{align*}

This means ## x_{1}=2, x_{2}=1 ## and ## x_{3}=1 ##.

Thus ## x\equiv (1\cdot 35\cdot 2+2\cdot 21\cdot 1+3\cdot 15\cdot 1)\pmod {105}\equiv 157\pmod {105}\equiv 52\pmod {105} ##.

Therefore, ## x\equiv 52\pmod {105} ##.

## x\equiv 1\pmod {3}, x\equiv 2\pmod {5}, x\equiv 3\pmod {7} ##.

Applying the Chinese Remainder Theorem produces:

## n=3\cdot 5\cdot 7=105 ##.

Now we define ## N_{k}=\frac{n}{n_{k}} ## for ## k=1, 2,..., r ##.

Observe that ## N_{1}=\frac{105}{3}=35, N_{2}=\frac{105}{5}=21 ## and ## N_{3}=\frac{105}{7}=15 ##.

Then

\begin{align*}

&35x_{1}\equiv 1\pmod {3}\\

&21x_{2}\equiv 1\pmod {5}\\

&15x_{3}\equiv 1\pmod {7}.\\

\end{align*}

This means ## x_{1}=2, x_{2}=1 ## and ## x_{3}=1 ##.

Thus ## x\equiv (1\cdot 35\cdot 2+2\cdot 21\cdot 1+3\cdot 15\cdot 1)\pmod {105}\equiv 157\pmod {105}\equiv 52\pmod {105} ##.

Therefore, ## x\equiv 52\pmod {105} ##.