- #1

Math100

- 771

- 219

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

##x\equiv 5\pmod{11},x\equiv 14\pmod {29},x\equiv 15\pmod{31}##.

- Relevant Equations
- None.

Consider the following set of simultaneous congruences:

## x\equiv 5\pmod {11}, x\equiv 14\pmod {29}, x\equiv 15\pmod {31} ##.

Applying the Chinese Remainder Theorem produces:

## n=11\cdot 29\cdot 31=9889 ##.

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

Observe that ## N_{1}=\frac{9889}{11}=899, N_{2}=\frac{9889}{29}=341 ## and ## N_{3}=\frac{9889}{31}=319 ##.

Then

\begin{align*}

&899x_{1}\equiv 1\pmod {11}\\

&341x_{2}\equiv 1\pmod {29}\\

&319x_{3}\equiv 1\pmod {31}.\\

\end{align*}

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

Thus ## x\equiv (5\cdot 899\cdot 7+14\cdot 341\cdot 4+15\cdot 319\cdot 7)\pmod {9889}\equiv 84056\pmod {9889}\equiv 4944\pmod {9889} ##.

Therefore, ## x\equiv 4944\pmod {9889} ##.

## x\equiv 5\pmod {11}, x\equiv 14\pmod {29}, x\equiv 15\pmod {31} ##.

Applying the Chinese Remainder Theorem produces:

## n=11\cdot 29\cdot 31=9889 ##.

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

Observe that ## N_{1}=\frac{9889}{11}=899, N_{2}=\frac{9889}{29}=341 ## and ## N_{3}=\frac{9889}{31}=319 ##.

Then

\begin{align*}

&899x_{1}\equiv 1\pmod {11}\\

&341x_{2}\equiv 1\pmod {29}\\

&319x_{3}\equiv 1\pmod {31}.\\

\end{align*}

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

Thus ## x\equiv (5\cdot 899\cdot 7+14\cdot 341\cdot 4+15\cdot 319\cdot 7)\pmod {9889}\equiv 84056\pmod {9889}\equiv 4944\pmod {9889} ##.

Therefore, ## x\equiv 4944\pmod {9889} ##.