Is this the general solution of finding the two original squares that add up to a given integer N?

Sometimes we are given an integer N and we want to know if it is the sum of two squares.

We know that the sum of two consecutive triangular numbers is always a square. So we can write $$ S_1 = T_n + T_{n+1} $$ and $$ S_2= T_{n+1} + T_{n+2} $$ It is enough to add $S_1$ and $S_2$ to get a number N that is the sum of two squares. And we can write $$ N = (T_n + T_{n+1}) + (T_{n+1} + T_{n+2}) $$

We give a simple example. $$ N = (T_1 + T_2) + (T_2 + T_3) = (1+3) + (3+6) = 2^2 + 3^2 = 13 $$

But we do not want to limit ourselves to the sum of two consecutive squares. We want to consider the general case $$ N = x^2 + y^2 $$ with $x^2$ and $y^2$ not consecutive. So we rewrite the above equation as:
$$ N = x^2 + y^2 = (T_n + T_{n+1}) + (T_{n+k+1} + T_{n+k+2}) $$

The question here is: given a number N, can we find the two squares that add up to it? And surprisingly, the answer is yes. At this point, it is useful to provide the definition of a triangular number. $$ T_n = n\cdot (n+1)/2 $$

So, it is easy to see that when we replace the T's with their definition, we will end up with a quadratic equation which can be solved to provide us with the indices n and k.

