Solve in $\mathbf{N}$ the equation $9x^2+p=y^2$

Question

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.

Answer 1

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

Answer 2

Well, as per your request, I'd add an answer so the comments section is clear (sorry again for the inconvenience).

Notice that you can rearrange the equation as $p = (y + 3x)(y-3x)$. The least bound for $p$ is $10^9$ as per your question, so I'd always suggest starting an exhaustive search (due to my being a rookie/ newbie at such big problems) from there so that you can get the least possible $p, x$ and $y$ that satisfies your equation. From there, tactically plan how you can manipulate the value of $x$ and $y$ and still obtain values for $p$. For example, you can add a $9a^2 \pm 6ax$ or $a^2 \pm 2ay$ (I'd suggest going for $9a^2 + 18ax$ or $a^2+ 2ay$ as long as you don't override a solution during the exhaustive search) to both sides of the equation and see the changes yourself.

If you're looking for multiple solutions for the same $p$, you can exchange things around.

Edit : OmG's answer is worth a special mention, please go check it above.

Edit: Another great contribution by Servaes; please go check below

Answer 3

Solution: Compute the remainder of $p$ modulo $36$.

1. If $p\equiv2,3,5,6,8,10,11,12,14,15,17,18,20,21,22,23,24,26,29,30,32,33,34,35\pmod{36}$, then there are no solutions.
2. If $p\equiv9,27\pmod{36}$ then for every factorization $p=9uv$ into positive integers $u$ and $v$ with $u>v$ take $$x=\frac{u-v}{2}\qquad\text{ and }\qquad y=3\frac{u+v}{2}.$$
3. If $p\equiv0\pmod{36}$ then for every factorization $p=36uv$ into positive integers $u$ and $v$ with $u>v$ take $$x=u-v\qquad\text{ and }\qquad y=3(u+v).$$
4. If $p\equiv1,7,13,19,25,31\pmod{36}$ then for every factorization $p=uv$ into positive integers $u$ and $v$ with $u>v$ take $$x=\frac{u-v}{6}\qquad\text{ and }\qquad y=\frac{u+v}{2}.$$
5. If $p\equiv4,16,28\pmod{36}$, all solutions $(x,y)$ are of the form $(2x',2y')$ where $(x',y')$ is a solution for $p'=\tfrac p4$.

Explanation:

Let $p$ be a large integer. We want to find all positive integers $x$ and $y$ such that $$9x^2+p=y^2.\tag{1}$$ First note that there are no solutions if $p\equiv2\pmod{3}$ or $p\equiv2\pmod{4}$.

If $p$ is divisible by $3$, which is easy to check given the decimal representation of $p$, then also $y$ is divisible by $3$. Then $y=3z$ for some positive integer $z$ and so $$p=y^2-9x^2=9z^2-9x^2=9(x^2-z^2),$$ which shows that $p$ must be divisible by $9$. That is to say, if $p\equiv3,6\pmod{9}$ then there are no solutions. Write $p=9q$ to see that $$q=z^2-x^2=(z+x)(z-x),\tag{2}$$ and so the integers $x$ and $y$ in $(1)$ yield a factorization of $q$ into two factors that are congruent mod $2$. This is of course impossible if $q\equiv2\pmod{4}$, which shows that there are no solutions if $p\equiv6\pmod{12}$. Otherwise, if $q$ is odd then for every factorization $q=uv$ into positive integers $u$ and $v$ with $u>v$ the pair $$z=\frac{u+v}{2}\qquad\text{ and }\qquad x=\frac{u-v}{2},$$ yields a solution to $(2)$. Similarly, if $q\equiv0\pmod{4}$ then for every factorization $q=4uv$ into positive integers $u$ and $v$ with $u>v$ the pair $$z=u+v\qquad\text{ and }\qquad x=u-v,$$ yields a solution to $(2)$. Either way we see that:

1. If $p\equiv2\pmod{3}$ or $p\equiv3,6\pmod{9}$ or $p\equiv 6\pmod{12}$, or equivalently $$p\equiv2,3,5,6,8,11,12,14,15,17,18,20,21,23,24,26,29,30,32,33,35\pmod{36},$$ then there are no solutions.
2. If $p\equiv0,9,27\pmod{36}$ then finding all solutions is equivalent to factoring $p$.

On the other hand, if $p\equiv1\pmod{3}$ and $p\not\equiv2\pmod{4}$ then $p\equiv1,4,7\pmod{12}$.

