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

• Math100
In summary, using the Chinese Remainder Theorem, we can solve the set of simultaneous congruences x≡5(mod11), x≡14(mod29), x≡15(mod31) to find that x≡4944(mod9889).
Math100
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} ##.

Math100 said:
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} ##.
Correct, and I checked all calculations. Btw., how did you find ##x_1,x_2## and ##x_3##?

Edit: A way to check modulo operations with calc.exe from windows is e.g. ##4944 \, : \,31= 159,...## followed by ##159,... \, - \,159 = ...## and ##... \, \cdot \,31 =15.## Hence ##4944 \equiv 15\pmod{31}.##

Math100
fresh_42 said:
Correct, and I checked all calculations. Btw., how did you find ##x_1,x_2## and ##x_3##?

Edit: A way to check modulo operations with calc.exe from windows is e.g. ##4944 \, : \,31= 159,...## followed by ##159,... \, - \,159 = ...## and ##... \, \cdot \,31 =15.## Hence ##4944 \equiv 15\pmod{31}.##

\begin{align*}
&899x_{1}\equiv 1\pmod {11}\\
&\implies 8x_{1}\equiv 1\pmod {11}\\
&\implies 32x_{1}\equiv 4\pmod {11}\\
&\implies -x_{1}\equiv 4\pmod {11}\\
&\implies x_{1}\equiv -4\pmod {11}\\
&\implies x_{1}\equiv 7\pmod {11}.\\
\end{align*}

## x_{1}=7 ##

\begin{align*}
&341x_{2}\equiv 1\pmod {29}\\
&\implies 22x_{2}\equiv 1\pmod {29}\\
&\implies -7x_{2}\equiv 1\pmod {29}\\
&\implies -28x_{2}\equiv 4\pmod {29}\\
&\implies x_{2}\equiv 4\pmod {29}.\\
\end{align*}
## x_{2}=4 ##
\begin{align*}
&319x_{3}\equiv 1\pmod {31}\\
&\implies 9x_{3}\equiv 1\pmod {31}\\
&\implies 36x_{3}\equiv 4\pmod {31}\\
&\implies 5x_{3}\equiv 4\pmod {31}\\
&\implies -30x_{3}\equiv -24\pmod {31}\\
&\implies x_{3}\equiv 7\pmod {31}.\\
\end{align*}
## x_{3}=7 ##

Last edited by a moderator:
fresh_42
Another way. Let
$$x=31a+15=29a+(2a+15)=11*3a+(-2a+15)$$
So
$$2a \equiv -1(mod\ 29)$$
$$2a \equiv -1(mod\ 11)$$
The least a is
$$2a+1=29*11$$
$$a=159$$
The least x is
$$x=31*159+15=4944$$
In general
$$x=31*29*11b+4944$$
where b=0,1,2,...

Last edited:

## What is the meaning of "mod" in this equation?

"Mod" stands for "modulus" and is used to indicate the remainder after dividing a number by another number. In this equation, the "mod" is used to indicate the congruence of the numbers on the left and right sides of the equation.

## What is the solution to this equation?

The solution to this equation is the value of x that satisfies all three congruences simultaneously. In this case, the solution is x = 1165.

## How do you solve this type of equation?

To solve this type of equation, you can use the Chinese Remainder Theorem, which states that if the moduli (in this case, 11, 29, and 31) are pairwise relatively prime, then there is a unique solution for x. You can also use the Extended Euclidean Algorithm to find the solution.

## What does it mean for two numbers to be congruent?

Two numbers are congruent if they have the same remainder when divided by the same number. In this equation, x is congruent to 5 when divided by 11, congruent to 14 when divided by 29, and congruent to 15 when divided by 31.

## Can this equation have multiple solutions?

Yes, this equation can have multiple solutions if the moduli are not relatively prime. In this case, the Chinese Remainder Theorem does not apply and there may be multiple values of x that satisfy the congruences. However, in this specific equation, there is only one solution.

Replies
1
Views
1K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
7
Views
1K
Replies
4
Views
1K
Replies
3
Views
1K
Replies
3
Views
1K
Replies
7
Views
2K
Replies
3
Views
2K
Replies
7
Views
1K