0
$\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
    Commented Jan 1, 2022 at 11:22
  • 1
    $\begingroup$ The final solution is $33$ $\endgroup$
    – Peter
    Commented Jan 1, 2022 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
    Commented Jan 1, 2022 at 11:38
  • $\begingroup$ @Peter thanks peter , it's cleared now $\endgroup$
    – user926846
    Commented Jan 1, 2022 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$
    – user926846
    Commented Jan 1, 2022 at 11:47

3 Answers 3

2
$\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$
    – user926846
    Commented Jan 1, 2022 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$ Commented Jan 2, 2022 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$
    – user926846
    Commented Jan 6, 2022 at 14:11
  • 2
    $\begingroup$ @Amit Great, glad it helped. $\endgroup$ Commented Jan 6, 2022 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$ Commented Jan 1, 2022 at 16:01
-1
$\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
    Commented Jan 5, 2022 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$
    – user926846
    Commented Jan 6, 2022 at 14:09
  • $\begingroup$ @AmitMittal, You'r welcome $\endgroup$
    – sirous
    Commented Jan 6, 2022 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$ Commented Jan 16, 2022 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$ Commented Jan 16, 2022 at 9:07

You must log in to answer this question.