1
$\begingroup$

Im trying to solve the following Simultaneous congruence.

$2x ≡ 3(mod\ 5) $
$3x ≡ 2(mod\ 4)$
$4x ≡ 3(mod\ 9) $

by Chinese remainder theorem
$x$ = $B_1c_1x_1 \ + \ B_2c_2x_2 \ + B_3c_3x_3 \ $

Where
$c_1 = 3$
$c_2 = 2 $
$c_3 = 3$

$B_1 = 2$x$3 $
$B_2 = 3$x$3 $
$B_3 = 3$x$2 $

$x_n=b_n(mod \ b_1)$
$x_1 = 1$
$x_2 = 1 $
$x_3 = no \ solution $

This is all i know and this is when $ x = c (mod \ n)$
but since there is a coefficient infront of x what should i change?
Thanks in advance.

Improve this question
$\endgroup$
1
$\begingroup$

All coefficients in front of $x$ are coprime to their respective moduli, which means we can multiply by the inverses of said coefficients. Take the first equation: $$2x\equiv3\bmod5$$ The multiplicative inverse of 2 modulo 5 is 3. Thus $$x\equiv2x\cdot3\equiv3\cdot3\equiv4\bmod5$$ Similarly $$x\equiv2\bmod4$$ $$x\equiv3\bmod9$$ Now the Chinese remainder theorem applies, and we get $x\equiv174\bmod180$.

Improve this answer
$\endgroup$
  • $\begingroup$ Can you help me understand $x≡2x⋅3≡3⋅3≡4mod5$ i dont understand that part. $\endgroup$ – Shehan Tearz Oct 16 '18 at 17:58
  • $\begingroup$ @ShehanTearz He multiplied the congruence $\,\color{#c00}2x\equiv 3\,$ by $\,\color{#c00}2^{-1}\equiv 3\pmod{\!5}\,$ to cancel the coefficient $\,\color{#c00}2.\,$ $\quad$ $\endgroup$ – Bill Dubuque Oct 16 '18 at 18:07
  • $\begingroup$ @BillDubuque so when considering the second equation $3x≡2(mod \ 4)$ we multiply it by $3^{-1}$? $\endgroup$ – Shehan Tearz Oct 16 '18 at 18:11
  • $\begingroup$ @ShehanTearz Right, and $\,3\equiv -1\,$ so $\,1/3 \equiv 1/(-1)\equiv -1\ \pmod{4},\ $ so you multiply the congruence by $-1,\,$ i.e. negate it. $\endgroup$ – Bill Dubuque Oct 16 '18 at 18:21
  • $\begingroup$ @BillDubuque Thanks $\endgroup$ – Shehan Tearz Oct 16 '18 at 18:28

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.