1
$\begingroup$

I am given the system of linear congruences:

$x\equiv 2$ mod $7$, $x\equiv 3$ mod $11$, and $x\equiv 4$ mod $13$.

I start to solve by substituting the first equation into the second, yielding: $x=2+7(-3+11m)$ for some $m\in\mathbb{Z}$. With some algebra, we find $x=-19+77m$.

I then plug that result for $x$ into the 3rd equation to find: $77m-13n=23$ for some $m,n\in\mathbb{Z}$. Then, I use Euclid's Algorithm to solve that equation, where I find $m=-23$ and $n=-138$.

What do I do with these solutions? How can I continue with the original problem? Edit: Please keep answers within the realms of this method.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You're pretty much done! $x = -19 + 77m$, and you just found $m = -23$, so $x = -19 + 77(-23) = -1790$. If you like, you can add some multiple of $7\cdot 11\cdot 13$ to this value to make it positive, while still keeping it a solution. $\endgroup$ – Mike Earnest Sep 14 '16 at 16:42
  • $\begingroup$ So the general solution would just be $x=-1790+11*7*13k$ for some $k\in\mathbb{Z}$? $\endgroup$ – user322548 Sep 14 '16 at 16:46
  • 1
    $\begingroup$ That's right :) Equivalently, $x=212+2002k$ for $k\in \mathbb Z$. $\endgroup$ – Mike Earnest Sep 14 '16 at 16:48
  • $\begingroup$ Should it be $2002k$ or $1001k$? $\endgroup$ – user322548 Sep 14 '16 at 16:51
  • 1
    $\begingroup$ Whoops, it should be $1001k$, my bad! $\endgroup$ – Mike Earnest Sep 14 '16 at 16:53
1
$\begingroup$

I dont know if this is the most efficient but it works. You have three primes $p$,$q$,$r$. Find $a,b,c$ such that $$aqr \equiv 1 \mod p$$ $$bpr \equiv 1 \mod q$$ $$cpq \equiv 1 \mod r$$

Then to solve $$x\equiv \alpha \mod p$$ $$x\equiv \beta \mod q$$ $$x\equiv \gamma \mod r$$

you have $aqr\alpha+bpr\beta+cpq\gamma$.

In this case we have $$(-2)11\cdot 13 \equiv 1 \mod 7$$ $$(4)7\cdot 13 \equiv 1 \mod 11$$ $$(-1)7\cdot 11 \equiv 1 \mod 13$$

So your solution is $$2(-2)11\cdot 13 +3(4)7\cdot 13 +4(-1)7\cdot 11 =212$$

Which you can check is indeed a solution.

Improve this answer
$\endgroup$
  • $\begingroup$ Yes, thank you. Unfortunately, in this problem, I am restricted to using the "iterative" method aka the method I try above. I'll upvote you for your help though. $\endgroup$ – user322548 Sep 14 '16 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy