Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|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
up vote 7 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|cite|improve this answer
Great thanks ;) – Chan Feb 8 '11 at 5:45
x_2x_2 seems wrong to me. – user2820379 Oct 4 '14 at 19:35
If you ever come back, have a look at this: – kuhaku Nov 21 '14 at 17:00

Your Answer


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.