3
$\begingroup$

I'm trying to do some questions on the Chinese remainder theorem, I've being reading the Wikipedia explanation but I still don't get it. Can someone explain it to me, please?

Here is the question I'm working with. If you have a simpler example, that would be great.

Find an integer $x$ such that $x\equiv2\bmod5$, $x\equiv1\bmod13$ and $x\equiv5\bmod17$.

$\endgroup$
  • $\begingroup$ There is an explicit example on Wikipedia. What part of that example do you not understand? $\endgroup$ – TMM Apr 16 '13 at 10:02
  • $\begingroup$ After finding $11$ as a common subset, why does it then say $x = 11 (mod 60)$ ? en.wikipedia.org/wiki/… $\endgroup$ – Adegoke A Apr 16 '13 at 10:04
  • $\begingroup$ Equation 1: $x = 2 + 3 × t$ (mod 3)// Equation 2: $x = 3 + 4 × s$ (mod 4)// Equation 3: $x = 1 + 5 × u$ (mod 5)// Solving the 3 equations simultaneously, we get $x = 11 + 60k$, where $k\in\mathbb{Z}$ $\endgroup$ – Poseidonium Apr 16 '13 at 10:08
  • $\begingroup$ @Poseidonium I don't get how the " substituting the x from equation 1 into equivalence 2" part. $\endgroup$ – Adegoke A Apr 16 '13 at 10:11
  • $\begingroup$ I think my answer is clearer. Although it does use 5, 13, 17. Which is more confusing. Hopefully, it can help you work out the wiki page. $\endgroup$ – Poseidonium Apr 16 '13 at 10:21
3
$\begingroup$

It's easier than usual because an evident constant-case optimization of CRT exists. Notice that $\rm\ x \equiv 1\equiv \color{#0a0}{-12}\:\ (mod\ 13),\:$ and $\rm\:x\equiv 5\equiv \color{#0a0}{-12}\ \: (mod\ 17),\:$ so $\rm\:13,17\mid x\!+\!\color{#0a0}{12},\:$ so $\rm\:13\cdot 17\mid x\!+\!\color{}{12},\:$ by $\rm\:lcm(13,17)= 13\cdot 17.\:$ So $\rm\: x = -12 + 13(17 j)\:$ for some integer $\rm\:j.\:$ Hence, applying CRT $\rm mod\ \color{blue}5\!:\: 2 \equiv x \equiv -12\! +\! 13(17j)\equiv -2\! +\! j\Rightarrow j\equiv \color{#c00}{ 4},\,$ so $\rm\,x\equiv -12\! +\! 13(17(\color{#c00}4\!+\!\color{blue} 5i)\!)\!\equiv 872\!+\!1105i$

$\endgroup$
  • 2
    $\begingroup$ Don't say "It is very easy". The poor OP has been struggling with this for hours, you're just going to make him feel small and insignificant. You only believe it is easy because you know and understand this all already... $\endgroup$ – user1729 Apr 16 '13 at 20:00
  • 2
    $\begingroup$ @user1729 One part of good teaching is giving the reader a sense of what level of difficulty lies ahead, e.g. whether the following proof will be easy or difficult. Hence my remark. One can find similar remarks by many eminent authors of textbooks. Yoo too have remarked about how "easy" some proofs are, as have many other MSE answerers. If that is the reason for the downvote, then I think it is ill-advised, since it may mislead the OP into thinking that there is an error or some other major problem, when there is not. $\endgroup$ – Math Gems Apr 16 '13 at 20:23
  • $\begingroup$ Sure, give the reader a sense of what level of difficulty lies ahead. However, there is a difference between telling them the problem they have been working on for ages is easy and telling them that something they have not come across before is easy. In one case you are bringing them down, in the other you are warning them. I think it is helpful to give them an idea of the level, but say something like "I think you are perhaps thinking too much about it". Try to make them feel good, rather than stupid... $\endgroup$ – user1729 Apr 17 '13 at 15:35
5
$\begingroup$

