A normal linear Diophantine equation would be some:
$ax + by = c$ where $a$ and $b$ are constants. Solution can be found using Euclid's Extended Algorithm.
But what about for longer equations such as:
$ax + by + cz = d$?
Is there a way to solve these kinds of equations for more than two variables?
It's this question that I've been asking myself. Say that I have some equation:
$aw + bx + cy + dz = e$
Such that $a, b, c, d$ are constants and $w, x, y, z$ are either 0 or 1. I want to be able to show if a solution exists for some $e$.
Of course, there's always the brute force method to solve, but is there anything more elegant?
Best Answer
The diophantine equation $ax+by = r$ can be solved if and only if $\gcd(a,b)\mid r$. In that case, the Euclidean algorithm provides an effective way of finding all solutions.
The key to this is that the collection of all possible values of $ax+by$ is precisely the set of all multiples of $\gcd(a,b)$.
Now consider $ax+by+cz = t$. This is equivalent to solving $\gcd(a,b)w + cz = t$, since any solution to the latter yields a solution of the former (by suitable choice of $x$ and $y$ so that $ax+by = \gcd(a,b)w$) and conversely, any solution to $ax+by+cz=t$ yields a solution to $\gcd(a,b)w+cz = t$. Thus, the diophantine equation $ax+by+cz=t$ is equivalent to the diophantine equation $\gcd(a,b)w+cz=t$, which can be solved if and only if $\gcd(\gcd(a,b),c) = \gcd(a,b,c)$ divides $t$.
Similar considerations yield that the diophantine equation $$a_1x_1+a_2x_2+\cdots+a_kx_k = d$$ with $k\gt 0$ has a solution if and only if $\gcd(a_1,a_2,\ldots,a_k)$ divides $d$. When it does, the Euclidean algorithm provides an effective way of finding the solutions.
Gerry Myerson has already addressed the other part of your question.