# $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C)\mid D$ [duplicate]

I read today that $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C\mid D$ but I can't find it again, I also can't find any Diophantine equations with 3 variables that doesn't have solutions so I'm starting to suspect that I'm remembering something wrong.

My questions are: Are there Diophantine equations with 3 variables that has no solutions?

Is the statement in the title correct?

Note: $A,B,C,D,x,y,z\in \mathbb Z$ and $A,B,C\neq0$.

## marked as duplicate by apnorton, graydad, saz, Michael Lugo, user147263 Jan 23 '15 at 19:54

• Note that $\gcd(gcd(A,B),C)=\gcd(A,B,C)$. For a Diophantine equation without a solution, take for instance $2x+2y+2z=5$. – Arthur Nov 21 '14 at 20:28
• This is the Euclidean Algorithm, I think. – Joe Z. Nov 21 '14 at 20:28
• All 3-variable Diophantine equations you've found have solutions; what does that have to do with remembering something wrong, when the example you give also does? – MackTuesday Nov 21 '14 at 20:31
• Do you already know that $Ax+By=F$ has a solution if and only if $\gcd(A,B)\mid F$? – Thomas Andrews Nov 21 '14 at 20:31
• Computers are not going to help you understand this, I think. $81x+57y+9z=3(27x+19y+3z)$, so if $D$ is not divisible by $3$... – Thomas Andrews Nov 21 '14 at 21:05

$$ax + by = \gcd(a,b)$$

has a solution $(x_0,y_0)$

so write:

$$ax_0 + by_0 = \gcd(a,b)$$

Then,

$$\gcd(a,b)w + cz = \gcd(\gcd(a,b),c)$$

has a solution $(w_0,z_0)$:

$$\gcd(a,b)w_0 + cz_0 = \gcd(\gcd(a,b),c)$$

Substituting for $\gcd(a,b)$ and some algebra, simplifying:

$$a(x_0w_0) + b(y_0w_0) + c(z_0) = \gcd(a,b,c)$$

so the original equation:

$$ax + by + cz = \gcd(a,b,c)$$

has a solution

$$x = x_0 w_0, y = y_0w_0,z = z_0$$

If you want all solutions, use $x = x_0 + \frac {b}{\gcd(a,b)}t$, etc

Because of this, the same theorems apply for three variable as for two, regarding linear equations with no solutions.