Finding Integer Solutions to $x^2-y^2-n=0$

Question

I am trying to find the integer solutions to the equation $x^2-y^2-n=0$.

Effectively, I am trying to find when the difference of two perfect squares is $n$

I have tried using a modified Newton's method to find the nearest point where the equation reaches parity; however, it ends up finding non-integer solutions. I am wondering if there is a way to factor/find all the integer solutions to this equation.

For my algorithm, taking the square root is prohibitively costly and I am trying to avoid using it.

Thanks for the help!

Answer 1

Given $x^2-y^2-n=0\implies y^2+n=x^2\quad$ if $n$ is a perfect square, we have the equation for the Pythagorean theorem where $A^2+B^2=C^2$. The B-value can be any multiple of $4$ so $n=(4z)^2, z\in\mathbb{N}$. There are infinite solutions. Finding them requires a square root but all values of $\sqrt{n}$ are known beforehand so there are always values of $x,y$ to be found in a finite search.

Let's begin with a form of Euclid's formula $F(m,k)$ where $\quad A=m^2-k^2\quad B=2mk\quad C=m^2+k^2.\quad$ We can find $m,k$ by solving $B$ for $k$ and test a finite number of m-values to see which yield integers.

\begin{equation} B=2mk\implies k=\frac{B}{2m}\qquad\text{for}\qquad \bigg\lfloor \frac{1+\sqrt{2B+1}}{2}\bigg\rfloor \le m \le \frac{B}{2} \end{equation} The lower limit ensures $m>k$ and the upper limit ensures $k\ge 1$ $$B=44\implies\quad \bigg\lfloor \frac{1+\sqrt{88+1}}{2}\bigg\rfloor =5 \le m \le \frac{44}{2}=22\\\land \quad m\in\{11,22\}\implies k\in\{2,1\}$$

$$F(11,2)=(117,44,125)\qquad\qquad F(22,1)=(483,44,485)$$

Alternatively, you can just find a list of triples and translate them to fit your equation. For instance, here are examples of triples $A,B,C$ translated to $y,n,x$.

$3,4,5\rightarrow 3,16,5\quad 15,8,17\rightarrow 15,64,17\quad 5,12,13\rightarrow 5,144,13\quad 35,16,37\rightarrow 35,256,37$

Answer 2

Suppose $(x, 3)=1$, also $(y, 3)=1$, the due to FLT we have:

$x^2-y^2 \equiv (x-y) \ mod (3)$

So a family of solution can be found if $x-y =3k$ such that:

$x^2-y^2= 3m$

Examples:

$x=5$, $y=2$ $\rightarrow 25-4=21=3\times 7$

Another family of solution can be found when $x\equiv ± 1$ also $y \equiv ± 1 \mod (3)$ in this case we have:

$x^2-y^2\equiv (1-1=0)mod (3)$

For example $x=7\equiv 1 \mod (3)$, $y=2 \equiv -1 \mod (3)$ then:

$49-4=45= 3\times 15$

Answer 3

We have

$$x^2-y^2-n=0\iff(x+y)(x-y)=n$$

so if you are looking for integer solutions, all you need to do is factorize $n$ as $ab$, let $x+y=a$ and $x-y=b$, obtaining $x=(a+b)/2$ and $y=(a-b)/2$, and then observe that the factorization $n=ab$ must have factors of the same parity (in order for $x$ and $y$ to be integers). This parity condition can always be met if $n$ is odd or a multiple of $4$, but not if $n$ is twice an odd number.

When $n$ is odd, there is always the factorization $n\cdot1$, giving $x=(n+1)/2$ and $y=(n-1)/2$. When $n=4m$, there is always the factorization $(2m)\cdot2$, giving $x=m+1$, $y=m-1$. When $n$ (or $m$) is prime, that's all you get (up to sign). But in composite cases, you get additional solutions.

Remark: I finally read the comments beneath the OP and saw that this approach was already described there. To reiterate a point made there, solving $x^2-y^2-n=0$ is essentially equivalent to factoring $n$. For odd integers $n$, it is known as Fermat's factorization method, which is the starting point for the more powerful Quadratic sieve approach to factoring.