Solving modulus equation systems

Question

I am studying for a test in discrete math and I created my own question but I cannot seem to solve it.

Is it possible to solve the following equation system (without brainless testing), and if so, how?

$$x \equiv 5 \pmod 3\\ x \equiv 2 \pmod 7$$

My attempt: $$x=3a + 5 $$

$$x=7b + 2$$

$$3\mid(x-5)$$ $$7\mid(x-2)$$

I cannot seem to continue beyond this point. Can I solve it with least common multiple or something?

Answer 1

we can write $$x=5+3k_1$$ and $$x=2+7k_2$$ where $k_1,k_2$ are integer numbers, thus you have to solve the Diophntine equation $$3=-3k_1+7k_2$$

Answer 2

Actually, this is a rather simple problem. $5\equiv2\pmod3$, so you have $x$ is $2$ more than a multiple of $3$ and $2$ more than a multiple of $7$. Combine these conditions, and $x$ must be $2$ more than a multiple of $21$, or $x\equiv2\pmod{21}$.

We can make a tougher problem by reversing the first condition to $x\equiv3\pmod5$. In which case you have

$$x=7b+2\equiv3\pmod5$$ $$2b\equiv1\equiv6\pmod5$$ $$b\equiv3\pmod5$$

Combining this with $x=7b+2$ yields

$$x=7(5k+3)+2=35k+21+2=35k+23$$ $$x\equiv23\pmod{35}$$

Answer 3

In general, the solution to

$$x=a_1 \text{ mod } m_1$$ $$x=a_2 \text{ mod } m_2$$

is

$$x=\left[a_1M_1M_1' +a_2M_2M_2'\right] \ \ \text{ mod } m_1m_2$$

where $M_i = \dfrac{m_1m_2}{m_i}$ and $M_i' = M_i^{-1}$ modulo $m_i$.

So $$x=(5\cdot 7\cdot 1 + 2\cdot 3\cdot 5) \ \ \text{ mod } 21 = 2$$

This process is explained in the standard constructive proof of the Chinese Remainder Theorem (see here), and is easily generalized to three or more equations to $\sum\limits_{i=1}^n a_iM_iM_i' \text{ mod } \prod m_i$

Answer 4

Using the Chinese Remainder Theorem, first we notice that $\gcd (3,7) = 1$.

We may tackle this by looking at sections, $\mod 3$ section, $\mod 7$ section. Now, you first choose a section and put an quivalent to zero on the other sections so they will disappear for example $3 \equiv 0\mod 3$ so we write

$$x = \underbrace{\ }_{\mod 3} + \underbrace{3}_{\mod 7} $$

Next we will have

$$x = \underbrace{7 }_{\mod 3} + \underbrace{3}_{\mod 7}$$

Notice that $7 \equiv 1 \mod 3$ then if you multiply by $5$ you get $35 \equiv 5 \mod 3$. If you hit $x \mod 3$ we get

$$x = 5 \mod 3$$

Using the same idea we have that $3\dot \ 5 \equiv 1\mod 7$ then $2 \dot\ 3\dot \ 5 \equiv2 \mod 7$

and then

$$x = 35 + 30 = 65$$

simply put we have that once applying the Chinese Remainder Theorem

$$x \equiv 65 \equiv 2\mod 3\dot \ 7$$

which gives $$x \equiv 2 \mod 21$$