# On Chinese remainder theorem

Suppose we know $x\equiv 3 \bmod 11$ and $x\equiv 7\bmod 13$ and $0<x<143$ holds then CRT gives that $x=3\times 13[13^{-1}\bmod 11] + 7\times 11[11^{-1}\bmod 13]=39\times 6 + 77\times 6=696$ gives a solution but it is not within $0$ and $143$. So we take $696\bmod 143$ and choose $124$ as solution.

My query is say instead of $3$ we choose $3+11k$ and instead of $7$ we choose $7+13\ell$ for some $k,\ell\in\Bbb Z$ can we still recover $124$?

Instead of $696$ is there a direct way to get $124$?

We have $696=124+4(143)$. In general what is the quantity that goes in instead of $4$?

The direct way to $124$ would be to start with $7$ and see how many $13$s to add to make it into a number that is $3\bmod 11$.

Since $13\equiv \color{red}2 \bmod 11$, we can see that we need $(3-7)/\color{red}2 = -2\equiv 9\bmod 11$ copies of $13$. $7+9\cdot 13 = 7+117 = 124$.

we have $$x=3+11m,x=7+13n$$ from here we get the Diophantine equation $$11m-13n=4$$ with Solutions $$m=11+13k,n=9+11k$$ plugging this in the equations for $x$ $$x=124+11\cdot 13k$$ thus we obtain $$x=124$$ for $$k=0$$

Some people do CRT theorem problems like this. If $x\equiv 3\pmod{11},$ then $x = 3+11k$. Plug that into $x \equiv 7 \pmod{13}$ to get $3+11k \equiv 7 \pmod{13}$ which reduces to

$$11k \equiv 4 \pmod{13}$$

$$-2k \equiv 4 \pmod{13}$$

$$k\equiv -2 \equiv 11 \pmod{13}$$

So $x = 3+11\cdot 11 =124.$

• nice $\mbox{ }$ – T.... Apr 21 '17 at 12:17
• does this always work??? even if we do mod 13 first and 11 second and also for any pair (replace 13 and 11 by variables and 3 and 7 by variables) of modular residues – T.... Apr 21 '17 at 12:19
• Yes. And if you have more congruences, you can continue by plugging in $x = 124 + 142n$ into the next congruence and repeat. The official CRT requires the moduli to be relatively prime, but this method doesn't. It will find the solutions (if they exist.) – B. Goddard Apr 21 '17 at 12:25
• Well, with all those variables flying around, it's going to be harder to solve the second congruence, for sure. And if you don't know the values of these 4 variables, it will be hard to know how big or small your answer is. – B. Goddard Apr 21 '17 at 12:41
• @Robut See this answer for a proof that it always works. You can find worked examples in the list of linked posts there. – Bill Dubuque May 3 '17 at 15:52