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

[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}$.

 

[fresh_42]

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]

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$

 

[anuttarasammyak]

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,...