0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please use MathJax - few people want to try to decipher anything else. Thanks. $\endgroup$ – Bobson Dugnutt Oct 17 '16 at 15:59
  • 1
    $\begingroup$ Pretty much all you need is to enclose the maths in dollars (double dollars for displayed formulae). Then it's better to replace the * for multiplication with \cdot. That doesn't take even a week to learn. Doing complicated formatting may take a while to learn, but the basics are quickly absorbed. $\endgroup$ – Daniel Fischer Oct 17 '16 at 17:30
  • 2
    $\begingroup$ As @DanielFischer says, it is really not that difficult. One last thing you need to know is that exponents that are longer than just one symbol (say, if you want to write $e^{ax}$), you need to surround the expression in the exponent with curly brackets, i.e. e^{ax} (with dollar signs around it). The same applies if you want to write something with indices, say $T_{ij}$ (write "T_{ij}"). Otherwise the expression will look like this: $e^ax$ and $T_ij$. Cheers. $\endgroup$ – Bobson Dugnutt Oct 17 '16 at 18:05
  • 2
    $\begingroup$ My intuition told me it was false but... n^2 = 1+3+5+....2n-1=(1+2+3+...+n)+(1+2+3+....+(n-1)) so it is true. Also T_n =n (n+1)/2 so T_n+T_{n-1} =((n-1)n+n (n+1))/2= 2n^2/2=n^2. So it is true and my intuition is wrong. $\endgroup$ – fleablood Oct 17 '16 at 19:26
  • 2
    $\begingroup$ Daniel Fisher and Lovsovs, I can't thank you enough for teaching me how to use latex in few sentences. I will always be grateful to both of you. And this is how this issue should be approached, showing to people how to do something not by screaming at them for not having done it. $\endgroup$ – user25406 Oct 17 '16 at 19:47
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you for your comment. If I understand, you are saying the two methods are equivalent. That they both give for N=13, N = 13 = 4 + 9. $\endgroup$ – user25406 Oct 20 '16 at 20:58
  • $\begingroup$ @user25406 after some reflection, my suggestion is that you try your method in two examples, first $N = 221,$ then $N = 209.$ $\endgroup$ – Will Jagy Oct 20 '16 at 21:56
  • $\begingroup$ @user25406 I thought you would find a difference in behavior and learn something that way, in your own way of thinking... anyway, $221 = 13 \cdot 17 = 14^2 + 5^2 = 11 ^2 + 10^2,$ but $209 = 11 \cdot 19$ is not the sum of two squares. If, in the prime factorization of a number, there is some prime $q \equiv 3 \pmod 4,$ and the exponent is odd, then the number cannot be expressed as the sum of two squares. This applies to both $11$ and $19,$ both with exponent $1.$ $\endgroup$ – Will Jagy Oct 21 '16 at 16:51
  • $\begingroup$ For the number 221 = 10^2 + 11^2, I made a mistake in my calculation because I was using the expression for N= x^2+ y^2= (T(n) + T(n+1)) + (T(n+k) + T(n+k+1)) which is wrong and should be N= (T(n) +T(n+1)) + (T(n+k+1) + T(n+k+2)). But the quadratic used was correct.. After the correction and using the values of (n=9,-12,k=0), I was able to find N=10^2 +11^2. I did get more values of the indices (n,k) so the N=14^2 +5^2 is among them. However, for 209, the method could not find a solution. Thank you for explaining why that was the case. I corrected the formula in the post. $\endgroup$ – user25406 Oct 21 '16 at 18:03
  • $\begingroup$ For completeness and because I could not fit my answer in my previous comment, I am providing another solution for N=221. The pair (k=8, n=4) provides another pair of squares, mentioned already in Will's post. N= (T(4) + T(5)) + (T(13) + T(14))= (10 + 15) + (91 + 105)= 5^2 + 14^2. So the method failed to provide a solution for N=209, not because it cannot provide one, but because of the nature of the primes involved in 209=11*19. $\endgroup$ – user25406 Oct 21 '16 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.