system of modular equations.

Question

$x\equiv 2\pmod3$

$x\equiv 3\pmod 5$

$x\equiv 7 \pmod{11}$

How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly appreciated. What value of $x$ satisfies these three equations?

Answer 1

Use the Chinese Remainder Theorem which tells us that the simultaneous solution to a system of linear congruences $$\left\{ \begin{array}{l} x \equiv b_1 \mod m_1\\[2ex] x \equiv b_2 \mod m_2 \\[2ex] ... \\[2ex] x \equiv b_i \mod m_i \end{array} \right. $$ will be in the form $$x_0=c_1 n_1 \tilde n_1+c_2 n_2 \tilde n_2+...+n_i c_i \tilde {n_i}$$ where $M=m_1 m_2 ...m_i$ for coprime $m_i$ $, n_i={M \over m_i},$ $\tilde {n_i}$ is the modular multiplicative inverse of $n_i\mod m_i$, and $c_i$ are integers that satisfy $c_i \equiv b_i \mod m_i$. So in your case a solution would be

$$x_0=2*55*1+3*33*2+7*15*3=623$$

The theorem also tells us that all solutions will be congruent modulo $M=3*5*11$, so any integer $y$ that satisfies $$623 \equiv y\mod 165$$ is also a solution (The smallest $y$ is 128).

Answer 2

Here is a hands-on solution:

$x\equiv 2\pmod3$ implies $x=2+3y$.

$x\equiv 3\pmod 5$ then implies $3y\equiv 1 \pmod 5$ and so $y\equiv 2 \pmod 5$ because $2 \cdot 3 \equiv 1 \pmod 5$. This means that $y=2+5z$ and $x=2+6+15z=8+15z$.

$x\equiv 7 \pmod{11}$ then implies $15z \equiv -1 \pmod{11}$ and so $z \equiv -3 \pmod{11}$ because $15 \equiv 4 \pmod{11}$ and $3 \cdot 4 \equiv 1 \pmod{11}$. This means that $z=-3+11t$ and so $x=8-45+165t=-37+165t$.

Thus, the solution is $x \equiv -37 \equiv 128 \pmod{165}$.

Answer 3

Some problems of this type, especially if the moduli are small, can be solved by the method of adding the modulus:

$\mod 11$: We have $x\equiv 7 \equiv 18$. We note that $18$ also satisfies the $\mod 5$ congruence, since $18\equiv 3 \pmod{5}$.

So $\mod{55}$: $x\equiv 18\equiv 73\equiv 128$. And $128$ satisfies the $\mod 3$ congruence.

So the solution is $x\equiv 128 \pmod{165}$

Answer 4

When I create new variables, they're integers.

$x\equiv 2\,\pmod{\! 3}\iff x=3k+2$.

$x\equiv 3\,\pmod{\! 5}\iff 3k+2\equiv 3\,\pmod{\! 5}$

$\iff 3k\equiv 1\equiv 6\stackrel{:3}\iff k\equiv 2\,\pmod{\! 5}$.

I.e. $k=5m+2$, then $x=3(5m+2)+2=15m+8$.

Here we could've solved $3k\equiv 1\pmod{\! 5}$ by using Extended Euclidean algorithm (as below) to find $k_1,b\in\Bbb Z$ such that $3k_1+5b=1$, in which case $3k_1\equiv 1\pmod{\! 5}$.

EEA can be used in a table (as explained here), where e.g. $5=5(1)+3(0)$. We subtract consecutive rows:

$$\begin{array}{l|c|r}5& 5(1)& 3(0)\\\hline 3& 5(0)& 3(1)\\\hline 2& 5(1)& 3(-1)\\\hline 1& 5(-1)& 3(2)\end{array}$$

$5(-1)+3(2)=1$ implies $3(2)\equiv 1\pmod{\! 5}$, i.e. $k\equiv 2\pmod{\! 5}$.

Gauss' algorithm can also be used:

$3k\equiv 1\stackrel{\cdot 2}\iff 6k\equiv 2\iff k\equiv 2\,\pmod{\! 5}$

$x\equiv 7\,\pmod{\! 11}\iff 15m+8\equiv 7\,\pmod{\! 11}$

$\iff 15m\equiv 4m\equiv -1\equiv -12\stackrel{:4}\iff m\equiv -3\equiv 8\,\pmod{\! 11}$

I.e. $m=11a+8$, then $x=15(11a+8)+8=165a+128$.

In the same way we could've used Extended Euclidean or Gauss' algorithm to solve $4m\equiv -1\,\pmod{\! 11}$, like above.