I would like to find solutions in positive integers for diophantine equations having no variable squared. (And having some other limitations, but I will not consider them now.) Take, for example, $abcd-3bcd+2abc+ad-3=0$.

It is known that $xy+xz+yz=C$ has positive solutions except for few special values of $C$ and proof of this is quite complicated. So, this is hard question in general. But sometimes an answer might be easy to find or to prove that there is no solutions.

For our example, we see that $abcd > -3bcd+2abc+ad+3$ at least when $a,b,c,d > |2+1+3|=6$ -- i.e. $abcd$ "dominates" value. So we have at most $6^4$ new equations, just let every variable have values from 1 to 6. And for example when $b=2$ we have $2acd-6cd+4ac+ad-3=0$. Now $2acd$ dominates, and we can take recursive approach. Of course we should check that GCD of coefficients divides constant.

In C++ one can have recursive template. Then compiler might be able to optimize code, because every level of recursion would be own function with at least some values for loops being constants. And if we might have overflow, we can first look for solutions mod $2^{32}$ with normal unsigned ints, and only for those possible solutions check if they are real solutions with some arbitrary length interger library.

EDIT: Example happened to be "too easy". Here is another one: $abcd-35bcd-7acd-5abd-3abc+1$. Now I can't see how to factor parts like suggested on first answer.

But is there better approach? Or ready code for this?


1 Answer 1


If you call $e$ the product $bc$, the equation is written as $ade+2ae+ad=3+3de$.

Now study the following cases:

(1). $3\mid{a}$; in this case the equation has no solution.

[Let $a=3k$, hence $k(de+2e+d)=de+1$. But we always have $k(de+2e+d)>de+1$ as $k,e,g\geq1$.]

(2). $a=1$; in this case the equation has no solution.

[In this case $2e+d=2de+3$. Therefore $2de-2e-d+3=0$, hence $2(de-e-d+1)+d+1=0$ and $2(d-1)(e-1)+d+1=0$, impossible.]

(3). $a=2$. There are only two solutions.

[In this case $2(de+2e+d)=3(de+1)$, hence $4e+2d=de+3$. Therefore $d,e$ are odd. Let $d=2x+1$ and $e=2y+1$, $x,y\geq0$, then $3y+x+1=2xy$. Since $y(2x-3)=x+1$, then $2x-3\mid{x+1}$. In particular $2x-3\leq{x+1}$, and $x\leq4$. The solutions are $(x,y)=(4,1),(2,3)$, hence $(d,e)=(9,3),(5,7)$.]

(4). $3\not\mid{a}$ and $a>2$; in this case the equation has no solution.

[In this case $a(de+2e+d)=3(de+1)$, hence $3\mid{de+2e+d}$. And $3\mid{d}$ if, and only if, $3\mid{e}$. If $d,e\not\equiv{0}\pmod{3}$, then the only possibility is $d\equiv{2}\pmod{3}$ and $e\equiv{1}\pmod{3}$.

(4.1). If $d,e\equiv{0}\pmod{3}$, let $d=3x$, $e=3y$, hence $a(de+2e+d)=3(de+1)$; $a(3^2xy+2\times3y+3x)=3(3^2xy+1)$ and $a(3xy+2y+x)=3^2xy+1$, which impossible as $a>3$, $x,y\geq1$.

(4.2). If $d,e\not\equiv{0}\pmod{3}$, let $d\equiv{2}\pmod{3}$ and $e\equiv{1}\pmod{3}$. Let $d=3x+2$, $e=3y+1$, hence $a(de+2e+d)=3(de+1)$; $a((3x+2)(3y+1)+2(3y+1)+3x+2)=3((3x+2)(3y+1)+1)$ and $a(3xy+4y+2x+2)=3(3xy+2y+x+1)$; which is impossible as $a>3$, $x,y\geq1$.]

Therefore the positive integer solutions to the original equation are: $(a,b,c,d)=(2,3,1,9),(2,1,3,9),(2,1,7,5)$ and $(2,7,1,5)$.

  • $\begingroup$ In this answer $ae$ should be $2ae$. But idea is good. So I should always test if I can split equation to left and right side so that at least on side could be factorized. I must think about how to do this in general. $\endgroup$ Oct 31, 2013 at 14:38
  • $\begingroup$ I made another example where I can't use your approach. $\endgroup$ Nov 4, 2013 at 9:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .