How many ways can a number $n>2$ be expressed as the difference of two squares?

Question

I provide my answer to the title question, which I pursue purely out of my own curiosity. My question to the community is: Have I thought this through correctly, or have I made one or more mistakes?

It is identically true algebraically, $$\Bigl(\frac{\frac{n}{t}+t}{2}\Bigr)^2-\Bigl(\frac{\frac{n}{t}-t}{2}\Bigr)^2=n$$ when $t\mid n$ and the following conditions hold: $\frac{n}{t}>t$ and $\frac{n}{t}\equiv t\mod{2}$. The first condition is necessary to ensure that both LHS terms inside the brackets will be positive, and the second condition is necessary to ensure that each LHS numerator is even, so that each LHS fraction is an integer.

My first conclusion is: The number of ways to express $n$ as the difference of two squares will simply be equal to the number of examples of $t$ that meet the stated conditions.

Let $n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$. Then for any factor $t$ of $n$, $t=p_1^{b_1}p_2^{b_2}\cdots p_m^{b_m}$ where $0\le b_i\le a_1$ (with the stipulation that $a_i>0$). Each prime factor $p_i$ may appear from $0$ to $(a_i)$ times in various $t$, giving $(a_i+1)$ choices, so the total number of factors $\tau(n)=(a_1+1)(a_2+1)\cdots(a_m+1)$.

But not all factors will meet the required conditions. I note that a question has been posed and answered here about a very limited instance of my question, where every $p_i$ is odd and every $a_i=1$.

The first condition, $\frac{n}{t}>t$, requires that $t$ be strictly smaller than $\sqrt{n}$. This is in general easy to accommodate because for every factor $t<\sqrt{n}$ there is a corresponding factor $\frac{n}{t}>\sqrt{n}$. So the number of factors smaller than $\sqrt{n}$ is just $\frac{\tau(n)}{2}$ with one caveat. If $n$ happens to be a perfect square, then there will be one factor $t=\frac{n}{t}=\sqrt{n}$, in which case the number of factors would be $\frac{\tau(n)-1}{2}$. This ambiguity can be addressed using the floor function: the number of factors that comply with the first requirement can be expressed as $\lfloor \frac{\tau(n)}{2}\rfloor$.

Next, accommodation must be made for the second requirement $\frac{n}{t}\equiv t\mod{2}$. In effect, this means that if $n$ contains factors of $2$ within it, they may not all be included in, or omitted from, $t$. If $n=2^xq$ where $q$ is odd, then with respect to the exponent of $2$ we must have $1\le b\le (x-1)$. There are two fewer options (i.e. $0$ and $x$) to choose from.

So if $n$ is even, we must multiply our previous result (i.e. $\lfloor \frac{\tau(n)}{2}\rfloor$) by $\frac{x-1}{x+1}$ to replace the incorrect multiplier $(x+1)$ with the correct value $(x-1)$. Note that if $2$ is present in $n$ only once, the correction factor $\frac{x-1}{x+1}=0$. This correctly shows that any number which is twice an odd number (including the number $2$ itself) cannot be expressed as the difference of two squares. This fact is independently known because $2(2j+1)=4j+2\equiv 2 \mod{4}$ which cannot be the difference of two squares.

I conclude that the number of ways that a number $n>2$ can be expressed as the difference of two squares is $\lfloor \frac{\tau(n)}{2}\rfloor$ if $n$ is odd, and $\lfloor \frac{x-1}{x+1} \cdot \frac{\tau(n)}{2}\rfloor$ in $n$ is even, where $x$ is the exponent of $2$ in the prime factorization of $n$.

Answer 1

The OEIS page linked in the comments (A100073) gives the following formulas:

a(n) = floor(numdiv(n)/2) for odd n;

floor(numdiv(n/4)/2) for n = 4k; and

0 else

Below is a verbose proof that uses the ceiling function rather than the floor function, as I propose that a more natural approach is to include $0$ as an admissible number in broaching this problem.

You can find this proof, along with another write-up, at the blog post here.

---

If we have an odd number expressed as $a^2 - b^2$, then we also have a factor pair for that number: $a-b$ and $a+b$. Indeed, any factor pair for an odd number can be written in this manner, for two factors of an odd number must both be odd, and this will mean that their average is a whole number, from which we can adjust up and down by the same amount to recover a representation in the $a-b$ and $a+b$ form. Specifically, we use $a$ as the factor pair’s average and adjust by $b$. This all becomes more clear by way of example.

Consider the odd number $15$, which has factor pairs $(1, 15)$ and $(3, 5)$. For the first factor pair, we find the average of $1$ and $15$ to be $8$, and note that $1 = 8-7$ and $15 = 8+7$. As a result, we can express $15$ as $1(15) = (8-7)(8+7) = 8^2 - 7^2$. Similarly, we can look to the second factor pair and find the average of $3$ and $5$ to be $4$, and note that $3 = 4-1$ and $5 = 4+1$. As a result, we can express $15$ as $3(5) = (4-1)(4+1) = 4^2 - 1^2$.

We have now established a matching between two representations of $15$: the first representation is as a specific difference of squares, and the second representation is as a specific factor pair. The number of factor pairs is usually equal to half the number of factors; the only exception is if the number of factors is odd, which occurs precisely when we are dealing with a perfect square. As we deal with nonnegative (rather than positive) integers, let us establish in that setting that we will continue to use the number of factor pairs as the number of ways to express our number as a difference of squares; so, we will take the total number of factors, add $1$, then divide by $2$ for our result. Again, let us clarify by way of example.

Consider the odd square $9$, which has factor pairs $(1, 9)$ and $(3, 3)$. As in the example with $15$, we use these factor pairs to produce the following representations of $9$ as a difference of squares: $9 = (5-4)(5+4) = 5^2 - 4^2$ and $9 = (3-0)(3+0) = 3^2 - 0^2$. Note that, if we were to adhere to positive integers only, we would not be able to use zero in our latter representation. The result of this is still that the number of representations, $2$, is equal to our number of factor pairs; but, the number of factors is $3$, so it is not quite right to say we have $3/2$ representations. Instead, we add $1$ to the number of factors, thereby double-counting the factor $3$, which gives us $4$ total factors (counted with multiplicity among factor pairs) and halving this gives us the desired result: $2$ ways to represent the odd square $9$ as a difference of squares.

As we segue to multiples of $4$, we find that matters are slightly more complicated. For an illustrative example, consider that of $8$: its factor pairs are $(1, 8)$ and $(2, 4)$. The latter factor pair generates a difference of squares: $2(4) = (3-1)(3+1) = 3^2 - 1^2$. Unfortunately, matters go somewhat awry with the former factor pair: the average of $1$ and $8$ is $4.5$; it is true, numerically, that $1(8) = (4.5-3.5)(4.5+3.5) = 4.5^2 - 3.5^2$; however, we have decided only to use nonnegative integers, which means that this difference of squares is inadmissible for our present purpose.

The issue at hand for the above-described example is that $1$ and $8$ have different parity; as a result, their average is a non-integer. To resolve this, we need to ensure that every factor pair for the multiples of $4$ has two factors with the same parity. As the product is even, this means, in particular, that each of the factors needs to be even; so, we propose the following resolution: Given a number $n = 4m$, factor out the $4$, which is equal to $2 \times 2$, and consider all of the factor pairs for $m$. Next, we modify every factor pair by multiplying each factor by $2$; as we double each of the factors, we end up with $4m$ as the product, which is equal to our starting number of $n$. Let us illustrate matters again by way of example.

Consider $60$, which is an even multiple of $4$. Let us now factor out a $4$, which leaves us with the number $15$ to consider. We saw earlier that $15$ has factor pairs $(1, 15)$ and $(3, 5)$. We can now modify these pairs by doubling the factors in each to yield $(2, 30)$ and $(6, 10)$; these now give us all of the factor pairs with the same parity for $60$, which means we can express $60$ as a difference of squares using them: $2$ and $30$ have an average of $16$, which leads to the representation $2(30) = (16-14)(16+14) = 16^2 - 14^2$; similarly, $6$ and $10$ have an average of $8$, which leads to the representation $6(10) = (8-2)(8+2) = 8^2 - 2^2$.

The result of this line of thinking is that when $n$ is a multiple of $4$, the number of representations of $n$ as a difference of squares is the number of factor pairs for $n/4$; as was the case for the odds, the number of factor pairs is usually half the number of factors, but in the case of a perfect square we would need to add $1$ to the number of factors to count them with multiplicity among the various factor pairs. One more example should do the trick in clarifying this matter.

Consider $36$, which is an even multiple of $4$ and a perfect square. We can divide it by $4$ to get $9$, which we saw earlier yields the factor pairs $(1, 9)$ and $(3, 3)$. Multiplying each factor by $2$, we arrive at $(2, 18)$ and $(6, 6)$. Respectively, these yield $10^2 - 8^2$ and $6^2 - 0^2$ as the two ways in which $36$ can be represented as a difference of squares. Just as occurred with our odd square case examined above, we are using the number of factor pairs (here, for $36/4$), but this is slightly different from the number of factors: there are only three factors across the relevant factor pairs, but we count one of them (the $6$) with multiplicity as it appears twice in the pair $(6, 6)$. As a result, we end up with $36/4 = 9$, which has $3$ factors; adding $1$, we get $4$ factors; dividing $4$ by $2$, we get our answer: there are two ways to represent $36$ as a difference of squares.

If we decide to summarize the above thinking succinctly, then we can use the ceiling function (rounding, if necessary, to the nearest integer greater than or equal to its input) for our final result. Defining $d(n)$ to be the number of divisors, or factors, of the natural number $n$, and $S(n)$ to be the number of ways in which $n$ can be represented as a difference of nonnegative squares, we have the following:

If n is odd, then $S(n) = \text{ceil}(d(n)/2)$;

If n is even but not a multiple of $4$, then $S(n) = 0$;

If n is even and a multiple of $4$, then $S(n) = \text{ceil}(d(n/4)/2)$

Finally, we recall that the number of factors can be computed if we know a natural number’s prime factorization. In particular, if we write $n$ as a product of the primes $p_k$ raised to the respective powers of $a_k$, then the number of factors is the product of $(a_k + 1)$ across all $k$. We close out with one more example.

The number $180$ is an even multiple of $4$; so, $S(180) = \text{ceil}(d(180/4)/2)$. But, what is $d(180/4)$? Since $180/4 = 45$, and $45$ has prime factorization $3^2 5^1$, we have that its number of factors is equal to $(2+1)(1+1) = 3(2) = 6$; so, we find $d(180/4)/2 = 6/2 = 3$, and $\text{ceil}(3) = 3$. This tells us that the number of representations of $180$ as a difference of squares is $3$. Indeed, we can verify this by listing them out exhaustively:

$$180 = 2(90) = (46-44)(46+44) = 46^2 - 44^2$$

$$180 = 6(30) = (18-12)(18+12) = 18^2 - 12^2$$

$$180 = 10(18) = (14-4)(14+4) = 14^2 - 4^2$$