1
$\begingroup$

I have the quadratic Diophantine equation: $$2x^2-y^2-y=0$$ $$x < y$$ and I'm writing a computer program which requires finding all positive integer solutions to this equation for $y\leq b$, where $b$ is a bound which could potentially be very large.

So far, the only way I seem to be able to solve this is by iterating over all $y\leq b$, solving for x and checking the result, which can be very slow.

Is there a more efficient way to do this? I've read that quadratic Diophantine equations can be represented as two Pell like equations which can be solved more easily but I have not been able to find a clear explanation of this.

Improve this question
$\endgroup$
  • $\begingroup$ Do you want to solve for $x$ or $y$?. It makes a difference in the solution. $\endgroup$ – poetasis Jul 27 '19 at 0:36
  • $\begingroup$ Thanks for the comment. I want to solve for both $x$ and $y$. $\endgroup$ – aa2bc56 Jul 27 '19 at 0:37
2
$\begingroup$

$$ 8x^2 - 4 y^2 - 4 y - 1 = -1 $$ $$ (2y+1)^2 - 8 x^2 = 1 $$ $$ w^2 - 8 x^2 = 1 \; , $$ so that $w$ really is odd, then $y = (w-1)/2$

The first two are $$ (w,x) = (1,0) $$ then $$ (w,x) = (3,1) $$

After that, growth comes from $$ (w,x) \mapsto (3w+8x, w + 3x ) $$ over and over

w:  1  x:  0  
w:  3  x:  1  
w:  17  x:  6
w:  99  x:  35
w:  577  x:  204
w:  3363  x:  1189
w:  19601  x:  6930
w:  114243  x:  40391
w:  665857  x:  235416
w:  3880899  x:  1372105
w:  22619537  x:  7997214

but still followed by $y = (w-1)/2$ for each

If preferred, there are separate recurrences

$$ w_{n+2} = 6 w_{n+1} - w_n \; , \; $$ $$ x_{n+2} = 6 x_{n+1} - x_n \; . \; $$

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you! That's exactly what I needed! $\endgroup$ – aa2bc56 Jul 27 '19 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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