This is a long post. The first half was written by Benjamin Dickman, who shared the problem with me. The second half was written by me, Michael Pershan. Enjoy these two different maps of the same mathematical terrain.
Part One: Benjamin’s Writeup
Part Two: Michael’s Writeup
Let us use the word ‘problem’ to refer to a question for which the method of solution is unknown at the outset. Problems can be viewed on a continuum that ranges from “trivial” to “intractable,” but locating a problem is a function of the individual or group trying to solve it and the resources to which they have access. There is, of course, no single perfect problem for all; but, here is a proposal for one of many perfect problems for some.
There is a wonderful problem for secondary school students looking to be stretched that asks which numbers can be written as the difference of two squares; here, we are roughly in the area of mathematics referred to as “number theory,” and are speaking of numbers that are non-negative integers. It is deeply unfortunate that number theory is not an area of mathematics taught more in our secondary schools across the world; as a result, there are many examples of number theoretical problems that can be effectively posed for students, but for which the techniques or strategies involved are not yet familiar.
Here is a proposed method – in other words, a spoiler – for characterizing the numbers that can be written as a difference of squares: Observe a2 – b2 = (a-b)(a+b); if a and b have the same parity, then the factors a-b and a+b are both even, which means their product is a multiple of 4. If a and b are of different parity, then the factors a-b and a+b are both odd, which means their product is odd. So, a necessary criterion for a number to be expressed as the difference of squares is that it is either a multiple of 4 or odd; it turns out that this is a sufficient criterion, too, as established by the following two identities:
4n = (n+1)2 – (n-1)2 and 2n+1 = (n+1)2 – n2
Uncovering this result is already an opportunity for exciting mathematical exploration with students; their thinking is sure to proceed in a manner much less linear than the description above.
Whenever a problem is solved, there are several options around how to move forward. Here are three such possibilities:
- Abandon the problem and move on to an unrelated one;
- Try to derive the solution in a new way; or
- Try to solve a related problem that is a bit more difficult.
Rich mathematics may (or may not) be uncovered through any of the aforementioned choices, but we will focus here on the third option. (There are slightly different ways of deriving the solution above that will be almost certainly unfamiliar to students; for example, we can observe that a number squared is always 0 or 1 modulo 4; so, the difference of two squares is necessarily odd or a multiple of 4, and this sort of phrasing allows one to bring in topics that are otherwise unseen in K-12 school mathematics: modular arithmetic, quadratic residues, and so forth.)
Our related problem is as follows: Given a nonnegative integer n, in how many ways can it be written as a difference of squares?
This can be viewed as a direct generalization of the earlier problem: if we know how to tell when the answer is “zero ways,” then we know which numbers cannot be written as a difference of squares.
One of the classical strategies for mathematical problem posing is to start with small cases; however, it is often presumed that “small” refers to magnitude (absolute value) and that the ordering from smaller to bigger proceeds additively. That is, one might try looking at 0, then 1, then 2, then 3, etc. But, for a problem whose underlying structure is multiplicative – for example, a problem that might be more easily expressed in the language of factors or factorizations – this additive procession can obfuscate important patterns.
For our problem, we know that the only numbers that can be expressed as a difference of squares are odd numbers and multiples of 4; so, let us begin by investigating the former and see where it leads.
If we have an odd number expressed as a2 – b2, 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) = 82 – 72. 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) = 42 – 12.
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) = 52 – 42 and 9 = (3-0)(3+0) = 32 – 02. 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) = 32 – 12. 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.52 – 3.52; 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 22, 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) = 162 – 142; similarly, 6 and 10 have an average of 8, which leads to the representation 6(10) = (8-2)(8+2) = 82 – 22.
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 102 – 82 and 62 – 02 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) = 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) = 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 pk raised to the respective powers of ak, then the number of factors is the product of (ak + 1) across all k. We close out with one more example.
The number 180 is an even multiple of 4; so, S(180) = ceil(d(180/4)/2). But, what is d(180/4)? Since 180/4 = 45, and 45 has prime factorization 3251, 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 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) = 462 – 442;
180 = 6(30) = (18-12)(18+12) = 182 – 122; and
180 = 10(18) = (14-4)(14+4) = 142 – 42
Q. E. D.
Here is a table that is worth spending some time mulling over.
Here’s what it’s all about: differences of squares.
Given a number, can you tell whether it’s possible to write that number as a difference of squares? Is it possible to characterize all the numbers that are possible to write as a difference of squares? And is there a systematic way to tell how many ways a given number can be written as a difference of squares? An algorithm? A formula?
Let’s tackle these questions in two parts:
- Given a number, can you tell whether it’s possible to write it as a difference of squares, at all?
- If a number can be written as a difference of squares, how many different ways are there to do it?
To start the first question, let’s note that every odd number can be written as a difference of squares. This is due to a wonderful property of squares — they can be decomposed into a sum of odd numbers. Every odd number can be seen as the difference between a large square and some inner, removed square.
That’s not really an explanation as much as restating the statement…ah, well. Here’s a picture:
So, let’s start checking out the small even numbers. Can they be written as a difference of squares?
Starting with the smallest, 2 can definitely not be written as a difference of squares. The smallest difference of squares is 22 – 12 = 3, so 2 is a no-go.
How about 4? That’s a no. (32 – 22 = 5.) How about 6? Also a no-go.
But, wait! 8 works: 32 – 12 = 8.
So…why is that? Why can some even numbers be written as a difference of squares, while others cannot?
Any difference of squares can be written as the product of two numbers: a2 – b2 = (a-b)(a+b). This factoring move can help explain what’s going wrong with so many of these even numbers.
If 6 were to have a representation, then 6 = a2 – b2 = (a-b)(a + b). But there are only so many ways to write 6 as the product of two factors. To make matters worse, the only ways to factor 6 involve one even and one odd factor. To see why this is a problem, note that while 6 = 3 x 2, this couldn’t produce a difference of squares:
a + b = 3
a – b = 2
2a = 5
a = 2.5
b = 0.5
And while it is true that 2.52 – 0.52 = 6, we were only looking for whole numbers.
The issue, then, is that some even numbers can be factored only into pairs of numbers where one is even and the other odd, i.e. of different parity. This explains why 8 works: 2 x 4 = 8, and setting a + b = 4 and a – b = 2 results in (3 + 1)(3 – 1) = 32 – 12 = 8.
As long as the prime factorization of an even number N has just one factor of 2 (as in e.g. 6, 14, 42, 30) then it can only ever be factored into an even and odd factor. That will never work.
As long as your even number is at least divisible by 4, it will always be possible to find at least one solution:
2n(2m + 1)
2(2nm + 2n-1)
a + b = 2nm + 2n-1
a – b = 2
2a = 2nm + 2n-1+ 2
a = 2n-1m + 2n-2+ 1
b = 2n-1m + 2n-2– 1
Both a and b are integers.
There is one other issue to worry about, and that’s 4 itself. 4 = 2 x 2 = (a + b)(a – b) demands that a = 2 and b = 0. Should we count that? It is true that 22 – 02 = 4. It’s not so interesting, which argues in favor of tossing it out of consideration. But sometimes these sort of uninteresting cases can help simplify formulas and generalizations.
Let’s keep an open mind, for now, as to whether we’d rather deal with differences of positive squares or might expand our focus (slightly) to include non-negative squares.
Let’s start with odd numbers. Every odd number can be represented as a difference of squares. But how many representations are there for each odd number?
Consider numbers that are the products of primes, like 15 and 21. They can be all represented in two different ways as differences of squares.
E.g. 15 = (8 + 7)(8 – 7) = (4 + 1)(4 – 1)
E.g. 21 = (11 + 10)(11 – 10) = (5 + 2)(5 – 2)
Then again, this comes as no surprise. If N = pq for p and q both prime, the only factor pairs are 1 x pq and p x q. All the factors are odd, so there are no parity problems — they all produce OK differences of squares.
Not much different for numbers like 147 or 75, which are a product of a prime and a square of a prime:
E.g. 147 = (74 + 73)(74 – 73) = (26 + 23)(26 – 23) = (14 + 7)(14 – 7)
E.g. 75 = (38 + 37)(38 – 37) = (15 + 10)(15 – 10) = (10 + 5)(10 – 5)
All of this still makes sense — 147 and 75 have 6 factors, all odd. That leads to 3 factor pairs, all which work for differences of squares.
In other words, all we’re doing is counting factor pairs, i.e. counting factors and dividing by 2.
E.g. 225 = 32 * 52= (113 + 112)(113 – 112) = (39 +36)(39 – 36) = (25 + 20)(25 – 20)
= (17 + 8)(17 – 8) = (15 + 0)(15 – 0)
This makes sense for 225, which has 9 factors but (including its square root) 5 factor pairs; 9/2 = 4.5, round that up and you get 5.
There is a much better-known number theory function that counts divisors, and it’s multiplicative:
If m and n are relatively prime, divisors(mn) = divisors(m)divisors(n)
So, if you have the prime factorization of a number and its odd, no big deal, you can find out how many ways it can be represented as a difference of squares, no trouble:
E.g. p2 * q8 * r3 has 3 * 9 * 4 = 108 divisors, and can therefore be represented in 54 different ways as a difference of squares.
As a formula, for odd N, N can be described as a difference of squares in ceil[divisors(N)/2] ways.
Now, how do we deal with even numbers? Meaning, those that are divisible by 4. (If they’re not divisible by 4, then they can never be expressed as differences of squares.)
When you have any even number, there are always parity problems you have when it comes to making a difference of squares:
E.g. for 24 = 23 * 3
1 x 24
2 x 12
3 x 8
4 x 6
E.g. for 80 = 24 * 5
1 x 80
2 x 40
4 x 20
5 x 16
8 x 10
E.g. for 84 = 22 * 3 * 7
1 x 84
2 x 42
3 x 28 4 x 21
6 x 14
7 x 12
Compare, in particular, the results for 21 and 84:
|1 x 213 x 7|
There are three times as many factor pairs you get from multiplying 21 by 22. But, of course, 4 of them result in mismatched parity.
Consider one other case, before we head towards a formula: 22 * 32 * 5 * 7. Let’s reason:
- 32 * 5 * 7 should have 3*2*2 = 12 factors and 6 factor pairs, all of which work for differences of squares
- 22 times 32 * 5 * 7 should therefore have 3*12 factors and 18 factor pairs
- Some of these will have mismatched parity, though. We’ll have to toss out all the pairs with an odd factor; as we’ve said, there are 12 odd factors.
- That means 18 – 12 = 6 factor pairs, and we are left with what we started with.
Generalizing, this means that for 2a * N, where N is odd:
- N will have divisors(N) factors (all odd) determined by its prime factorization, and ceil[divisors(N)/2] factor pairs
- 2a N should therefore have ceil[(a+1)divisors(N)/2] factor pairs
- But you have to throw out divisors(N) of those factor pairs, since they contain an odd factor.
That leaves as the number of ways to represent this even number as a difference of squares:
ds(2aN) = ceil[(a+1)divisors(N)/2] – divisors(N)
This formula is certainly ugly, but it works for the cases above, plus a few more:
|80 = 24 * 5||ceil[5 x 1] – 2 = 3|
|24 = 23 * 3||ceil[4 x 1] – 2 = 2|
|84 = 22 * 3 * 7||ceil[3 x 2] – 4 = 2|
|180 = 22 * 32 * 5||ceil[3 x 3] – 6 = 3|
|36 = 22 * 32||ceil[3 x 1.5] – 3 = 2|
|60 = 22 x 3 x 5||ceil[3 x 2] – 4 = 2|
Can we extend this formula in a meaningful way to even numbers that aren’t divisible by 4?
42 = 2 x 3 x 7, ceil[2 x 2] = 4 = 0.
30 = 2 x 3 x 5, ceil[2 x 2] – 4 = 0
18 = 2 x 32, ceil[2 x 1.5] – 3 = 0
Yes, I think so!
For 21N, ceil[2 x divisors(N)/2] – divisors(N) = ceil[divisors(N)] – divisors(N) = 0
Can we extend this formula to odd numbers, that aren’t even divisible by 2? Well, not really:
For 20N, ceil[1 x divisors(N)/2] – divisors(N)
But we can patch it up. Rather than subtracting divisors(N), let’s subtract badDivisors(N), which are the divisors of N that wouldn’t work for difference of squares tally. Of course, for odd numbers there are no bad divisors, so badDivisors(N) = 0 for ever odd.
Here is our ur-formula, then:
|For 2aN, the number of difference of squares representations are:|
ceil[(a+1)divisors(N)/2] – badDivisors(N)
For odd N badDivisors(N) = 0 so the formula simplifies to:
ceil[(0+1)divisors(N)/2] – 0 = ceil[divisors(N)/2]
For 21N, this simplifies to:
ceil[2 x divisors(N)/2] – divisors(N) = 0
Note that for the ceiling function, ceil[x + n] = ceil[x] + n where n is an integer. We can use this to prove something for another special case.
For 22N, our formula simplifies to:
ceil[3 x divisors(N)/2] – divisors(N)
= ceil[divisors(N)/2 + divisors(N)] – divisors(N)
=ceil[divisors(N)/2] + divisors(N) – divisors(N)
So multiplying an odd number by 4 does not alter the number of ways it can be represented as a difference of squares.
More generally, for 22mN:
ceil[(2m + 1) x divisors(N)/2] – divisors(N) =
= ceil[(divisors(N)/2 + 2m x divisors(N)/2] – divisors(N)
=ceil(divisors(N)/2) + (m – 1)divisors(N)
Though maybe it makes more sense to consider the patterns of growth in two separate cases — the case of square and non-square odd Ns.
|21 = 3 x 7||ceil[1 x 2] – 0 = 2|
|42 = 2^1 x 3 x 7||ceil[2 x 2] – 4 = 0|
|84 = 2^2 x 3 x 7||ceil[3 x 2] – 4 = 2|
|168 = 2^3 x 3 x 7||ceil[4 x 2] – 4 = 4|
|336 = 2^4 x 3 x 7||ceil[5 x 2] – 4 = 6|
|672 = 2^5 x 3 x 7||ceil[6 x 2] – 4 = 8|
|25 = 52||ceil[1 x 1.5] – 0 = 2|
|50 = 2152||ceil[2 x 1.5] – 3 = 0|
|100 = 2252||ceil[3 x 1.5] – 3 = 2|
|200 = 2352||ceil[4 x 1.5] – 3 = 3|
|400 = 2452||ceil[5 x 1.5] – 3 = 5|
|800 = 2552||ceil[6 x 1.5] – 3 = 6|