5
$\begingroup$

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.

  • 0
    http://math.stackexchange.com/questions/1776734/how-to-find-integer-solutions-to-m2-5n22n1/1776757#17767572016-06-26

3 Answers 3

6

Write the equation as $ (2n)^2 + (n+1)^2 = y^2,$ and then apply the [well-known] parameterization for Pythagorean triples.

5

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.

  • 1
    @Mike this post describes how to format mathematics on this site: http://meta.math.stackexchange.com/questions/107/faq-for-math-stackexchange/117#1172013-03-25
1

As it says above, you may manipulate the original problem into:

$(n+1)^2 + (2n)^2 = (y)^2.$

The sum of two squares equalling a square is a Pythagorean type equation, so parametrize as follows:

\begin{align} p^2 - q^2&=n+1 \tag{1} \\ 2pq&=2n \tag{2} \\ p^2 + q^2 &= y^2 \tag{3} \end{align}

Put this $n$ back into (1), we have

$pq + 1 = p^2 - q^2 \implies 1 = p^2 - pq -q^2.$

Completing the square of the first and second terms:

\begin{align} 1 = (p-q/2)^2 - q^2/4 - q^2 \\ &\implies 1 = (p-q/2)^2 - (5/4)q^2 \\ &\implies 4 = (2p - q)^2 - 5q^2 \end{align}

Let $r = 2p - q$, this implies that $p=\frac{r+q}{2}$, thus $n=pq=\frac{(r+q)q}{2}$, thus $y=\sqrt{\left(\frac{r+q}{2}\right)^2 + q^2}$. The equation above is now $r^2 - 5q^2 = 4$ which is a Pell type equation

It's fair I think to represent the solution of the problem in terms of the solutions of a Pell type equation, which are infinite in number:

In this way, the solution set is $(n,y) = \left(\frac{(r+q)q}{2}, \sqrt{\left(\frac{r+q}{2}\right)^2 + q^2}\right)$ such that $(r,q)$ belongs in the solution set of $r^2 - 5q^2 = 4$. Here are some examples:

\begin{array}{rcl} (r,q) &\to& (n,y^2) \\\hline (3,1) &\to& (2,5) \\ (7,3) &\to& (15,34) \\ (18,8)&\to& (104,233) \\ \end{array} and so on...

  • 1
    Thank you for pointing me in this direction. I used this knowledge.2017-07-11