<s>[INST] Solve in $\mathbf{N}$ the equation $9x^2+p=y^2$ In these days, I have been trying to solve this problem:

Let $p \in \mathbf{N}$ a positive large integer ($> 10^9$). Find all $x, y \in\mathbf{N}$ such that:
$$9x^2+p=y^2$$

The first approach that I have tried is the following. We know that:
$$(t+n)^2-t^2=t^2+2\cdot t \cdot n +n^2-t^2=2\cdot t \cdot n +n^2$$
Also, we can build every possible square $w_n$ greater than $p$ in this way:
$$w_n=\left\lfloor\sqrt{p}\right\rfloor^2+2\cdot \left\lfloor\sqrt{p}\right\rfloor \cdot n +n^2 = \left(n+\left\lfloor\sqrt{p}\right\rfloor^2\right)^2$$
For example, let $p=5$. Follows that: $w_1=\left(1+\left\lfloor\sqrt{5}\right\rfloor^2\right)^2=9$, $w_2=\left(2+\left\lfloor\sqrt{5}\right\rfloor^2\right)^2=16$ and so on.
Now, using this idea and applying to the first equation:
$$9x^2=\left(n+\left\lfloor\sqrt{p}\right\rfloor^2\right)^2-p$$
I am not allowed to apply Pell's equation because $9=3^2$ and calcultaing $\Delta$ in $x$ doesn't help anymore.
Another approach is based on Pell's equation. I thought to express $9x^2=8x^2+x^2$ and then:
$$8x^2+x^2+p=y^2\leftrightarrow 8x^2+p=y^2-x^2\leftrightarrow (y^2-x^2)-8x^2=p \leftrightarrow u^2-8x^2=p$$
But then, in order to generate all the solutions, I have to guess the first one (or one of them) that is pretty complicated for big $p$.
So, how can we do that? Are there any other solutions?
Thanks.
 [/INST] First, reformulate the problem as the following:
$$
y^2 - 9x^2 = p \Rightarrow(y-3x)(y+3x)= p
$$
Now, for any given $p$, find its prime factors. Then, for any 2-partitions of them, solve a simple equation system.
To simplify some cases, suppose $p$ is factorized to $p_1 \times p_2$. Now, solve the following system:
$$
y-3x = p_1
$$
$$
y+3x = p_2
$$
So, $y = \frac{p_1 + p_2}{2}$, and $x = \frac{p_2 - p_1}{6}$. It gives us a heuristic to find potential answers more quickly.  $p_2$ is in the form of $6k + p_1$.
</s>