Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

share|improve this answer
    
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. –  Jori Mäntysalo Oct 31 '13 at 14:38
    
I made another example where I can't use your approach. –  Jori Mäntysalo Nov 4 '13 at 9:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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