1
$\begingroup$

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.

$\endgroup$
10
  • 5
    $\begingroup$ $(1)$ the correct solution modulo $23$ is $10$. $(2)$ You missed the "17" in "$x\equiv 9\mod 23$" $\endgroup$
    – Peter
    Jan 1 at 11:22
  • 1
    $\begingroup$ The final solution is $33$ $\endgroup$
    – Peter
    Jan 1 at 11:24
  • 3
    $\begingroup$ Does this answer your question? Using the Chinese Remainder Theorem to solve the following linear congruence: $17x \equiv 9 \pmod{276}$ $\endgroup$
    – cineel
    Jan 1 at 11:38
  • $\begingroup$ @Peter thanks peter , it's cleared now $\endgroup$ Jan 1 at 11:46
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 1 at 11:47

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Wow thanks. I am reading this. If I have to ask any question about it, I will definitely ask you. $\endgroup$ Jan 1 at 16:37
  • $\begingroup$ @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). $\endgroup$ Jan 2 at 18:44
  • $\begingroup$ @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 $\endgroup$ Jan 6 at 14:11
  • 2
    $\begingroup$ @Amit Great, glad it helped. $\endgroup$ Jan 6 at 14:29
1
$\begingroup$

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

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

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

$\endgroup$
6
  • $\begingroup$ @AMIT MITAL, my methode is much easier if we do not have to use Chinies remainder theorem. $\endgroup$
    – sirous
    Jan 5 at 19:57
  • $\begingroup$ 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 $\endgroup$ Jan 6 at 14:09
  • $\begingroup$ @AmitMittal, You'r welcome $\endgroup$
    – sirous
    Jan 6 at 15:43
  • $\begingroup$ @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. $\endgroup$ Jan 16 at 9:07
  • $\begingroup$ $$\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$$ $\endgroup$ Jan 16 at 9:07

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.