# How to generate another solution $\in \mathbb N$ of $x^2=2y^2+7$ knowing one.

This is from a new book I started reading; it asks whether I can construct another solution for $$x^2=2y^2+7$$, given that $$(x_0,y_0)$$ is one. It gives the following diagram as a hint:

However, this diagram only "tells me" that there are no integer solutions ($$\neq 0$$) for $$x^2=2y^2$$, and I really don't see how I can use that information. I wrote a little program to find the solutions up to 1000:

x | 3  5  13  27  75  157  437  915
y | 1  3   9  19  53  111  309  647


but cannot work out any patterns (except for all the numbers being odd). Any further hints would be appreciated.

EDIT: The table above is supposedly superfluous. I am really curious as to how the diagram constitutes a hint.

Here's the German excerpt:

IV . Die Basis eines gleichschenkeligen rechtwinkligen Dreiecks sei $$x$$ und die Schenkellänge sei $$y$$.

a) [...]

b) Entwickle aus der Zeichnung ein Verfahren, aus einer Lösung $$(x,y)$$ der Gleichung $$x^2-2y^2=7$$ eine weitere zu erhalten.

c) [...]

What might be relevant, is that in one of the previous examples it was shown, that if $$(x_0,y_0)$$ a soltion to $$x^2+xy-y^2=1$$, others can be obtained with $$(y,x+y)$$ and $$(y-x,x)$$, and that the same equation with a $$0$$ instead of a $$1$$ has no solutions.

• Look for Pell Equation. Called that because the equation was studied almost a thousand years before Pell, by Brahmagupta and others. And, as far as is known, never studied by Pell. Let $(a,b)$ be a solution. Then $(u,v)$ will be a solution, where $u+v\sqrt{2}=(a+b\sqrt{2})(3+2\sqrt{2})^n$. From this you can get a recurrence. Oct 10, 2015 at 0:17
• @AndréNicolas That is very interesting, thank you! Can you think of a way to connect it to the diagram? This should be simpler judging from the surrounding tasks. Oct 10, 2015 at 0:23
• It reminds me of the geometric argument for generating solutions of $x^2-2y^2=1$ that I remember seeing, and indeed using before in a lecture. (It comes up in making rational approximations of $\sqrt{2}$.) Am at this time too lazy to reconstruct. Oct 10, 2015 at 0:29
• I dk how the diagram is supposed to help. But 2 good answers so far.. Oct 10, 2015 at 0:29
• @AndréNicolas Well, that's at least closer to $x^2-2y^2=0$ ^^ Oct 10, 2015 at 0:31

Suppose you have a solution $(x_0, y_0)$ for $x^2 = 2y^2 + 7$. Now suppose you have another solution $(a_0, b_0)$ for $a^2 = 2b^2 + 1$. Then because \begin{align*} 7 = (7)(1) &= (x^2-2y^2)(a^2-2b^2) \\ &= (ax)^2 - 2(bx)^2 - 2(ay)^2 + 4(by)^2 \\ &= (ax)^2 + 4(ax)(by) + 4(by)^2 - 2(bx)^2 - 2(ay)^2 - 4(bx)(ay) \\ &= (ax+2by)^2 - 2(ay+bx)^2, \end{align*} we see that $$(x_1, y_1) = (a_0 x_0 + 2b_0 y_0, a_0 y_0 + b_0 x_0)$$ is also a solution to $x^2 = 2y^2 + 7$. Now since $(a_0, b_0) = (3,2)$ is a fairly easy solution of the second identity, we get $$(x_1, y_1) = (3x_0 + 4y_0, 2x_0 + 3y_0)$$ is a solution if $(x_0, y_0)$ is a solution.

What is curious about this result is that it actually also finds additional solutions to the auxiliary equation $a^2 = 2b^2 + 1$, since our derivation did not rely on the fact that we had a $7$. If that $7$ had been $1$, it still would have held, meaning that we could generate other solutions to $a^2 = 2b^2 + 1$ using the same recursion formula. Indeed, we find $(a_1, b_1) = (17, 12)$ also works.

Furthermore, we can also see how to generalize the above for equations of the form $$x^2 = Dy^2 + N,$$ for square-free $D$ and positive integers $N$. I leave it as an exercise for the reader to determine if such a method can be used to generate all integer solutions.

given a solution $(x,y)$ of $$x^2 - 2 y^2 = k,$$ you get a new solution with $$(3x+4y, 2x+3y)$$

The matrix $$\left( \begin{array}{rr} 3 & 4 \\ 2 & 3 \end{array} \right)$$ and its inverse generate the (oriented) automorphism group of the quadratic form $x^2 - 2 y^2$

It should be noted that you must use two seed solutions to get your entire list, $(3,1)$ and $(3,-1).$ The two infinite sequences of pairs are interlaced in your list

By Cayley-Hamilton, we get a one-variable recurrence, however it applies to every other number; $$x_{2n+4} = 6 x_{2n+2} - x_{2n}$$ $$x_{2n+5} = 6 x_{2n+3} - x_{2n +1}$$ $$y_{2n+4} = 6 y_{2n+2} - y_{2n}$$ $$y_{2n+5} = 6 y_{2n+3} - y_{2n +1}$$ For example, $6 \cdot 13 - 3 = 75,$ $6 \cdot 75 - 13 = 437.$

• Is there a method to derive this? More specifically, to tie it to the diagram? Oct 10, 2015 at 0:17
• @Grantwalzer, several methods. What book are you talking about? Oct 10, 2015 at 1:10
• I mean, how is the diagram a hint? It's a German book, "Zahlentheorie für Einsteiger" by A. Bartholomé, J. Rung and H. Kern. Oct 10, 2015 at 1:32
• @Grantwalzer Found a preview online, more than half the pages, but the index is not shown. What page? Oct 10, 2015 at 1:47
• @Grantwalzer, so far it won't let me see that, although some other preview might eventually do so. It would help if you posted that page as an image in your question; definitely include the writing and symbols, not just that diagram. I know enough German to read a page of mathematics, also there are plenty of fluent German speakers on the site. Oct 10, 2015 at 1:57