Considering $x \equiv 1$ (mod 13) and $x \equiv 5$ (mod 17), we get $x = 1 + 13a$ and $x = 5 + 17b$. So, $1+13a=5+17b$.

So, by letting $a=a'-1$ and $b=b'-1$, we get $x = -12 + 13a' = -12 + 17b'$, $x \equiv -12$ (mod $13\times17$). ie. $x\equiv -12$ (mod 221)

Considering $x\equiv -12$ (mod 221) and $x \equiv 2$ (mod 5), we get $x = -12 + 221m = 2 + 5n$.

We can let $m=m'+4$ and $n=n'+174$ to get $x=872 + 221m' = 872 + 5n'$.

So, we get $x = 872 + 1105k$, or $x \equiv 872$ (mod 1105).

$\endgroup$
  • $\begingroup$ Thank you. I just want to confirm something. At first, I was wondering why $a=a′−1$ , $b=b′−1$, $m=m′−4$ and $n=n′−174$ but then I realized that you were trying to get a $-12$ for the first one and $872$ for the second one. Am I right? But how did you go about knowing what to subtract from $b′$ or any other variable? $\endgroup$ – Adegoke A Apr 16 '13 at 10:34
  • 1
    $\begingroup$ @AdegokeA smart guesses for the 13 and 17 case. While 221 and 5 case is due to the last digit. $\endgroup$ – Poseidonium Apr 16 '13 at 11:07
  • $\begingroup$ What do you mean by 'the last digit'? I'm now trying to use this example to work out the Wikipedia example. I used $a = a' - 1$ and for b also. But now I'n on the second part and I dont know what number to use. $\endgroup$ – Adegoke A Apr 16 '13 at 11:11
  • $\begingroup$ The last digit is in reference to the fact that 5 is half of 10 and so any mod 5 is going to represent a couple of cases mod 10 which is a single digit. 2 mod 5 would imply that the final digit in reading from left to right will be either 2 or 7. If you have to, map out 0-9 and notice that these mod 5 will become 0,1,2,3,4,0,1,2,3,4 for the digits 0,1,2,3,4,5,6,7,8,9. $\endgroup$ – JB King Apr 16 '13 at 20:04
1
$\begingroup$

I'd do it as follows (which is, basically, one of the most usual proofs of the CRT): we have the coprime (primes, in fact) integers $5,13,17$:

$$(1)\;\;\;\text{solve}\;\; 13\cdot 17y_5=1\pmod 5:\;\;\;\color{red}5\cdot(-44)+\color{red}{13\cdot 17}\cdot1=1\;\;\;\implies \color{blue}{y_5=1}$$

$$(2)\;\;\;\;\text{solve}\;\; 5\cdot 17y_{13}=1\pmod {13}\;\;\;\color{red}{13}\cdot (-13)+\color{red}{5\cdot17}\cdot2=1\;\;\;\implies \color{blue}{y_{13}=2}$$

$$(3)\;\;\;\;\;\,\text{solve}\;\; 5\cdot 13y_{17}=1\pmod {17}\;\;\;\color{red}{17}\cdot23+\color{red}{5\cdot13}\cdot(-6)=1\;\;\;\implies \color{blue}{y_{17}=-6}$$

and now define

$$x:=\color{green}2\cdot\color{blue}1\cdot13\cdot17+\color{green}1\cdot\color{blue}2\cdot5\cdot17+\color{green}5\cdot\color{blue}{(-6)}\cdot5\cdot13=-1338=-233=872\pmod{5\cdot13\cdot17}$$

You could, of course, have chosen $\,11\,$ instead of $\,-6\,$ in (3) above, but you'd have obtained a much bigger solution, $\,4187\pmod{5\cdot13\cdot17}\,$ , so a negative solution here and there isn't usually a problem but, in fact, an advantage.

The biggest pro in the above method, in my opinion, is that it serves you in any case, whether you have 2, 3 or more congruencies to solve, and is very mechanical.

$\endgroup$

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.