If $p\equiv4\pmod{12}$ then $p\equiv4\pmod{6}$ and from $$p=y^2-9x^2=(y+3x)(y-3x),$$ we get a factorization of $p$ into two factors that are congruent modulo $6$. It follows that $$y+3x,y-3x\equiv2\pmod{6},$$ and so both $x$ and $y$ are even, say $x=2x'$ and $y=2y'$. Then $p$ is divisible by $4$, say $p=4p'$, and we find that $$9(x')^2+p'=(y')^2,$$ where of course $p'\equiv1\pmod3$ because $p\equiv4\pmod{12}$. This shows that every solution $(x,y)$ for $p$ is of the form $(2x',2y')$ where $(x',y')$ is a solution for $p'=\tfrac p4$.

What remains are the cases $p\equiv1,7\pmod{12}$, or equivalently the case $p\equiv1\pmod{6}$. If $p\equiv1\pmod{6}$ then for every factorization $p=uv$ into positive integers $u$ and $v$ with $u>v$ we have $u\equiv v\pmod{6}$. Then setting $$y=\frac{u+v}{2}\qquad\text{ and }\qquad x=\frac{u-v}{6},$$ yields a solution to $(1)$. Conversely, every solution $(x,y)$ to $(1)$ yields a factorization $$p=(y+3x)(y-3x),$$ into distinct factors that are congruent modulo $6$. So in this case the problem is again equivalent to factoring $p$.

Answer 4

An experimental approach:

Here I find one solution for this equation which a family of solutions can be based on:

$9x^2=y^2-p=(y-\sqrt p)(y+\sqrt p)$

we can can construct following system of equations:

$\begin{cases}y-\sqrt p=9\\y+\sqrt p=x^2\end{cases}$

Subtracting first equation from second one we get:

$2\sqrt p=x^2-9=(x-3)(x+3)$

Suppose:

$x-3=2\Rightarrow x=5$

$x+3=\sqrt p$

subtracting first fro, second we get:

$\sqrt p-2=6\Rightarrow \sqrt p=8\rightarrow p=64$

Now we have:

$9x^2=y^2-64=(y-8)(y+8)$

Let $y-8=9\rightarrow y=17$

$x^2=y+8=25$

hence :

$x=5$, $y=17$ and $p=64$

$9\times5^2+64=17^2\space\space\space\space\space (1)$

$10^{12}\div 64=15625\times10^6>10^9$

So we can construct following relation by multiplying both sides of the relation (1) by $15625\times 10^6=(125\times 10^3)^2$:

$9(5\times 125000)^2+15625\times 10^6=(17\times125000)^2$

that is one solution of equation under condition $p=15625000000>10^9$ is:

$x=625\times10^3$

$y=2125\times 10^3$

This experiment shows that only with particular values of p the equation may have integer solutions.

Answer 5

If we let $\quad A^2+B^2=C^2 \qquad A=3x\quad B=\sqrt{p}\quad C=y\qquad$ we can use Euclid's formula for Pythagorean triples to find infinite solutions based on the value of $(x)$. We start with the formula

$$ \qquad A=m^2-k^2\qquad B=2mk \qquad C=m^2+k^2\qquad$$ and solve the $A$-function for $(k).\quad$ Then we test a defined range of $m$-values to see which yield integers.

\begin{equation} A=m^2-k^2\implies k=\sqrt{m^2-A}\\ \text{for}\qquad \lfloor\sqrt{A+1}\rfloor \le m \le \frac{A+1}{2} \end{equation} The lower limit ensures $k\in\mathbb{N}$ and the upper limit ensures $m> k.$

There are Pythagorean triples for all $A=2n+1$ but A=$3x$, so we are limited to odd muliples of $3:$ $$ x\in\big\{1,3,5,7,\cdots\big\}\implies A\in\big\{3,9,15,21,\cdots\big\}.\quad $$

Here, we will use $x=5\implies A=15$

$$A=15\implies \lfloor\sqrt{15+1}\rfloor=4\le m \le \frac{15+1}{2} =8\\ \land\quad m\in\{4,8\}\implies k \in\{1,7\} $$ $$F(4,1)=(15,8,17)\implies (x,p,y)=(5,8^2,17)\\ F(8,7)=(15,112,113)\implies (x,p,y)=(5,112^2,113) $$