$$2N = (n(n+1) + (n+1)\cdot (n+2)) + ((n+k+1)\cdot (n+k+2) + (n+k+2)\cdot (n+k+3)$$

If I did not make any mistake in the algebra, we get the following equation:

$$2n^2 + (2k+6)n + k^2 + 4k + 5 -N = 0 $$

By solving this equation, we get two solutions, $n_1$ and $n_2$. The condition for a solution is that:

$$(2k+6)^2 -8\cdot (k^2 + 4k + 5 - N ) = s^2$$

If we set k=0 ( for N=13 ), we get $$ \sqrt{36 + 64}=10^2 $$ and $n_1=1$, and $n_2=-4$
So we see that it is possible, given a number N which we assume is the sum of two squares, to get back the indices in the original equation. Of Course, we know that, in the general case, we have a parametric equation in k and we want the discriminant $$b^2-4ac=m^2$$ to be a perfect square. We may have to try few values of k before we hit on the solution. But it is possible to start from N and go back to the $T_n$

It is also known that for triangular numbers, we have $$ 8\cdot T_n + 1 = m^2 $$

We can do the same in this case as what we did with the previous case. We can consider the general case of $$ N = (8\cdot T_{n} +1) + (8\cdot T_{n+k} +1) $$
We can work out the algebra by using the definition of $T_i$ and we will end up again with a quadratic equation in n and k, k being just a parameter. And we will get two solutions and the positive solution will provide us with the indices we need to go from N to $x^2$ and $y^2$.

The question here is: does this method provide the general solution to the problem of going from N to $x^2$ and $y^2$ or just a subset of solutions?

As a bonus, we get (if we allow negative indices for $T_n$ ) a simple relation:
$$ T_{-n} + T_{+n} = m^2 $$

And by the way, this method does not really care if N is a prime or not. There is really nothing special about N being a prime. More importantly, this method does not need to factor N and that may be an advantage over the methods that do.

Appendix 1- We need to address the question raised in one of the comments concerning the ability of the method to find all pairs of squares ($x^2$ and $y^2$) for numbers that can be represented as a sum of two squares in more than one way. It is clear that the quadratic equation derived above can only produce one pair at a time.

For this, we consider the number 50 which is the smallest number that admits two representations as a sum of squares.
$$ 50 = 1 + 7^2 = 5^2 + 5^2 $$ We are looking for values that will make the discriminant $$b^2-4ac=m^2$$ a perfect square.

$$(2k+6)^2 -8\cdot (k^2 + 4k + 5 - N ) = s^2$$
when we expand and plug in the value of N=50, we get the following equation

$$396 - 4k^2 -8k = s^2$$ or equivalently $$ 4\cdot (99 - k^2 -2k)=s^2 $$ we will simply list the triplets $$ (k,n_{1},n_{2}) $$ that are solutions and that will allow us to write $$ 50 = (T_n + T_{n+1}) + (T_{n+k+1} + T_{n+k+2}) $$ They are $$ (k,n_1,n_2) = (5,0,-8),(7,-2,-8),(9,-6,-6) $$ Here we need to specify that negative values of $n$ should be considered in calculating the representations of 50. We also need to specify that $T_{0}=0$ needs to be considered as the first triangular value. Let's use the first and last triplets to show how it works. To begin with, there is only one value of k for every pair of values of n so each triplet will give two pairs $$(k,n_{1})=(5,0)$$ and $$(k,n_{2})=(5,-8) $$
$$50 = (T_{0} + T_{1}) + (T_{6} + T_{7}) = (0 +1) + (21+28) = 1^2 + 7^2 $$ and
$$50 = (T_{-8} + T_{-7}) + (T_{-2} + T_{-1}) = (28 + 21) + (1+0) = 7^2 +1^2$$ For the last triplet, we only need to consider one pair since they are identical. For the pair $$(k,n) = (9,-6)$$ we get: $$50 = (T_{-6} + T_{-5}) + (T_{4} + T_{5}) = (15 + 10) + (10+15) = 25 +25 = 5^2 + 5^2 $$ When using negative indices, we need to use the defining equation for $T_{n}$ that is $$ T_{n} = n\cdot (n+1)/2 $$ So we see that it was possible to find the two pairs of squares that add up to 50, one at a time. A nice feature of the discriminant is that as we increase the value of k when looking for solutions, the value of the discriminant itself is rapidly decreasing. This means that the convergence to square values of the discriminant is fast.

Appendix-2

For completeness, we will provide an example of the implementation of the second case involving the expression:

$$ N = (8\cdot T_{n} +1) + (8\cdot T_{n+k} +1) $$ In this case the quadratic equation to be solved to determine the triplets $$(k,n_{1},n_{2})$$ is:

$$ 8n^2 + 8\cdot (k+1)n +4k^2 + 4k +2 -N = 0 $$

We first need to provide an example of a number that is the sum of two squares. For this we choose $$(n=1,k=5)$$

$$ N = x^2 + y^2 = (8\cdot (T_{n}) +1) + (8\cdot (T_{n+k}) +1) $$

$$ N = x^2 + y^2 = (8\cdot (T_{1}) + 1) + (8\cdot (T_{6}) + 1) $$ $$ N = x^2 + y^2 = (8+1) + (8\cdot (21) +1) $$ $$ N = x^2 + y^2 = 9 + 169 = 3^2 + 13^2 = 178 $$

Now that we have $$ N=178= 3^2 +13^2 $$ that is a sum of two squares by construction, we will show that we can recover the two squares whose sum adds up to N without having to factor N. We are looking for values of k that will make the discriminant $$b^2 -4ac=s^2$$ a square in the previous quadratic equation. The discriminant is given by $$ 8N -16k^2 $$ We get the values of k that makes the discriminant a square by checking $$ k=0,1,2,3...$$ It turned out that the value of k=5 is one of the values that make the discriminant a square (though we did not look for other values of k). The corresponding values of $$n_{1},n_{2}$$ are $$n_{1}=1,n_{2}=-7$$

Keep in mind that each triplet $$ (k,n_{1},n_{2}) $$ will provide two pairs $$ (k,n_{1}), (k,n_{2})$$ to use in the original equation $$ N = (8\cdot T_{n} +1) + (8\cdot T_{n+k} +1) $$

It is easy to see that the pair $$(k=5,n_{1}=1)$$ will get us the following $$ N = 178 = (8\cdot (T_{1}) + 1) + (8\cdot (T_{-2}) +1) = 9 + 169 = 3^2 +13^2$$

The other pair $$(k=5,n_{2}=-7)$$ will provide us with $$ N = 13^2 + 3^2$$ which is basically the same pair.

Again, we see that we were able to get back the two original squares whose sum adds up to N with very little effort. And again we want to point out that when we are increasing the value of k to find the one that makes the discriminant a square, the value of the discriminant itself is decreasing. This means that the number of steps needed to find all representations of $$ N = x^2 + y^2 $$ is finite.

We need to mention that we have two quadratic equations to solve to get the two squares that add up to a given number N. It is not known how specific the test to determine which equation to use is but if $$ (N-2)=8\cdot j $$ then we use the second equation to find the values of k and the corresponding values of the index n.

Solution 1:

Since you emailed me about this:

" The condition for a solution is that: $$(2k+6)^2 -8\cdot (k^2 + 4k + 5 - N ) = s^2$$"

That is, $$ 4k^2 + 24 k + 36 - 8 k^2 - 32 k - 40 + 8 N = s^2, $$ $$ -4k^2 -8 k -4 + 8 N = s^2, $$ $$ 8N -4k^2 -8 k -4 = s^2. $$ It follows that $s$ is even, $s= 2t,$ $s^2 = 4 t^2$ $$ 8N -4k^2 -8 k -4 = 4 t^2. $$ $$ 2N -k^2 -2 k -1 = t^2. $$ $$ 2N - (k+1)^2 = t^2. $$ $$ 2N = (k+1)^2 + t^2. $$

That is, your method for writing $N$ as two squares is to write $2N$ as two squares. It might appear that this is different from the original task, however, if $$ 2N = u^2 + v^2, $$ then $u \equiv v \pmod 2$ and $$ N = \left( \frac{u+v}{2} \right)^2 + \left( \frac{u-v}{2} \right)^2. $$

If $$ N = a^2 + b^2, $$ then $$ 2N = (a + b)^2 + (a-b)^2. $$

There is, thus, a bijection between the problems.