4
$\begingroup$

Here is a tricky congruence system to solve, I have tried to use the Chinese Remainder Theorem without success so far.

$$2x \equiv3\;(mod\;7)\\ x\equiv8\;(mod\;15)$$

Thank you very much Li

$\endgroup$

3 Answers 3

10
$\begingroup$

You need to "get rid of" the $2$ from the right hand side of the first congruence in your system:

\begin{aligned} 2x & \equiv 3 \mod 7 & (1) \\ x & \equiv 8 \mod 15 & (2) \end{aligned}

So here, you have to multiply both sides of equation $(1)$ by the inverse of $2$ modulo $7$, which is $4$. This means the first equation becomes $x \equiv 12 \equiv 5 \mod 7$ So this leaves us with the system:

$$\color{blue}{\begin{aligned} x & \equiv 5 \mod 7 \\ x & \equiv 8 \mod 15 \end{aligned}}$$

Since $\gcd(7, 15) = 1$, there is a unique solution for $x$ modulo $(7)(15) = 105$. So we can use the Chinese remainder theorem on the system that is in $\color{blue}{\mathrm{blue} }$.

Now try using the Chinese remainder theorem. Recall for a system of two congruences:

$$x \equiv a_1 \mod n_1$$

$$x \equiv a_2 \mod n_2,$$ if $\gcd(n_1, n_2) = 1$, then the solution is given by:

$$x \equiv a_1 n_2 [n_2^{-1}]_{n_1} + a_2 n_1[n_1^{-1}]_{n_2},$$ where $[p^{-1}]_{q}$ means "the inverse of $p$ modulo $q$".

You will find this is the solution: $$x \equiv 5\cdot15\cdot1 + 8\cdot7\cdot13 \equiv \color{green}{803} \mod 105$$ and $$\color{green}{803} \equiv \color{red}{68} \mod 105,$$ so $$\boxed{\color{red}{x=68}}.$$

$\color{red}{\mathrm{That}}$ is the least positive residue solution, modulo $105$. Since anything congruent to $68$ modulo $105$ will also be a solution, you could also say $\boxed{x=105n+68}$ for each integer $n$.

$\endgroup$
1
$\begingroup$

$$ 2x = 3(mod 7) $$ $$ x+x= 3(mod 7) $$ $$ x = 5(mod 7) $$ $$ x = 8(mod 15) $$ $$ x = 15k_1 + 8 $$ $$ x = 7k_2 + 5 $$ $$ x = 105k_3 + c $$ $$ 0 \le c < 7*15 $$ $$ c(mod 7)=5 $$ $$ c = 15k_4+8 $$ $$ 0 \le k_4 < 7 $$ $$(15k_4+8)(mod 7)=3$$ $$ k_4 + 1 = 5 $$ $$ k_4 = 4 $$ $$ c=15*4+4 => c=68 $$ $$ x = 105k_3 + 68 $$ $$ 0 \le k_3 <\infty$$ $$ k_3 \in Z $$

$\endgroup$
-1
$\begingroup$

\begin{split} X&=15L+8\\ 2X&=30L+16=30(7m+u)+16 \end{split} [ where $u$ can be $0,1,2,3,4,5,6$] $$ 2X=(210m+28u+14)+(2u+2) $$ So $2u+2$ must leave remainder $3$ when divided by $7$,thus \begin{split} u&=4\\ 2X&=210m+136. \end{split} Therefore $X=105m+68$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .