How to find integer solutions to $M^2=5N^2+2N+1$?

My number theory is terrible so I don't know what "class" of problem this secretly is. I'm looking for all positive integer solutions to the equation:

$M^2=5N^2+2N+1$

That is, I want positive integer $M$ and $N$ to make the above true. I've got the obvious solution ($N=0$, $M=1$) but I don't know how to go about getting more solutions. It has been suggested to me that there should be infinitely many solutions, and I would like to find them all.

I could transform it to look like Pell's equation by completing the square on the right, but it won't have integer coefficients (or you could multiply it through by the denominators, but then it wouldn't look like Pell's equation), so I don't think that helps much.

I don't know enough number theory to guess at other things, but I'm happy to read something on this topic.

Solution 1:

One possibility is to rewrite as $$M^2=(2N)^2+(N+1)^2. $$ So you are looking at the Pythagorean triples of the form $(N+1,2N,M) $.

Edit: Along the lines of Erick's complaint, I want to make this into a full answer, so let's talk about Pythagorean triples and how this turns into an acceptably fast algorithm.

A primitive Pythagorean triple is a triple $(r^2-s^2, 2rs, r^2+s^2)$ where $r$ and $s$ are coprime positive integers, not both odd, and $r>s$. It turns out that every Pythagorean triple -- a triple of positive integers $(a,b,c)$ where $a^2+b^2=c^2$ -- is a positive integer multiple of a primitive Pythagorean triple.

If $(N+1, 2N, M)$ is a Pythagorean triple, then there are positive integers $r$, $s$, and $k$ as above where $N+1=k(r^2-s^2)$ and $2N=2krs$. Since $2N=2((N+1)-1)$, this means $2krs=2(k(r^2-s^2)-1)$, so $krs=kr^2-ks^2-1$, so $k(rs-r^2+s^2)=-1$. Since $k$ is a positive integer, this means $k=1$, so that's one degree removed.

So we're looking at positive integers $r$ and $s$ where $rs-r^2+s^2=-1$, or rearranged, $s^2+rs-r^2+1=0$. So it must be that $s=\frac{1}{2}\left(-r+\sqrt{r^2+4(r^2-1)}\right)=\frac{1}{2}\left(-r+\sqrt{5r^2-4}\right)$.

Note that it's $+$, not $\pm$, in the above, since $s$ needs to be positive. Thus, given $r$, we can find $s$.

So the algorithm is now this. For each positive integer $r$, find $s$ in the above. If it's a positive integer, then $N=rs$, and you've found a solution $N$. Every $N$ is of this form, so this enumerates all of them, in order.

Additionally, if some number $N$ is a solution, this algorithm will find it in $O(\sqrt{N})$ time.

It can be sped up by enumerating solutions to the Pell-like equation $5r^2-4=t^2$ (that is, finding $r$ which make $s$ rational), which can be done very quickly through a recurrence (I believe) but I don't actually know how to do it. If you can do that, about half of those $r$ should make $s$ an integer, as opposed to merely rational, and you've got a really fast algorithm.

Solution 2:

For these equations we use the standard approach. For a private quadratic form: $$Y^2=aX^2+bX+1$$

Using solutions of Pell's equation: $$p^2-as^2=1$$

Solutions can be expressed through them is quite simple.

$$Y=p^2+bps+as^2$$

$$X=2ps+bs^2$$

$p,s$ - these numbers can have any sign.

Finding solutions of equations Pell - standard procedure.

Solution 3:

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

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

the sum of two squares equaling a square is a Pythagorean type equation

so parametrize as follows:

$p^2 - q^2=n+1 \tag{1}$

$2pq=2n \tag{2}$

and

$p^2 + q^2 = y^2 \tag{3}$

thus $n = pq$ and $y=\sqrt{p^2+q^2}$

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

$$pq + 1 = p^2 - q^2$$

$$1 = p^2 - pq -q^2$$

completing the square of the first and second terms:

$$1 = (p-q/2)^2 - q^2/4 - q^2$$

$$1 = (p-q/2)^2 - (5/4)q^2$$

$$4 = (2p - q)^2 - 5q^2$$

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 by the way 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:

$\underline{(r,q)\to(n,y^2)}$

$(3,1)\to(2,5)$

$(7,3)\to(15,34)$

$(18,8)\to(104,233)$

and so on...