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

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.

• $(1)$ the correct solution modulo $23$ is $10$. $(2)$ You missed the "17" in "$x\equiv 9\mod 23$" Jan 1 at 11:22
• The final solution is $33$ Jan 1 at 11:24
• Does this answer your question? Using the Chinese Remainder Theorem to solve the following linear congruence: $17x \equiv 9 \pmod{276}$ Jan 1 at 11:38
• @Peter thanks peter , it's cleared now Jan 1 at 11:46
• @cineel no it's not . I solve my question completely in different way and do some mistakes in between which is already cleared by Peter. Jan 1 at 11:47

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.

• Wow thanks. I am reading this. If I have to ask any question about it, I will definitely ask you. Jan 1 at 16:37
• @AMIT Did you understand it? If not I can elaborate if you tell me which points are not clear. It is worth the effort to understand it since it will give you a better grasp of CRT (often the motivation for the CRT formula - explained in the linked post - is not presented in textbooks). Jan 2 at 18:44
• @BillDubuque nah after seeing your reply in linked post and then read here , i totally understand this. Actually this makes my proof of CRT more clear also . Thanks Jan 6 at 14:11
• @Amit Great, glad it helped. Jan 6 at 14:29

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}$$

• There is more than one error, and they can be precisely located by a standard proof debugging method - see my answer. Jan 1 at 16:01

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

• @AMIT MITAL, my methode is much easier if we do not have to use Chinies remainder theorem. Jan 5 at 19:57
• yeah sirous , thanks a lot. It's really a easy way for solving it. My motive wasn't to solve this question but learn myself the Chinese reminder Theorm and how can i use in more critical situation. But i learned to see this question in new way by your answer so thank you very much Jan 6 at 14:09
• @AmitMittal, You'r welcome Jan 6 at 15:43
• @Amit Essentially the answer solves $\, 17x -276k = 9\,$ by using the $\it extended\,$ Euclidean algorithm to compute $\,\gcd(17,276),\,$ a standard method - see here. The following comment presents it more explicitly in this form. Jan 16 at 9:07
• \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}\qquad Jan 16 at 9:07