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 know how to solve ax + by = c using Extended Algorithm. But with more than variables, I'm lost :(. To verify if it has an integer solution is easy, since we only need to check for gcd(a,b,c)|d. Other than that, how can we find an integer solution for this equation?

Thanks,
Chan

share|improve this question
    
Use the extended Euclidean algorithm several more times. –  Qiaochu Yuan Feb 8 '11 at 0:13
    
@Qiaochu Yuan: for each pair (a,b) then ((a,b), c)? –  Chan Feb 8 '11 at 1:01

1 Answer 1

up vote 5 down vote accepted

Suppose you need to solve $$a_1x_1 + a_2x_2 + a_3x_3 = c\qquad (1)$$ in integers.

I claim this is equivalent to solving $$\gcd(a_1,a_2)y + a_3x_3 = c\qquad (2)$$ in integers.

To see this, note that any solution to (1) produces a solution to (2): letting $g=\gcd(a_1,a_2)$, we can write $a_1 = gk_1$, $a_2=gk_2$, so then we have: $$c = a_1x_1 + x_2x_2 + a_3x_3 = g(k_1x_1) + g(k_2x_2) + a_3x_3 = g(k_1x_1+k_2x_2) + a_3x_3,$$ solving (2). Conversely, suppose you have a solution to (2). Since we can find $r$ and $s$ such that $g=ra_1+sa_2$, we have $$c = gy+a_3x_3 = (ra_1+sa_2)y +a_3x_3 = a_1(ry) + a_2(sy) + a_3x_3,$$ yielding a solution to (1).

This should tell you how to solve the general case $$a_1x_1+\cdots+a_nx_n = c$$ in terms of $\gcd(a_1,\ldots,a_n)$, which can in turn be computed recursively.

share|improve this answer
    
Great thanks ;) –  Chan Feb 8 '11 at 5:45
    
x_2x_2 seems wrong to me. –  user2820379 Oct 4 at 19:35
    
If you ever come back, have a look at this: math.stackexchange.com/q/1032593/146115 –  kuhaku Nov 21 at 17:00

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.