3
$\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$
7
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.