Representing integers as the difference of two squares

Most integers can be represented as a difference of two squares, where each square is a non-negative integer.

Algebraically speaking:

$n = x^2 - y^2$

for some non-negative integers

$x$ and

$y$ .

In this blog post we're going to look at a simple and elegant algorithm for finding all the possible representations for any given integer that can be represented as a difference of two squares, using its divisors.

For example, if we have

$n = 12345$ , we can represent it in four different ways as a difference of two non-negative integer squares:

$12345 = 419^2 - 404^2$

$12345 = 1237^2 - 1232^2$

$12345 = 2059^2 - 2056^2$

$12345 = 6173^2 - 6172^2$

# Finding solutions

By writing

$n$ as the product of two whole numbers,

$n = a*b$ , we have the following identity:

$a*b = ((a+b)/2)^2 - ((a-b)/2)^2$

Then, by iterating over all the divisors of

$n$ , we generate all the possible representations for

$n$ as a difference of two non-negative squares.

In order to generate only integer solutions, we have to make sure that

$a+b$ is even. In general, when

$n$ is even, we can iterate only over its even divisors. Otherwise, we iterate over its odd divisors.

Algorithm:

Let

$d$ run over the divisors of

$n$ which are

$d <= sqrt(n)$ and have the same parity as

$n$ .

For each such divisor

$d$ , we generate a new solution to

$n = x^2 - y^2$ , as:

$x = (n/d + d)/2$

$y = (n/d - d)/2$

Illustrating this with an example, let

$n = 24$ . As

$24$ is even, we are going to iterate only over its even divisors, which are:

$[2, 4, 6, 8, 12, 24]$ .

First divisor in the list,

$d=2$ :

$x = (n/d+d)/2 = 7$

$y = (n/d-d)/2 = 5$

Second divisor in the list,

$d=4$ :

$x = (n/d+d)/2 = 5$

$y = (n/d-d)/2 = 1$

Solutions:

$24 = 7^2 - 5^2$

$24 = 5^2 - 1^2$

In fact, this are all the representations for

$24$ as a difference of two non-negative integer squares, because in the next iteration,

$d=6$ , we would have

$n/d = 4$ , and since

$n/d < d$ , this would generate negative solutions, which are essentially the same as the positive ones, so we can stop here.

# Extra

Finding a non-trivial representation for a semiprime

$n$ as a difference of two squares, is just as hard as factoring

$n$ , because:

$x^2 - y^2 = (x + y) * (x - y)$

For example, if we have

$n = 15709691830279$ and we also know a non-trivial representation for it:

$n = 4384780^2 - 1875261^2$

Then we can factorize it as:

$n = (4384780 + 1875261) * (4384780 - 1875261)$

From this results that if we know only the sum or the difference of the prime factors of a semiprime, we can find its prime factors in polynomial time.

Let

$t$ be the absolute difference between the two prime factors of a semiprime

$n$ (i.e.:

$t=abs(p-q)$ , for

$n = p*q$ ):

$x = sqrt(t^2 + 4n) / 2$

$y = t/2$

Alternatively, let

$s$ be the sum of its two prime factors (i.e.:

$s = p+q$ , for

$n = p*q$ ):

$x = s/2$

$y = sqrt(s^2 - 4n) / 2$

Then

$n$ can be factorized in both cases as:

$n = (x+y) * (x-y)$

# Implementations

Bellow we have a Perl implementation of the algorithm described in this post.

Difference of two squares - algorithm implementation:

Perl: difference_of_two_squares_solutions.pl

Extra:

Perl: difference_of_three_squares_solutions.pl

Next time we're going to look at an algorithm for representing an integer as a sum of two squares, which is a slightly more advanced problem.

Perl: sum_of_two_squares_all_solutions.pl
Sidef: sum_of_two_squares_solutions.sf

See also:

Mathematics and computer science