# Solving quadratic diophantine equations

I hope it's not inappropriate asking this here. I stumbled upon this site recently while researching a Project Euler problem, now I figure I'd use it to ask about a recurring theme in these problems: quadratic Diophantine equations.

I've recently boiled down another Project Euler problem (I won't say which, it should be unrecognizable from the original problem and should probably be kept that way) to the following Diophantine equation:

$$5n^2+2n+1=y^2$$

I've been trying to use http://www.alpertron.com.ar/METHODS.HTM as a reference, but I seem to get lost in a sea of constants. And the steps that program on the bottom of that page takes don't seem to match what he says to do. I'd rather be able to understand the steps I'm taking anyway rather than just copying a method.

I'm interested in all positive integer values of n and I'm more or less given a solution exists with n=2. How would I go about finding the rest of the solutions? And how would I solve these kinds of equations in general? If that last part is too complex a question to be handled here, is there any other resource that might help? As far as my current level of math, I have a degree in engineering (and helped a math major with some courses I never took myself) and I've already worked on Project Euler problems involving Pell's equations and continued fraction expansions of square roots.

-

## 1 Answer

Start by completing the square on the left: $$5\big( n+\tfrac15)^2 + \tfrac45 = y^2$$ Multiply by 5 to clear denominators: $$(5n+1)^2 + 4 = 5y^2.$$ Therefore you're looking for solutions to the Pell equation $$x^2 - 5y^2 = -4$$ that happen to satisfy $x\equiv1\pmod5$ (so that $n=(x-1)/5$).

Given that you know how to solve Pell's equation, you should be able to find a way to generate all integer solutions $(x_k,y_k)$; some of these values $x_k$ will be $1\pmod 5$, and the set of such $k$ should be an arithmetic progression.

-
I guess I should be more specific. I've had problems dealing with Pell's equations of the form x^2-ny^2=1. I've had to calculate solutions for such equations by checking the convergents of the square root of n. I've had other equations where I've had to do similar substitutions as the above, though I wasn't aware about the arithmetic progression thing and checked each answer to make sure it was still an integer after resubstition. I do not know why the convergents work and assume the answer would be complex. I also don't know how to generalize to solve x^2-ny^2=k. – Mike Oct 23 '11 at 10:29

1
There's one obvious solution $(a,b)$ to $x^2-5y^2=-4$. Prove that if $(x,y)$ is any solution then $(u,v)$ is another given by $(u+v\sqrt5)/2=((3+\sqrt5)/2)(x+y\sqrt5)/2$. It follows that $((3+\sqrt5)/2)^r(a+b\sqrt5)/2$ gives solutions for all $r$. If you choose $r$ cleverly, you'll even get $x\equiv1\pmod5$. If that's not enough, the libraries are full of intro number theory texts that discuss quadratic diophantine equations. – Gerry Myerson Oct 23 '11 at 11:47
How do you do mathematical notation here like exponents and radicals? Ah well, I was able to prove that statement. First I went to prove that if a+bz=c+dz, where a,b,c, and d are rational and z is irrational, then a=c and b=d. I rewrite the equation as a-c=(d-b)z. The left side is rational. The right size is rational if and only if d-b=0. So that step is proven. I cleared the parentheses in your equation to yield u=(3x+5y)/2 and v=(x+3y)/2. I then wrote u+v(root 5) in terms of x and y, then multiplied by the original equation you gave and simplified, giving u^2-5v^2=x^2-5y^2 – Mike Oct 23 '11 at 23:13
I guess I'll need to check the libraries for that and maybe something on game theory. In any case, I used u as x(n+1) and checked to see if that equation with (x0,y0)=(1,1) would generate all the solutions I needed. It appears the answers I needed were given for even values of r, so I redid the recurrences to take that into account. I was given what the 10th value should be for the problem, which matched the 10th iteration. So while I don't know how you arrived at that formula, it did generate all solutions I needed. Another problem solved. Thanks. – Mike Oct 24 '11 at 2:36
If you have $x^2 - 5^2 = -4$, then $(x / 2)^2 - 5 (y / 2)^2 = -1$. That I recognize as Pell's equation. – vonbrand Mar 25 at 1:15
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9632857441902161, "perplexity_flag": "head"}