# 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
@Dimitri. Exactly. – Rick Decker Dec 2 '13 at 17:29

Divide both sides of 12x + 28y = 20 by 4 gives: 3x + 7y = 5. Solve for x gives: x = (5 - 7y)/3 = 2 - 2y - (y+1)/3. Since x is an integer, -(y+1)/3 must be an integer so y + 1 = -3n and so y = -3n - 1 with n being an integer. So substituting y back into the equation and get x = (5 - 7(-3n - 1))/3 = (5 + 21n +7)/3 = 7n + 4. Thus (x,y) = (7n + 4, -3n - 1) with n an integer. Check: 3x + 7y = 3(7n + 4) + 7(-3n - 1) = 12 - 7 = 5 as claimed.

-

Divide 12x + 28y = 20 by 4, then 3x + 7y = 5.

3x = 5 mod 7.

3x = 12 mod 7.

x = 4 mod 7.

Therefore x = 4 + 7n and y = -1 - 3n for any value of n.

There are infinitely many solutions not just x = 4,11,18, and 25.

-