# Solving system of linear congruences

I have the following:

$$12x+28y=20$$

I'm trying to find solutions to the equation above defined by: $12x\equiv 20\pmod {28}$

The GCD is $d = gcd(28,12)=4$ and since $4 | 20$, then there are 4 solutions that exist. (please correct me if I'm wrong).

Using the extending Euclidean Algorithm, we find $x_0=-2$ and $y_0=1$. The general solution is defined by: $$x_0+t(\frac nd)$$ which in turn gives $-2+7t$ in our case. But how can we have a negative remainder if $x=-2 \pmod 7$ which can't happen.

-
Why do you think that $x\equiv -2\pmod{7}$ doesn't have a solution? What about $x\equiv 5\pmod{7}$? –  Rick Decker Dec 1 '13 at 22:50
You're right, it is a solution. The reason why I'm confused it because the solution given to this problem is $4+7k$... –  Dimitri Dec 1 '13 at 23:27
Ah. I misunderstood your question. You just missed a step. See below. –  Rick Decker Dec 2 '13 at 3:00

Your extended Euclid result, $x_0=-2, y_0=1$ is a solution to $12x+28y=\gcd(12, 28)=4$. However, you want solutions to $12y+28z=20$ so you need to multiply your solutions by $5$, namely $x=5(-2)+7t=-10+7t\equiv 4\pmod7$. Since there are 4 solutions to the original equation, as you've correctly noticed, we'll have $x\equiv 4, 11, 18, 25\pmod{28}$.
So after you get $x_o$ and $y_o$, you need to multiply it back to 20 since the equation is divisible by 4? –  Dimitri Dec 2 '13 at 15:32