2
$\begingroup$

I'm trying to solve the following modular arithmetic question using the Chinese Remainder Theorem, using this link. (We learned a different method in our class, but I found this easier to grasp). $$x \equiv 1 (\text{mod} \ 5)$$ $$x \equiv 2 (\text{mod} \ 7)$$ $$x \equiv 3 (\text{mod} \ 9)$$ $$x \equiv 4 (\text{mod} \ 11)$$

I then represented $x$ as a sum of $4$ boxes, such that the first term is "related" to $\text{mod} \ 5$ (i.e. the $1^{st}$ term will not be made $0$ due to the $\text{mod} \ 5$), the second term is related to $\text{mod} \ 7$ and so on. Here's what I mean by "related":

If we only consider $\text{mod} \ 5$, the value of box $1$ is $693$, the value of box $2$ is $495$, then $693 \ \text{mod} \ 5 = 3$ but $495 \ \text{mod} \ 5 = 0$. Likewise, if we only consider $\text{mod} \ 7$, then the value of box $1$ is $693 \ \text{mod} \ 7 = 0$ but $495 \ \text{mod} \ 7=5$. And so on...

After doing all that, I have $$x = (7 \times 9 \times 11) + (5 \times 9 \times 11) + (5 \times 7 \times 11) + (5 \times 7 \times 9)$$

The next step is applying the $\text{mod} \ 5$ to $x$: $$\begin{align} x \ \text{mod} \ 3 &\equiv 691 \ \text{mod} \ 5 + 495 \ \text{mod} \ 5 + 385 \ \text{mod} \ 5 + 315 \ \text{mod} \ 5 \\ &\equiv 693 \ \text{mod} \ 5 + 0 + 0 + 0 \\ &\equiv 693 \ \text{mod} \ 5 \\ &\equiv 3 \ (\text{mod} \ 5) \end{align}$$

This is where I get stuck. In the video, and the video doesn't explain how to deal with such a scenario.

PS - If there is a more "intuitive" or more efficient version of the Chinese Remainder Theorem, I'd be grateful if you could share it.

PPS - Sorry if the question is a bit awkwardly formulated. As you can guess this is my first doing this.

$\endgroup$
  • $\begingroup$ Have you seen en.m.wikipedia.org/wiki/Chinese_remainder_theorem#Computation ? $\endgroup$ – Alek Fröhlich Jun 6 at 15:34
  • $\begingroup$ Some formatting tips. Look at how at how I aligned the calculations. You don't have to worry about putting spaces in expressions; MathJax will take care of that. There are two operators for modulus: $x\pmod{17}$ gives $x\pmod{17}$ and $x\mod{17}$ gives $x\mod{17}$ Of course, if you don't like the spacing, you will have to do what you did with \text or use \operatorname. $\endgroup$ – saulspatz Jun 6 at 15:45
  • $\begingroup$ Why on earth should $x = (7 \times 9 \times 11) + (5 \times 9 \times 11) + (5 \times 7 \times 11) + (5 \times 7 \times 9)$? If $x=17$ and $x\equiv 1 \pmod 2$ and $x\equiv 2\pmod 3$ and $x\equiv 2\pmod 5$, we don't have $17=x = 3*5 + 2*5 + 2*3=31$. $\endgroup$ – fleablood Jun 6 at 16:06
  • $\begingroup$ Why are you doing mod 3 instead of mod 9.? $3$ is not one of your components. $\endgroup$ – fleablood Jun 6 at 16:14
  • $\begingroup$ "the video doesn't explain how to deal with such a scenario. " You get that the "experimental" $x\equiv 3\pmod 5$ but the "real" $x \equiv 1\pmod 5$. So you need to multiply $3\pmod 5$ by $?$ to get $1\pmod 5$. So $3*2 \equiv 1\pmod 5$ you will get the "real" $x$ is $2*(7\cdot 9\cdot 11) + ......$ The video explained that in the second mod they tested but I oppose the idea of setting $x=7*9*11+5*9*11+ 5*7*11+5*7*9$. $x$ ISN"T equal to that. $x = a*695+b*495+c*385+d*315$ $\endgroup$ – fleablood Jun 6 at 17:58
1
$\begingroup$

That is a TERRIBLE video. But the technique is interesting.

SO we have

$x = a*693 + b*495 + c*385+d*315$.

First we do $\mod 5$.

$x \equiv 3*a + 0 +0 +0\equiv 3a \pmod 5$ and we need $3a \equiv 1 \pmod 5$. Now trial and error shows us that $3*2 = 6 \equiv 1 \pmod 5$ so $a=2$ will do.

Now $\mod 7$

$x\equiv 0 + b*5 + 0 + 0\equiv 5b \pmod 7$. So we need $5b\equiv 2\pmod 7$.

He doesn't explain how do do this. Trial and error shows us that $5*6 =30\equiv 2 \pmod 2$ so $b=6$ will do.

Then we $\mod 9$ (not $3$)

$x \equiv 7c \pmod 9$ and we need $7c \equiv 3\pmod 9$.

Okay. No trial and error any more.... $7c = 3 + 9k$ so $7\frac c3= 1+ 3k$ so $3|c$. Le $c = 3e$. $7e = 1+3k$ so $(2*3+1)e= 1+3k$ so $e = 1 + 3(k-2)$ so we can have $e=1$ and $c = 3$. $7*c = 21 =3+18 \equiv 3 \pmod 9$.

So $c= 3$ will do.

And finally $\mod 11$ we have $x \equiv 315d\equiv 7d\pmod {11}$ so we need $7d\equiv 4\pmod 11$.

$7d = 4 + 11k$

$(11-4)d= 4 + 11k$

