Since it was Christmas two days ago, I thought I’d write about a result which is sometimes called Fermat’s Christmas theorem, since Fermat first claimed to have proven in a letter dated to the 25th of December, 1640 (although, typically for Fermat, he didn’t actually give the proof, so he may not have had a correct proof). Recall that by Pythagoras’s theorem, the length of the hypotenuse of a right-angled triangle is related to the lengths and of the other two sides by the equation
Therefore, if and are integers, the square of is also an integer. Interestingly, however, there are non-negative integers which cannot be the square of if and are integers. For example, cannot be 3, because if or , then , and if and , . Let’s call the non-negative integers which can be the ‘2-square’ integers, because, just as the square integers are the integers such that if you have blocks, you can arrange all the blocks into exactly one square, the 2-square integers are the integers such that if you have blocks, you can arrange all the blocks into exactly two squares. In other words, the 2-square integers are exactly those equal to equal to for some pair of integers and .
There is an obvious method for finding out whether a given integer is 2-square. If is negative, it is definitely not 2-square, because square integers are never negative and sums of non-negative integers are never negative. Otherwise, whether is 2-square can be determined by simply testing each of the pairs of integers and such that and , of which there are only finitely many, and seeing whether . If there is at least one pair such that this is the case, then is 2-square, and if there are no pairs such that this is the case, then cannot be 2-square because for any pair of integers and where at least one of and is greater than , at least one of and is greater than , so . However, if is non-negative this method involves testing lots of different pairs of integers. It would be nice if there was a quicker method we could use in the case where is non-negative.
When you want to find out whether a non-negative integer is square, you can use a similar method, testing all the integers such that and seeing whether , but there is a quicker method which can be used when you know the prime factorisation of : is square if and only if the multiplicity of every prime in the prime factorisation of is even 1 (this method isn’t applicable when because only positive integers have prime factorisations, but it’s easy to see that 0 is square). Therefore, you might expect that if there is a quicker method for finding out whether is 2-square, it will also involve the prime factorisation of .
Let’s try just writing out the first 50 positive integers and identifying which of these are 2-square; maybe we will be able to see the pattern. We don’t need to worry about the negative integers and 0, because we already established that no negative integer is 2-square, and it is easy to see that 0 is 2-square (because it is equal to ). Since we already have a hunch that the prime factorisations will be involved, let’s write them as their prime factorisations. The bolded numbers are the 2-square numbers.
There isn’t a particularly obvious pattern here. We can see that every square integer is 2-square as well; this is because 0 is square and adding 0 to a square does not change it. Also, for every square integer , is 2-square, because . Notice that 2 is 2-square, because it is equal to . So this is actually a special case of a more general rule: for every 2-square number and every square integer , is 2-square as well, because there are integers , and such that and , so . You can see that this holds in the above list: and are 2-square because is 2-square, and are 2-square because 5 is 2-square, is 2-square because is 2-square, is 2-square because is 2-square, and is 2-square because is 2-square. The natural question to ask at this point is: does the converse hold? That is, if is not 2-square and is square, is not 2-square either? Well, obviously if is 0, will always be 0 which is 2-square, but does it hold if is positive? Let’s see if we can find a counterexample in the list above. 3 is not 2-square, and neither are , or . is not 2-square, and neither is . 7 is not 2-square, and neither is . 11 is not 2-square, and neither is . is not 2-square, and neither is . It certainly looks like the converse does hold. But it’s not obvious how this can be proven, since there’s not much you can do with a negative condition like ‘ is not 2-square’. For now, let’s just state it as a conjecture.
Conjecture 1. For every pair of integers and such that is not 2-square and is positive and square, is not 2-square.
If conjecture 1 does hold, then we can determine whether an integer is 2-square by dividing it by one of its positive square factors and seeing whether the result is 2-square (if it is 2-square, then so is , and if it is not 2-square, then neither is ). Therefore, we only need to be able to be able to determine whether the ‘square-free’ positive integers (those with no positive square factor other than 1) are 2-square. Let’s write out the list again, but omit all the non-square-free integers. Since the integers in the list are written as their prime factorisations, it is very easy to see which of them are square-free: the square-free integers are those whose prime factorisations do not contain multiple instances of any prime.
We’re getting closer to seeing the pattern, but it’s still not very obvious. However, notice that is 2-square, and so are its prime factors, 2 and 5. is 2-square, and 13 is also 2-square. is 2-square, and 17 is also 2-square. On the other hand, 3 is not 2-square, and all the square-free numbers which include it as a prime factor (, , , , and ) are not 2-square. 7 is not 2-square, and neither are and . 11 is not 2-square, and neither is . 19 is not 2-square, and neither is . 23 is not 2-square, and neither is . It looks like a square-free integer is 2-square if and only if all of its prime factors are 2-square.
Again, the ‘only if’ part will be difficult to prove since we are working with a negative condition. But let’s try and prove the ‘if’ part here, because in that case we do have something to work with. Now, whenever you want to prove something it’s always useful to try and identify exactly what you’re going to need to use in order to prove it. What we want to prove is that for every square-free positive integer whose prime factors are all 2-square, then is 2-square. But do we really need to use the fact that is square-free? We don’t, actually. The 2-square primes in the list are 2, 5, 13, 17, 29, 37 and 41, and sure enough, , , , , , , , , and are all 2-square, so it seems that even if is not square-free, it is still the case that if all its prime factors are 2-square, is 2-square as well. The fact that is square-free only needs to be used in the ‘only if’ part. In fact, we don’t even need to use the fact that the factors are prime, because the statement ‘every positive integer whose prime factors are all 2-square is 2-square’ is equivalent to the statement ‘for every pair of 2-square positive integers and , is 2-square’, assuming the ‘only if’ part holds. It’s obvious that the second statement implies the first, and to see that the first implies the second, just notice that if and are 2-square, so are all their prime factors (by the ‘only if’ part), and hence so are all the prime factors of (since each such factor is either a factor of or a factor of ). So, it should be possible to prove that is 2-square as long as and are both 2-square; no additional information should be needed.
If is 2-square, it can be written as where and are integers, and if is 2-square, it can be written as where and are integers. The product is then . Well, this is definitely a sum of four square integers. At this point it’s not totally obvious what to do, which is why it is useful to be sure that the proof can be carried out even if is not square-free or and are not both prime. You might just stumble across the method by which the proof is completed by trial and error, but a more illuminating way of completing the proof is to think, again, about what 2-square numbers are in geometric terms. They are the squares of hypotenuses of triangles whose other sides are of integral length. Equivalently, they are the squares of distances from the origin of points on the coordinate plane whose coordinates are integers. Equivalently, they are squares of norms of complex numbers whose real and imaginary parts are integers. Now, the norm operation on complex numbers respects multiplication, just as it does on real numbers: for every pair of complex numbers and , . If and , then , and hence the equation is equivalent to the equation
which shows how can be expressed as the sum of two square integers. And you can check, if you want, by expanding the brackets, that both sides of this equation are the same.
That takes care of the ‘if’ part; the ‘only if’ part is not yet proven, so let’s state it as our second conjecture.
Conjecture 2. For every square-free positive integer which is 2-square, every prime factor of is 2-square.
If conjecture 2 does hold, then we can determine whether a square-free positive integer is 2-square by seeing whether its prime factors are 2-square (if they are all 2-square, then so is , and if at least one is not 2-square, then neither is ). So let’s rewrite the list a final time, including only the prime numbers.
Do you see the pattern? Probably not at the moment, but there is one here. Recall that we can divide integers into two kinds, even integers and odd integers, according to their positions in the sequence of all integers, with the terms alternating between being even and being odd (for example, 0 is even, 1 is odd, 2 is even, 3 is odd, and so on). Now, apart from 2, all prime numbers are odd (because even integers are, by definition, divisible by 2). But we can do a similar thing with the sequence of all odd integers and divide all the odd integers into two kinds, which we can call ‘odd-even’ and ‘odd-odd’, according to their position in the sequence (for example, 1 is odd-even, 3 is odd-odd, 5 is odd-even, 7 is odd-odd, and so on). The more standard terms for ‘odd-even integers‘ and ‘odd-odd integers‘ are ‘integers congruent to 1 modulo 4‘ and ‘integers congruent to 3 modulo 4‘, respectively, because, just as even integers are those which are divisible by 2 and odd integers are those whose remainder upon division by 2 is 1, odd-even integers are those whose remainder upon division by 4 is 1 and odd-odd integers are those whose remainder upon division by 4 is 3, and in general we say that an integer is congruent to an integer modulo a positive integer (and write (mod ) if and only if the remainder of upon division by is . However, using this non-standard terminology makes it easy to see that this is quite a natural way to divide the prime numbers (other than 2) into two classes. Now, if you have a look at the list above, you’ll see that the 2-square integers in this list are exactly those which are odd-even (as well as 2), and the non-2-square integers in this list are exactly those which are odd-odd. It’s a lot easier to see this pattern if we make each line contain 8 numbers rather than 10.
It’s actually very easy to prove that the odd-odd integers in this list are not 2-square, if you are familiar with how congruences work. In fact, no odd-odd integer, whether prime or not, is 2-square. I’ll go through this proof in more detail than it really needs just in case you aren’t very familiar with congruences. First note that there are only 4 possible remainders upon division by 4, 0, 1, 2 and 3, so every integer is congruent to one of these integers modulo 4. Now, integers which are congruent can be regarded as the same up to a certain point. In particular, if (mod ) and (mod ) (where , , and are integers and is a positive integer), then (mod ) and (mod ). Therefore, for every integer , since one of , , and (mod 4) holds, one of , , and (mod 4) holds. But (mod 4) and (mod 4), and congruence is transitive (if (mod ) and (mod ), then (mod )), so in fact is always congruent to one of 0 and 1 modulo 4. As a result, every 2-square integer, since it can be written in the form , can only be congruent to one of 0 (), 1 () or 2 () modulo 4, never 3.
Proving that every odd-even prime number is 2-square is much more difficult. In fact, it was probably the chief obstacle Fermat faced in making his proof. However, Fermat did come up with a method, known as Fermat’s method of descent, which, once applied, makes the proof fairly straightforward (in fact, for this reason, we can be pretty sure Fermat really did prove the theorem, unlike some). The idea of Fermat’s method of descent, as applied to this problem in particular, is to prove two things, which together, imply that every odd-even prime number is 2-square.
- For every odd-even prime number , there is a multiple of which is 2-square.
- For every pair of integers and such that is 2-square and , there is an integer such that and is 2-square.
This works because for each odd-even prime number , we can find an integer such that is 2-square, by (1), and then we can find a smaller as many times as needed, using (2), until we get to . It is actually harder to prove (1) than (2), so we will begin by proving (2). Suppose and are integers, is 2-square and . Then , where and are integers. We want to find integers , and such that and . Due to equation 2, another 2-square integer which is a multiple of can be found by multiplying by another 2-square integer. If and are integers, then
Of course, if and are not both 0, , and if are both 0, , so either way we haven’t found a new integer such that . But if we choose and so that is divisible by , then will be divisible by . Therefore, if we can also get and to be divisible by , we can divide both sides of the above equation by to get
so, if we let , we have a sum of two squares which is equal to . And hopefully, if we choose and carefully, we can make it so that . That inequality can also be written as , i.e. (since ). We can therefore ensure that the inequality holds by making sure that both and are less than . But we can actually do better than that and make sure that both and are less than , by choosing values of and such that and . Since there are exactly values in this range, we can find values in this range which are congruent to every integer modulo . In particular, we can choose and so that they are in this range and and are congruent to and , respectively, modulo . Then and are congruent to modulo , so, since is divisible by , both and are divisible by . And is congruent to modulo , so, since 0 is divisible by , so is . And that completes the proof of (2). Note that this process allows us to find an actual pair of integers such that is the sum of their squares, if we have a sum of squares which is a multiple of to start of the process.
So how do we prove (1)? Well, it really is a lot harder to prove than (2). In fact, I’ve just done a course in number theory at the University of York, and we began the course by looking at the same problem I’m talking about in this post. All the work on the problem I’ve done so far in this post was covered in the first and last lectures. Pretty much the entire remainder of the course was about how to prove (1). That said, it could have been done more briefly, it’s just that (1) turns out to be a special case of a more general problem, which it is a natural to investigate at the same time. Recall what (1) states: it states that for every odd-even prime number , there are integers and such that is divisible by . That means that (mod ), so (mod ). Now, integers which are congruent to a square integer modulo are called quadratic residues modulo . So what we’re looking for is a pair of quadratic residues modulo which are each other’s negations. The natural thing to do, then, is to investigate which integers are quadratic residues modulo . This is a large topic, so that’s why it took most of the course to complete the proof. I’m not going to go into the full proof here, in order to prevent this post from becoming ridiculously long. But it turns out that is a quadratic residue modulo if and only if (mod 4). Therefore, if is odd-even, there is an integer such that (mod ), i.e. (mod ), i.e. is a multiple of . And that completes the proof of (1).
Now that we know which primes are 2-square, all that is left to do is to prove conjectures 1 and 2. Before we go ahead with that, we can state Fermat’s theorem on when a positive integer in general is 2-square.
Theorem 1 A positive integer is 2-square if and only if every prime number whose multiplicity in the prime factorisation of is odd is odd-even.
Proof: Suppose is a positive integer. For every prime number , let denote the multiplicity of in the prime factorisation of . Let be the product of all the prime numbers such that is odd. Then is square-free (because its prime factorisation does not contain multiple instances of any prime). Furthermore, is square (because the multiplicity of every prime number in its prime factorisation is if is even and if is odd, which is in either case even). Therefore, if is 2-square, is 2-square by conjecture 2, and hence every prime factor of is 2-square, i.e. odd-even, by conjecture 1. On the other hand, if every prime factor of is odd-even, i.e. 2-square, then , as the product of all these prime numbers, is 2-square, and hence is 2-square since is square.
We will prove both conjectures at once by showing that if is a 2-square positive integer, then every prime number whose multiplicity in the prime factorisation of is odd is odd-even. The proof uses, again, the fact that is a quadratic residue modulo if and only if (mod ).
Proof: Suppose is a 2-square positive integer, so that where and are integers. Let be the greatest common divisor of and , so there are coprime integers and such that and . Then
Suppose is a prime number and the multiplicity of in the prime factorisation of is odd. This multiplicity is the sum of its multiplicities in the prime factorisations of and , respectively. Since is square, the former multiplicity is even; therefore, since is odd, the latter multiplicity must be odd, from which we can conclude that it is not 0. In other words, is divisible by . That means (mod ), so (mod ). Now, we can show that neither nor is divisible by . First of all, since and are coprime, at least one of them must not be divisible by . If , then , so (mod ), hence (mod ) which means (mod ), so . If , then , so (mod ), hence (mod ) which means (mod ), so . So if one of them is divisible by , the other one is as well, and it follows that neither can be divisible by . What can we do with this information? Well, one of the basic results in number theory states that if an integer is not divisible by a prime , there is another integer such that (mod ), just like how . So there are integers and such that (mod ) and (mod ). So we can take the congruence and multiply both sides by , giving (mod ), i.e. (mod ), i.e. (mod ). Therefore, is a quadratic residue modulo , and that means (mod 4), so is 2-square.
So, we have, at last, found the solution to the problem. The 2-square integers are those with prime factorisations in which every prime number with even multiplicity is odd-even (i.e. congruent to 1 modulo 4).
I’ll leave you with this to think about. We can generalise the idea of a 2-square integer and define an integer to be ‘-square’ (where is a positive integer) if and only if it can be expressed as a sum of exactly squares. Now that we know which integers are 1-square and 2-square, it’s natural to wonder which integers are 3-square, 4-square, 5-square and so on. If this post has interested you (and it probably has if you’ve got this far), I encourage you to try and investigate which integers are 4-square yourself using the same sort of method I used in this post. You’ll find that the pattern for 4-square integers is pretty easy to spot.
- ^ The multiplicity of a prime number in the prime factorisation of a positive integer is defined as the greatest integer such that is divisible by . If you think of the prime factorisation of as a bag (a set which can contain multiple elements) of prime numbers, the multiplicity of each prime number in the prime factorisation of can be thought of the number of instances of which the bag contains. If we write as its prime factorisation , then for every positive integer such that , is the multiplicity of in the prime factorisation of .