Integer solutions to $\sqrt{ax^2+1}$ and the unusually large solutions

Question

While trying to simplify some triangle graphing I came across this equation $\sqrt{ax^2+1}$ looking for integer solutions. Trivially $x=0$ is true for any $a$. However the non-trivial solutions have a nice recurrent relation.

For example, $\sqrt{5x^2+1}$ has the solutions $x=\{0,4,72,1292,23184\cdots\}$ defined by the recurrent relation $x_n = 19x_{n-1}-x_{n-2}$ with $x_0=0$ and $x_1=4$

In my triangle search I was at first looking for solutions to $\sqrt{(1+b^2)x^2+1}$.

This actually had a nice recurrent relation. $x= \{0,2b,(4b^2+2)a_{n-1}-a_{n-2}\}$

That problem I have is what gives you the first nontrivial $x$ for a given $a$. When $a$ is of the form $b^2+1$ the relation is pretty nice. But consider the solutions to $\sqrt{41x^2+1}$. The solution set is $x=\{0,320,1311360,5373952960\}$. Intuition had me consider large solutions when $a$ is prime but $a=47$ gives $x=\{0,7,672,64505\}$, but my python script can't find any solutions to $\sqrt{61x^2+1}$ under $10^7$

I suppose my question would be how to solve for the first two nontrivial solutions for any $a$ or any other insights or info on this equation.

Answer 1

The following procedure finds all integer solutions of $$ax^2+1=y^2$$ It works for any integer $a$ but I will use $a=41$ to illustrate it. Notice that if we divide by $x^2$ we get $\sqrt{a}\approx(y/x)$.

Calculate the continued fraction of $\sqrt{41}$ as $$\sqrt{41}=6+\frac{1}{2+\frac{1}{2+\frac{1}{12+\cdots}}}$$ This is just a sequence of fractions: $6$, $\frac{13}{2}$, $\frac{32}{5}$, $\frac{397}{62}$, $\ldots$ One of them will have numerator and denominator that solve the equation $41x^2+1=y^2$. (This is guaranteed from the theory of Pell equations). For $a=41$, the first one is the sixth fraction $2049/320$. As you point out, $x=320$, $y=2049$ is the smallest non-trivial solution.

For $a=61$ (which incidentally was proposed as a challenge by the Indian mathematician Bhaskara in the 12th century), the first fraction is the 22nd one $1766319049/226153980$ with integers of order $10^9$.

Once you find the smallest solution, you can obtain all other solutions by multiplying out $(y+x\sqrt{a})^n$ and simplifying. So, for $a=41$, the next solution is found from $$(2049+320\sqrt{41})^2=8396801 + 1311360\sqrt{41}$$ to be $x=1311360$, as your algorithm found out.

Answer 2

Let me add that Prof. Lubin wrote out the continued fraction method using only integer operations, suitable for a python program, for example. I wrote it in C++ with GMP. Oh, you might like the book Pell's Equation by Barbeau.

