How to find an integer solution for general Diophantine equation $ax + by + cz + dt... = N$

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

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.