# Confused by process of solving linear congruences

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.

• 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. – Mike Earnest Sep 14 '16 at 16:42
• So the general solution would just be $x=-1790+11*7*13k$ for some $k\in\mathbb{Z}$? – user322548 Sep 14 '16 at 16:46
• That's right :) Equivalently, $x=212+2002k$ for $k\in \mathbb Z$. – Mike Earnest Sep 14 '16 at 16:48
• Should it be $2002k$ or $1001k$? – user322548 Sep 14 '16 at 16:51
• Whoops, it should be $1001k$, my bad! – Mike Earnest Sep 14 '16 at 16:53

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.

• 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. – user322548 Sep 14 '16 at 16:37