The new year 2024 is a difference of squares, , which got me thinking about a fun little number theory problem:
Is there a largest number that can not be expressed as the difference of squares? If so, find it. If not, prove no such number exists. Good luck, and happy new year!
As promised, here’s my solution.
There are infinitely many numbers that can not be expressed as a difference of squares. In fact, we can completely characterize numbers that can be expressed as a difference of squares and those that can’t. It all starts with factoring.
Differences of squares have a useful structure that can be exposed by factoring:
We can leverage this structure to answer our question.
Suppose n can be factored as . If n can be expressed as a difference of squares, then we can also write
Now set and . This gives us the system of equations
We can solve this system by adding and subtracting the equations. Adding gives us , and subtracting gives us . This shows us how to express n as a difference of squares: Just factor n into , compute and , and then .
There’s only one thing we have to worry about: a and b must be integers. But as long as s and t have the same parity — that is, s and t are both even or both odd — then the sum and difference of s and t will both be even, and so will be an integer.
This means that n can be expressed as a difference of squares if and only if we can write where s and t are both odd or both even. This is usually possible, often in multiple ways. But there’s one situation when it isn’t: When n is divisible by 2 exactly once. When this is true, then however you factor n into , the lone factor of 2 will end up as a part of either s or t, making one of them even and the other odd. Thus, in this case, it’s impossible to factor n so that the two factors have the same parity, and so it’s impossible to express n as a difference of squares.
This gives us a complete answer to our question: A number n is not expressible as a difference of squares if and only if it is divisible by 2 exactly once! In other words, every odd number times 2 is not expressible as a difference of squares, and every other integer is.
As an example, given , we can factor which gives and , and sure enough, . Notice, we could also write , which gives and , so .
On the other hand, it isn’t possible to do this at all for 6. There are only two factorizations, and , and in both cases the factors have different parity, so the a and b we need won’t be integers.
There’s an interesting resemblance here to Euclid’s Formula for generating Pythagorean triples. There’s also an interesting follow-up question about how many different ways a number can be expressed as a difference of squares. And since the numbers that answer our question are those that are divisible by 2 exactly once, I wonder what properties numbers that are divisible by 3 exactly once have.
Thanks to everyone who contributed on the Mastodon thread! There are some cool ideas there as well, so be sure to check it out.
Related Posts