4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Multiply by $5$, we get a Pell equarion. $\endgroup$ – André Nicolas May 8 '16 at 13:43
  • $\begingroup$ You missed $N=-1$ and $N=2$ $\endgroup$ – Empy2 May 8 '16 at 14:29
  • $\begingroup$ @Michael, well, I think I missed infinitely many solutions, but yes, those are not too tough. $\endgroup$ – Richard Rast May 8 '16 at 14:34
  • $\begingroup$ @Andre Doesn't a Pell equation need to be in the form $x^2-Dy^2=1$? I don't see how to multiply by 5 and get that. $\endgroup$ – Richard Rast May 8 '16 at 14:34
  • $\begingroup$ @RichardRast Strictly speaking you are correct, however more generally any Diophantine equation of the form $x^2 - Dy^2 = k$ with $k \ne 0$ is often called a Pellian equation. The important thing is that the same principle still applies to the general case: if you have one solution, then you can always find infinitely many more. $\endgroup$ – Erick Wong May 8 '16 at 18:01
9
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I like this answer, but it seems less general than the other one (which I don't yet understand). In general it seems like I would not be able to put equations in this form, right? If I just had $aN^2+bN+c$? $\endgroup$ – Richard Rast May 8 '16 at 14:20
  • $\begingroup$ Absolutely. This is an answer from someone like me who doesn't know any number theory. $\endgroup$ – Martin Argerami May 8 '16 at 16:07
  • $\begingroup$ Well, since the other answers don't give a concrete (efficient) way to get all solutions, I'll go with this, even though I'm not sure I'll be able to use the technique on other problems. Thanks! $\endgroup$ – Richard Rast May 8 '16 at 22:56
  • $\begingroup$ @RichardRast 1) I don't see how this answer efficiently gives all solutions, 2) Your original question never asks to find all solutions, only infinitely many, 3) Will Jagy's answer did give all solutions efficiently, it just requires substantial background knowledge to follow. $\endgroup$ – Erick Wong May 10 '16 at 8:22
  • $\begingroup$ @ErickWong 1) There are nice ways to enumerate all pythagorean triples, which are well-known, although the answer doesn't state them. 2) That's a flaw in my phrasing, but it was always the intent of the question. 3) I was happy with Will Jagy's answer, and would have been happy to accept it after I asked a few questions, but he deleted it and I do not know why. There is no private messaging on StackExchange so I was unable to ask him. $\endgroup$ – Richard Rast May 10 '16 at 11:32
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Is this guaranteed to give every possible solution? And does this work for every integer $a$ and $b$ (assuming $a\not=0$)? $\endgroup$ – Richard Rast May 8 '16 at 14:25
  • $\begingroup$ Generally speaking, you can write down several formulas. But I think that's enough. The main thing that shows. Infinitely many solutions when the number $a$ is not a square. $\endgroup$ – individ May 8 '16 at 14:42
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If you numerate your solutions, it seems, that on the lhs, $q_{k}=3q_{k-1}-q_{k-2}$ and equivalently with $r$. Is that true? $\endgroup$ – Gottfried Helms Jul 15 '17 at 8:50
  • $\begingroup$ @GottfriedHelms I see what you're saying. I'm trying to work out why. I know that $(\sqrt{5}-2)(\sqrt{5}+2)=1$ but still the smallest second order recursion I can come up with is $q_{k+2}−18q_{k+1}+q_{k}=0$. Perhaps you can help me $\endgroup$ – AmateurMathPirate Jul 15 '17 at 20:12
  • $\begingroup$ Hmm, the recursion for $\{2,15,104,714,4895,...\}$ is $n_k=8n_{k-1}-8n_{k-2}+n_{k-3}$ and that for $y = \{5, 34, 233, 1597, 10946,...$ is $y_k=7y_{k-1}-y_{k-2}$ (The higher values for $(n,y)$ were found using brute-force in Pari/GP) Don't yet see how this helps for $(r,q)$ though... $\endgroup$ – Gottfried Helms Jul 15 '17 at 20:19
  • $\begingroup$ @GottfriedHelms what I know is the following: $$ax^2-by^2=a\left((1+2bq^2)x+(2bpq)y\right)^2-b\left((2apq)x+(1+2bq^2)y\right)^2=c$$ iff $$ap^2-bq^2=1$$ or$$ap^2-bq^2=-1$$. There must be some quadratic surd that I haven't come across yet that could solve this problem. $\endgroup$ – AmateurMathPirate Jul 15 '17 at 20:30
  • 1
    $\begingroup$ that looks very good; thanks for the effort to explain this to me! $\endgroup$ – Gottfried Helms Jul 18 '17 at 5:33
1
$\begingroup$

A quick way to find some solutions is the following:
You probably know you can get the square numbers by calculating $1+3+5+7+9+...$
In the same way, you can get the numbers $5N^2+2N+1$ by calculating $$1+7+17+27+37+47+57...$$ So, one add per number, which you can do with pencil and paper.
You might need a calculator to check which numbers are squares.
You can also get values for negative $N$ with $1+3+13+23+33+43+53+...$

|cite|improve this answer
$\endgroup$

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.