10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Use the extended Euclidean algorithm several more times. $\endgroup$ – Qiaochu Yuan Feb 8 '11 at 0:13
  • $\begingroup$ @Qiaochu Yuan: for each pair (a,b) then ((a,b), c)? $\endgroup$ – Chan Feb 8 '11 at 1:01
10
$\begingroup$

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 + a_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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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