Using the Chinese Remainder Theorem, $17x \equiv 9 \pmod{276}$

Question

I want to uses the Chinese Remainder Theorem to solve $17x \equiv 9 \pmod{276}$ by breaking it up into a system of three linear congruences, $$17x \equiv 9 \pmod{3}$$ $$17x \equiv 9 \pmod{4}$$ $$17x \equiv 9 \pmod{23}$$ For that I reduced it to

$$x \equiv 0 \pmod{3}$$ $$x \equiv 1 \pmod{4}$$ $$17x \equiv 9 \pmod{23}$$

So for converting this In terms of chinese reminder Theorem , I calculate The solution Of last linear Congurence as

$$x \equiv 13 \pmod{23}$$

So Our System Of Linear Congurence is now :

$$x \equiv 0 \pmod{3}$$ $$x \equiv 1 \pmod{4}$$ $$x \equiv 13 \pmod{23}$$

And now I apply the Chinese Remainder Theorem on it such that

$$92b_1 \equiv 1 \pmod{3}$$ $$69b_2 \equiv 1 \pmod{4}$$ $$12b_3 \equiv 1 \pmod{23}$$ So $b_1$ = 2 , $b_2$ = 1 , $b_3$ = 2

So simultaneous solution be

$$92\cdot2\cdot0 + 69\cdot1\cdot1 + 13\cdot2\cdot5 = 199$$

But it's wrong (@_@)༎ຶ‿༎ຶ . Can please Please Someone can Correct me.

Answer 1

as Peter has said in the comments,
$x\equiv 10\pmod{23}$
the last equation is supposed to be:
$92*2*0 +69*1*1 + 12*2*10=309\equiv 33\pmod{276}$

Answer 2

Below I show how to easily find the errors. Recall (read!) that the reason the CRT formula works is because each summand has the sought value for one modulus, and is $\equiv 0\,$ for all others. Thus your last summand $\,s = \color{#0a0}{13}\cdot 2\cdot\color{#c00} 5\,$ should satisfy $\,s\equiv 0 $ mod $3\ \&\ 4$, and have the sought value mod $23$, i.e. $\,s\,$ should be a root of $\,17\:\! s\equiv 9\pmod{\!23}$.

But your $\,s\not\equiv 0 $ mod $3\ \&\ 4$. The CRT formula achieves that by including a $\rm\color{#0a0}{first\ factor}$ of $\,3\cdot 4 = 12$, but your first factor is $\color{#0a0}{13}$. Fixing that typo your summand becomes $\,s = 12\cdot 2\cdot\color{#c00} 5$.

Finally $\,s\,$ must be a root of $17s\equiv 9\pmod{23}\,$ but yours has $17s\equiv 15\not\equiv 9$. The CRT formula achieves that by choosing a root $\,r\,$ then writing $\,s = 12\:\!(12^{-1}\bmod 23)\:\!r\equiv r.\,$ Your 2nd factor $\,12^{-1}\equiv 2\,$ is correct but your $\rm\color{#c00}{3rd\ factor}$ $\,r\equiv \color{#c00}5\,$ is not a root since $17\cdot 5\equiv 17\not\equiv 9$. Let's fix that by calculating a root $\,r\,$ by twiddling to exact quotients

$$\bmod 23\!:\,\ 17r\equiv 9\iff r\equiv \dfrac{9}{17}\equiv\dfrac{9}{-6}\equiv\dfrac{-3}{2}\equiv\dfrac{20}2\equiv 10\qquad\qquad$$

Thus the correct summand for modulus $\,23\,$ is $\,s = 12\cdot 2\cdot 10$.

Notice how a good understanding of the reason that the CRT formula works allowed us to easily troubleshoot the problem. This is true in general - if you understand the idea behind a proof or formula then you can debug an erroneous application of it be going through the proof line-by-line to determine the first place where the proof breaks down in your special case. For more examples of this debugging method see a "proof" that $1 = 0$ and a "proof" that $2 = 1$.

---

Below I explain from a general viewpoint the method used in sirous's answer.

$\begin{align}\ 17x&\equiv 9\!\!\!\pmod{\!276}\\[.2em] \iff\qquad \color{#c00}{17}x {-}\color{#0a0}{276}k &= 9,\ \, {\rm note}\ \,\color{#0a0}{276\equiv 4}\!\!\!\pmod{\!\color{#c00}{17}},\,\ \rm so\\[.2em] \iff\!\:\! \bmod \color{#c00}{17}\!:\ \ \ {-}\color{#0a0}4k&\equiv 9\equiv -8\iff \color{#c00}{k\equiv 2}\\[.3em] \iff\:\! \qquad\qquad\quad\ \ x\, &=\, \dfrac{9\!+\!276\color{#c00}k}{17} = \dfrac{9\!+\!{276}(\color{#c00}{2\!+\!17j})}{17} \equiv 33\!\!\!\!\pmod{\!276} \end{align}$

The above method may be viewed a bit more conceptually as computing a value of $\,\color{#c00}k\,$ that makes exact the following quotient $\, x\equiv \dfrac{9}{17}\equiv \dfrac{9+276\color{#c00}k}{17}\pmod{\!276},\,$ cf. inverse reciprocity.

Answer 3

$17x\equiv 9\bmod 276$

$276=16\times 17 +4\Rightarrow 17x=9+(16(17)+4)k$

$\Rightarrow 17(x-16k)=9+4k$

For $k=2$ we have:

$17(x-16\times2)=9+4\times 2=17$

$\Rightarrow x-32=1\rightarrow x=33$

$k=53\rightarrow x-53\times 16=13\times 17\rightarrow x=861$

K makes an arithmetic progression with common difference $d=51$:

$k= 2, 53, 104, 155\cdot\cdot\cdot$