1
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ nice $\mbox{ }$ $\endgroup$ – T.... Apr 21 '17 at 12:17
  • $\begingroup$ 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 $\endgroup$ – T.... Apr 21 '17 at 12:19
  • $\begingroup$ 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.) $\endgroup$ – B. Goddard Apr 21 '17 at 12:25
  • $\begingroup$ 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. $\endgroup$ – B. Goddard Apr 21 '17 at 12:41
  • 1
    $\begingroup$ @Robut See this answer for a proof that it always works. You can find worked examples in the list of linked posts there. $\endgroup$ – Bill Dubuque May 3 '17 at 15:52

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.