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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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$. $\endgroup$ – Arthur Nov 21 '14 at 20:28
  • $\begingroup$ This is the Euclidean Algorithm, I think. $\endgroup$ – Joe Z. Nov 21 '14 at 20:28
  • $\begingroup$ 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? $\endgroup$ – MackTuesday Nov 21 '14 at 20:31
  • 1
    $\begingroup$ Do you already know that $Ax+By=F$ has a solution if and only if $\gcd(A,B)\mid F$? $\endgroup$ – Thomas Andrews Nov 21 '14 at 20:31
  • 2
    $\begingroup$ 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$... $\endgroup$ – 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)$$


$$\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.


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