Let me put in 19 first:

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 19} = 4 + \frac{ \sqrt {19} - 4 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {19} - 4 } = \frac{ \sqrt {19} + 4 }{3 } = 2 + \frac{ \sqrt {19} - 2 }{3 } $$ $$ \frac{ 3 }{ \sqrt {19} - 2 } = \frac{ \sqrt {19} + 2 }{5 } = 1 + \frac{ \sqrt {19} - 3 }{5 } $$ $$ \frac{ 5 }{ \sqrt {19} - 3 } = \frac{ \sqrt {19} + 3 }{2 } = 3 + \frac{ \sqrt {19} - 3 }{2 } $$ $$ \frac{ 2 }{ \sqrt {19} - 3 } = \frac{ \sqrt {19} + 3 }{5 } = 1 + \frac{ \sqrt {19} - 2 }{5 } $$ $$ \frac{ 5 }{ \sqrt {19} - 2 } = \frac{ \sqrt {19} + 2 }{3 } = 2 + \frac{ \sqrt {19} - 4 }{3 } $$ $$ \frac{ 3 }{ \sqrt {19} - 4 } = \frac{ \sqrt {19} + 4 }{1 } = 8 + \frac{ \sqrt {19} - 4 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccc} & & 4 & & 2 & & 1 & & 3 & & 1 & & 2 & & 8 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 4 }{ 1 } & & \frac{ 9 }{ 2 } & & \frac{ 13 }{ 3 } & & \frac{ 48 }{ 11 } & & \frac{ 61 }{ 14 } & & \frac{ 170 }{ 39 } \\ \\ & 1 & & -3 & & 5 & & -2 & & 5 & & -3 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 19 \cdot 0^2 = 1 & \mbox{digit} & 4 \\ \frac{ 4 }{ 1 } & 4^2 - 19 \cdot 1^2 = -3 & \mbox{digit} & 2 \\ \frac{ 9 }{ 2 } & 9^2 - 19 \cdot 2^2 = 5 & \mbox{digit} & 1 \\ \frac{ 13 }{ 3 } & 13^2 - 19 \cdot 3^2 = -2 & \mbox{digit} & 3 \\ \frac{ 48 }{ 11 } & 48^2 - 19 \cdot 11^2 = 5 & \mbox{digit} & 1 \\ \frac{ 61 }{ 14 } & 61^2 - 19 \cdot 14^2 = -3 & \mbox{digit} & 2 \\ \frac{ 170 }{ 39 } & 170^2 - 19 \cdot 39^2 = 1 & \mbox{digit} & 8 \\ \end{array} $$

=======================================================

Here is 41, notice how it hits $-1$ first, so it does the loop twice to reach $+1$

$$ \sqrt { 41} = 6 + \frac{ \sqrt {41} - 6 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {41} - 6 } = \frac{ \sqrt {41} + 6 }{5 } = 2 + \frac{ \sqrt {41} - 4 }{5 } $$ $$ \frac{ 5 }{ \sqrt {41} - 4 } = \frac{ \sqrt {41} + 4 }{5 } = 2 + \frac{ \sqrt {41} - 6 }{5 } $$ $$ \frac{ 5 }{ \sqrt {41} - 6 } = \frac{ \sqrt {41} + 6 }{1 } = 12 + \frac{ \sqrt {41} - 6 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccc} & & 6 & & 2 & & 2 & & 12 & & 2 & & 2 & & 12 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 6 }{ 1 } & & \frac{ 13 }{ 2 } & & \frac{ 32 }{ 5 } & & \frac{ 397 }{ 62 } & & \frac{ 826 }{ 129 } & & \frac{ 2049 }{ 320 } \\ \\ & 1 & & -5 & & 5 & & -1 & & 5 & & -5 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 41 \cdot 0^2 = 1 & \mbox{digit} & 6 \\ \frac{ 6 }{ 1 } & 6^2 - 41 \cdot 1^2 = -5 & \mbox{digit} & 2 \\ \frac{ 13 }{ 2 } & 13^2 - 41 \cdot 2^2 = 5 & \mbox{digit} & 2 \\ \frac{ 32 }{ 5 } & 32^2 - 41 \cdot 5^2 = -1 & \mbox{digit} & 12 \\ \frac{ 397 }{ 62 } & 397^2 - 41 \cdot 62^2 = 5 & \mbox{digit} & 2 \\ \frac{ 826 }{ 129 } & 826^2 - 41 \cdot 129^2 = -5 & \mbox{digit} & 2 \\ \frac{ 2049 }{ 320 } & 2049^2 - 41 \cdot 320^2 = 1 & \mbox{digit} & 12 \\ \end{array} $$

As an alternative, if you have found $u^2 - n v^2 = -1,$ then you may duplicate, and the first occurrence of $-1$ does give the first $+1$: $$ \left( u^2 + n v^2 \right)^2 - n \left( 2 u v \right)^2 = 1 $$

Meanwhile, if, by whatever method, you have found the first ($t \neq 0$) $s^2 - n t^2 = 1,$ then the second comes from $$ \left( s^2 + n t^2 \right)^2 - n \left( 2 s t \right)^2 = 1 $$