1
$\begingroup$

Find all solutions using the Chinese Remainder Theorem.

x = 2 (mod 4)
x = 3 (mod 5)
x = 9 (mod 13)

My step is here:

a = 2 (mod 4) , a = 0 (mod 5) , a = 0 (mod 13)
b = 0 (mod 4) , b = 3 (mod 5) , b = 0 (mod 13)
c = 0 (mod 4) , c = 0 (mod 5) , c = 9 (mod 13)

The general solution for x is given by x = a + b + c + k*lcm(4,5,13) = a+b+c+260k

since a = 0 (mod 5) and a = 0 (mod 13), so a = 65m for some integer m then 65m = 2 (mod 4)

What should i do next? I think the step i write 65m - 2 = 4 is wrong

$\endgroup$
  • $\begingroup$ Not sure I understand the method you are using...how does it save any time? Just go stage by stage. To solve the first two congruences, write $x=2+4A$ and solve $2+4A\equiv 3 \pmod 5\implies A\equiv 4 \pmod 5$ so we have $x=2+4(4+5B)=18+20B$. Now solve $18+20B\equiv 9 \pmod {13}$. $\endgroup$ – lulu Dec 12 '19 at 10:28
  • 1
    $\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ – José Carlos Santos Dec 12 '19 at 10:28
  • $\begingroup$ Welcome to Mathematics Stack Exchange. $x\equiv-2\bmod4$ and $x\equiv-2\bmod5\implies x\equiv-2\bmod 20$. Now solve that and $x\equiv9\bmod 13$ $\endgroup$ – J. W. Tanner Dec 12 '19 at 10:31
  • 1
    $\begingroup$ I added an answer showing how to use the constant-case CRT optimization mentioned by @J.W.T This is the easiest approach in cases like this. $\endgroup$ – Bill Dubuque Dec 12 '19 at 16:52
1
$\begingroup$

We have ,

