Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.