$-4d = 4 + 11(k+d)$ so $d=-1$ will do.

So we can have $x = 2*693 + 6*495+ 3*385 - 315=5196$

Of course that not the smallest positive answer.

To get a reasonable answer I'd alternate a few negative and positive values.

Instead of $b=6$ we can have $b\equiv 6 \equiv -1 \pmod 7$ and use $b=-1$ to get

$x = 2*693 -495 + 3*385 -315=1731$ will do. (And if my instincts are right that is smallest value between $0$ and $5\times 7\times 9\times 11 = 3465$

$2*693 -495 + 3*385 -315\equiv 2*3 + 0 + 0 + 0 \equiv 1 \pmod 5$.

And $2*693 -495 + 3*385 -315\equiv 0-5 + 0 + 0 \equiv 2\pmod 7$.

And $2*693 -495 + 3*385 -315\equiv 0+0+3*7 +0+0\equiv 21 \equiv 3 \pmod 9$

And $2*693 -495 + 3*385 -315 \equiv 0+0+0-7\equiv 4 \pmod {11}$.

.....

I've never seen this method before.... but I ... sort of liked it. But the presentation in that video was terrible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ To determine the smallest positive value for $x$, can't you simply do $5196 \mod 3465=1731$? $\endgroup$ – Ski Mask Jun 9 at 11:43
  • 1
    $\begingroup$ Yeah but I'd rather get a smaller answer from the begining. If we have $a693 + b*495+c*385 + d*315$ and $a,b,c,d$ are all positive I'm probably going to get a very large number. To keep in in bound It make sense to choose $a*693 - (7-b)495 + c*385-(11-d)*315$. That'll probably make the arithmetic a lot easier anyway. $\endgroup$ – fleablood Jun 9 at 15:11
2
$\begingroup$

There should be $x = (7 \times 9 \times 11)\cdot(7 \times 9 \times 11)^{-1}_5\cdot 1 $ ${}+ (5 \times 9 \times 11)\cdot(5 \times 9 \times 11)^{-1}_7\cdot 2 $ ${}+ (5 \times 7 \times 11)\cdot(5 \times 7 \times 11)^{-1}_9\cdot 3 $ ${}+ (5 \times 7 \times 9)\cdot (5 \times 7 \times 9)^{-1}_{11}\cdot 4$ for this approach.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hmm, it is a bit troubling to see inverse $\mod 9$ since it is not necessarily true for non–primes $\endgroup$ – crystal_math Jun 6 at 16:01
  • 1
    $\begingroup$ There's a version of CRT that has as a pre-condition that all modules considered have to be mutually coprime. Hence the inverse exists. Anyway as $gcd(m_i,m_j)=1$ one may use extended euclidean algorithm to compute $am_i+bm_j=1$ so $b$ will be such inverse of $m_j$ (i.e. $m_j^{-1}$) $\pmod{m_i}$. Then we multiply them up. $\endgroup$ – Alexey Burdin Jun 6 at 16:29
  • $\begingroup$ Oh yeah. My bad. $\endgroup$ – crystal_math Jun 6 at 16:39
  • $\begingroup$ You need to solve $\omega \times 5\cdot 7\cdot 11 \equiv 3 \pmod 9$. There is no inverse mod $9$ that work for all values but as $5\cdot 7\cdot 11$ is coprime to $9$ (That's the entire point) then there is an inverse for $5*7*11$ which would be the inverse for $(-4)(-2)2\equiv 16\equiv 7$ which is...counts on fingers $7,14,21,28$.... $4$. So $(3*4)*5*7*11 \equiv 3\pmod 9$. $\endgroup$ – fleablood Jun 6 at 17:54
1
$\begingroup$

I think the best way for me to solve a CRT problem is like this: $$x \equiv1 \pmod{5} \implies x \in \{1,6,11,16,21,26\dots\}$$ $$x \equiv4 \pmod{11} \implies x \in \{4,15,26,\dots\}$$

Now one can immediately see the intersection at $x=26$, and indeed $x \equiv 26 \pmod{55}$ satisfies both $x \equiv1 \pmod{5}$ and $4 \pmod{11}$.

Similarly, $$x \equiv 2 \pmod{7} \implies x \in \{2,9,16,23,30,\dots\}$$ $$x \equiv 3 \pmod{9} \implies x \in \{3,12,21,30,\dots\}$$ So $x \equiv 30 \pmod{63}$

Now, from there I can solve it with the casual method: $$x \equiv26 \pmod{55} \implies x=55k+26$$ $$\implies55k+26 \equiv30 \pmod{63} \implies 55k \equiv4 \equiv 130 \pmod{63}$$ $$\implies 11k \equiv 26 \equiv 341 \pmod{63} \implies k \equiv 31 \pmod{63} \implies k=63j+31$$ $$\implies x=55(63j+31)+26=3465j+1731 \implies x \equiv 1731 \pmod{3465}$$ Noting, of course, that $3465=5\cdot7\cdot9\cdot11$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The best way to do the Chinese Remainder Theorem is to do it one at a time, and merge two conditions repeatedly.

For two values, the best way to compute is given in the Wikipedia page, under the "Case of two moduli" section.

From here, you want to contract conditions: you can convert $x \equiv 1 \pmod 5, \; x \equiv 2 \pmod 7$ into $x \equiv 16 \pmod {35}$ using this technique, and then repeat on $35$ and $9$ to find a condition for $x$ modulo $315$, and finally finish using the modulo $315$ condition and the modulo $11$ condition.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "best" is pretty subjective. I rather think the technique described in the OP works pretty well. $\endgroup$ – fleablood Jun 7 at 8:03

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.