$$x\equiv2 \mod 4 \implies \color{#d05}{x=4a+2}\\ $$
$$\begin{align}x&\equiv3 \mod 5 \\4a+2&\equiv3\mod5\\ 4a&\equiv 1\mod5 \\ a &\equiv 4 \mod 5\implies\color{#2cd}{a = 5b+4}\end{align} $$
$$\begin{align}x&\equiv9 \mod 13 \\ 4(5b+4)+2&\equiv 9\mod13 \\ 20b+18&\equiv9\mod13 \\ 20b&\equiv 4\mod 13 \implies \color{#2c0}{b = 13c+8}\end{align} $$

So , $x = 4a+2 = 20b+18=260c + 178$

$\endgroup$
  • 1
    $\begingroup$ To fill the two gaps: $\ a = 5b+4\, $ so $\,x = 4a+2 = 4(5b+4) = 20b+18.\ $ $\bmod 13\!:\ 9\equiv x\equiv 20b+18 \equiv -6b+18\iff 6b\equiv 9\iff b\equiv 9/6\equiv 3/2\equiv 16/2\equiv 8.\ $ This method of solving the congruences in pairs works generally, see here for a proof. $\endgroup$ – Bill Dubuque Dec 12 '19 at 17:05
  • 1
    $\begingroup$ @BillDubuque I Left that for the O.P to fill in . On a different note , why was the answer downvoted ? $\endgroup$ – The Demonix _ Hermit Dec 12 '19 at 17:08
  • $\begingroup$ Maybe due to the gaps? The 2nd one, solving $\, 6b\equiv 9\pmod{13}\,$ is often a stumbling block in problems like these, so it helps to say how to solve it. $\endgroup$ – Bill Dubuque Dec 12 '19 at 17:28
  • $\begingroup$ The edit still doesn't show how you deduced $\bmod 13\!:\ 20b\equiv 4\iff b\equiv 8\ \ $ Also all arrows need to be bidirectional to concude that the necessary conditions are also sufficient (else root(s) might be extraneous) $\endgroup$ – Bill Dubuque Dec 12 '19 at 17:52
1
$\begingroup$

By CCRT $\,x\equiv -2\pmod{\!4,5}\!\iff\! x\equiv \color{#0a0}{-2\pmod{\!20}}$
$\,\bmod \color{#c00}{13^{\phantom{|^|}}}\!\!\!\!:\,\ 9\equiv x\equiv \color{#0a0}{-2\!+\!20}\color{#c00}k\equiv -2\!-\!6k\!\iff\! 6k\equiv -11\equiv-24\!\iff\! \color{#c00}{k\equiv -4}$
So we conclude $\ x = -2^{\phantom{|^i}}\!\!\!\!+\!20(\color{#c00}{-4\! +\! 13}n) = -82+260n,\, $ using only trivial mental arithmetic.


Remark $\ $ We solved $\bmod 13\!:\ 6x\equiv 6(-4)\ $ using $$\bmod n\!:\ ax\equiv ab\iff x\equiv b,\ \ {\rm when}\ \ \gcd(a,n)=1\!$$

since by Bezout, $\,a\,$ is invertible so cancellable from LHS, i.e. scale LHS by $\,a^{-1}\,$ to cancel $\,a,\,$ using the Congruence Product Rule.

Such linear congruences are often much easier to solve using modular fractions, e.g. see my comment below, and see here, and here and here for circa $20$ motley worked examples via a handful of methods.

$\endgroup$
  • $\begingroup$ I think you meant $-82$ where you typed $-84$ $\endgroup$ – J. W. Tanner Dec 12 '19 at 17:03
  • $\begingroup$ There's more than one way to skin a cat: $\mod 13:\;9\equiv-2-6k\iff 4\equiv2+6k\iff 2\equiv1+3k\iff 1\equiv 3k\iff k\equiv9$, so we'd conclude $x=-2+20(9+13n)=178+260n$ $\endgroup$ – J. W. Tanner Dec 12 '19 at 17:05
  • $\begingroup$ @J.W.T typo fixed, tx. Yes. many ways to evaluate $\!\bmod 13\!:\ \color{#c00}k\equiv \dfrac{2}6\equiv \dfrac{1}3\equiv \dfrac{-12}3\equiv -4,\ $ or $k\equiv \dfrac{2(-2)}{6(-2)}\equiv \dfrac{-4}1\ $ by Gauss's algorithm, or $\,\color{#c00}{\dfrac{2}{3}}\equiv \dfrac{15}3\equiv\color{#c00} 5\,\Rightarrow\,\dfrac{2}{6}\equiv \color{#c00}{\dfrac{2}{3}}\dfrac{1}2\equiv \dfrac{\color{#c00}5}2\equiv \dfrac{18}2\equiv 9\ \ $ $\endgroup$ – Bill Dubuque Dec 12 '19 at 17:23
1
$\begingroup$

Following @lulu's suggestion, but using Bezout coefficients, we first get for $\begin{cases} x\cong2\pmod4\\x\cong3\pmod5\end{cases}$, that $-1\cdot4+1\cdot 5=1$.

Now, by a well known result, detailed in the section "Using the existence construction" of "Computation" in this article , we get $x=(-4)\cdot 3+(5)\cdot 2=-2+20k$.

Then, repeat for $20$ and $13$. That is, take $\begin {cases} x\cong-2\pmod{20}\\x\cong 9\pmod{13}\end{cases}$.

So $2\cdot20+-3\cdot 13=1$.

And we get $x=40\cdot9+(-39)\cdot (-2)=438+260k$, or $x=178+260k$, as our solution.

$\endgroup$
  • 1
    $\begingroup$ \equiv not \cong. $\endgroup$ – lhf Dec 12 '19 at 11:18
  • $\begingroup$ You should explain the big leap from the Bzout equation to the CRT solution. One easy way is described here by scaling and rearranging the Bezout gcd equation $\endgroup$ – Bill Dubuque Dec 12 '19 at 18:14
  • $\begingroup$ @BillDubuque see for instance section $4.3$ of the following article en.m.wikipedia.org/wiki/Chinese_remainder_theorem $\endgroup$ – Chris Custer Dec 12 '19 at 21:05
  • $\begingroup$ I know how to do it, but you need to explain that to your readers, and it belongs in the answer, e.g. "by using Bezout to compute inverses then using this well-known CRT formula we obtain ...." That's a direct link to that Wiki section. Btw, if you've never seen it, the Bezout scaling & rearranging way is easier so worth knowing. $\endgroup$ – Bill Dubuque Dec 12 '19 at 21:18

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.