Fermat’s Christmas theorem

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 {c} of the hypotenuse of a right-angled triangle is related to the lengths {a} and {b} of the other two sides by the equation

\displaystyle   c^2 = a^2 + b^2. \ \ \ \ \ (1)

Therefore, if {a} and {b} are integers, the square of {c} is also an integer. Interestingly, however, there are non-negative integers which cannot be the square of {c} if {a} and {b} are integers. For example, {c^2} cannot be 3, because if {a \ge 2} or {b \ge 2}, then {a^2 + b^2 \ge 2^2 = 4}, and if {a \le 1} and {b \le 1}, {a^2 + b^2 \le 1^2 + 1^2 = 2}. Let’s call the non-negative integers which {c^2} can be the ‘2-square’ integers, because, just as the square integers are the integers {n} such that if you have {n} blocks, you can arrange all the blocks into exactly one square, the 2-square integers are the integers {n} such that if you have {n} 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 {a^2 + b^2} for some pair of integers {a} and {b}.

There is an obvious method for finding out whether a given integer {n} is 2-square. If {n} 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 {n} is 2-square can be determined by simply testing each of the pairs of integers {a} and {b} such that {a \le \sqrt n} and {b \le \sqrt n}, of which there are only finitely many, and seeing whether {a^2 + b^2 = n}. If there is at least one pair such that this is the case, then {n} is 2-square, and if there are no pairs such that this is the case, then {n} cannot be 2-square because for any pair of integers {a} and {b} where at least one of {a} and {b} is greater than {\sqrt n}, at least one of {a^2} and {b^2} is greater than {n}, so {a^2 + b^2 > n}. However, if {n} 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 {n} is non-negative.

When you want to find out whether a non-negative integer {n} is square, you can use a similar method, testing all the integers {a} such that {a \le n} and seeing whether {a^2 = n}, but there is a quicker method which can be used when you know the prime factorisation of {n}: {n} is square if and only if the multiplicity of every prime in the prime factorisation of {n} is even 1 (this method isn’t applicable when {n = 0} 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 {n} is 2-square, it will also involve the prime factorisation of {n}.

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 {0 + 0}). 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.

\displaystyle \begin{matrix} \mathbf{1} & \mathbf{2} & 3 & \mathbf{2^2} & \mathbf{5} & 2 \cdot 3 & 7 & \mathbf{2^3} & \mathbf{3^2} & \mathbf{2 \cdot 5} \\ 11 & 2^2 \cdot 3 & \mathbf{13} & 2 \cdot 7 & 3 \cdot 5 & \mathbf{2^4} & \mathbf{17} & \mathbf{2 \cdot 3^2} & 19 & \mathbf{2^2 \cdot 5} \\ 3 \cdot 7 & 2 \cdot 11 & 23 & 2^3 \cdot 3 & \mathbf{5^2} & \mathbf{2 \cdot 13} & 3^3 & 2^2 \cdot 7 & \mathbf{29} & 2 \cdot 3 \cdot 5 \\ 31 & \mathbf{2^5} & 3 \cdot 11 & \mathbf{2 \cdot 17} & 5 \cdot 7 & \mathbf{2^2 \cdot 3^2} & \mathbf{37} & 2 \cdot 19 & 39 & \mathbf{2^3 \cdot 5} \\ \mathbf{41} & 2 \cdot 3 \cdot 7 & 43 & 2^2 \cdot 11 & \mathbf{3^2 \cdot 5} & 2 \cdot 23 & 47 & 2^4 \cdot 3 & \mathbf{7^2} & \mathbf{2 \cdot 5^2} \end{matrix}

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 {n}, {2 n} is 2-square, because {2 n = n + n}. Notice that 2 is 2-square, because it is equal to {1 + 1}. So this is actually a special case of a more general rule: for every 2-square number {m} and every square integer {n}, {m n} is 2-square as well, because there are integers {x}, {y} and {z} such that {m = x^2 + y^2} and {n = z^2}, so {m n = (x^2 + y^2) z^2 = x^2 z^2 + y^2 z^2 = (x z)^2 + (y z)^2}. You can see that this holds in the above list: {2^4} and {2^2 \cdot 3^2} are 2-square because {2^2} is 2-square, {2^2 \cdot 5} and {3^2 \cdot 5} are 2-square because 5 is 2-square, {2^5} is 2-square because {2^3} is 2-square, {2^2 \cdot 3^2} is 2-square because {3^2} is 2-square, and {2^3 \cdot 5} is 2-square because {2 \cdot 5} is 2-square. The natural question to ask at this point is: does the converse hold? That is, if {m} is not 2-square and {n} is square, is {m n} not 2-square either? Well, obviously if {n} is 0, {m n} will always be 0 which is 2-square, but does it hold if {n} is positive? Let’s see if we can find a counterexample in the list above. 3 is not 2-square, and neither are {2^2 \cdot 3}, {3^3} or {2^4 \cdot 3}. {2 \cdot 3} is not 2-square, and neither is {2^3 \cdot 3}. 7 is not 2-square, and neither is {2^2 \cdot 7}. 11 is not 2-square, and neither is {2^2 \cdot 11}. {2^2 \cdot 3} is not 2-square, and neither is {2^4 \cdot 3}. 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 ‘{m} is not 2-square’. For now, let’s just state it as a conjecture.

Conjecture 1. For every pair of integers {m} and {n} such that {m} is not 2-square and {n} is positive and square, {m n} is not 2-square.

If conjecture 1 does hold, then we can determine whether an integer {n} 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 {n}, and if it is not 2-square, then neither is {n}). 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.

\displaystyle \begin{matrix} \mathbf{1} & \mathbf{2} & 3 & & \mathbf{5} & 2 \cdot 3 & 7 & & & \mathbf{2 \cdot 5} \\ 11 & & \mathbf{13} & 2 \cdot 7 & 3 \cdot 5 & & \mathbf{17} & & 19 & \\ 3 \cdot 7 & 2 \cdot 11 & 23 & & & \mathbf{2 \cdot 13} & & & \mathbf{29} & 2 \cdot 3 \cdot 5 \\ 31 & & 3 \cdot 11 & \mathbf{2 \cdot 17} & 5 \cdot 7 & & \mathbf{37} & 2 \cdot 19 & 39 & \\ \mathbf{41} & 2 \cdot 3 \cdot 7 & 43 & 2 \cdot 23 & & & 47 & & & \end{matrix}

We’re getting closer to seeing the pattern, but it’s still not very obvious. However, notice that {2 \cdot 5} is 2-square, and so are its prime factors, 2 and 5. {2 \cdot 13} is 2-square, and 13 is also 2-square. {2 \cdot 17} 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 ({2 \cdot 3}, {3 \cdot 5}, {3 \cdot 7}, {2 \cdot 3 \cdot 5}, {3 \cdot 11} and {2 \cdot 3 \cdot 7}) are not 2-square. 7 is not 2-square, and neither are {2 \cdot 7} and {5 \cdot 7}. 11 is not 2-square, and neither is {2 \cdot 11}. 19 is not 2-square, and neither is {2 \cdot 19}. 23 is not 2-square, and neither is {2 \cdot 23}. 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 {n} whose prime factors are all 2-square, then {n} is 2-square. But do we really need to use the fact that {n} 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, {2^2}, {2^3}, {2^4}, {2^2 \cdot 5}, {5^2}, {2^5}, {2 \cdot 17}, {2^3 \cdot 5}, {3^2 \cdot 5} and {2 \cdot 5^2} are all 2-square, so it seems that even if {n} is not square-free, it is still the case that if all its prime factors are 2-square, {n} is 2-square as well. The fact that {n} 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 {n} whose prime factors are all 2-square is 2-square’ is equivalent to the statement ‘for every pair of 2-square positive integers {a} and {b}, {a b} 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 {a} and {b} are 2-square, so are all their prime factors (by the ‘only if’ part), and hence so are all the prime factors of {a b} (since each such factor is either a factor of {a} or a factor of {b}). So, it should be possible to prove that {a b} is 2-square as long as {a} and {b} are both 2-square; no additional information should be needed.

If {a} is 2-square, it can be written as {x^2 + y^2} where {x} and {y} are integers, and if {b} is 2-square, it can be written as {x^2 + z^2} where {w} and {z} are integers. The product {a b} is then {(x^2 + y^2) (u^2 + v^2) = x^2 u^2 + x^2 v^2 + y^2 u^2 + y^2 v^2 = (x u)^2 + (x v)^2 + (y u)^2 + (y v)^2}. 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 {a b} is not square-free or {a} and {b} 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 {a} and {b}, {|a b| = |a| |b|}. If {a = x + y i} and {b = u + v i}, then {a b = (x u - y v) + (x v - y u) i}, and hence the equation {|a b| = |a| |b|} is equivalent to the equation

\displaystyle   (x u + y v)^2 + (x v - y u)^2 = \left( x^2 + y^2 \right) \left( u^2 + v^2 \right), \ \ \ \ \ (2)

which shows how {(x^2 + y^2) (u^2 + v^2)} 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 {n} which is 2-square, every prime factor of {n} is 2-square.

If conjecture 2 does hold, then we can determine whether a square-free positive integer {n} is 2-square by seeing whether its prime factors are 2-square (if they are all 2-square, then so is {n}, and if at least one is not 2-square, then neither is {n}). So let’s rewrite the list a final time, including only the prime numbers.

\displaystyle \begin{matrix} & \mathbf{2} & 3 & & \mathbf{5} & & 7 & & & \\ 11 & & \mathbf{13} & & & & \mathbf{17} & & 19 & \\ & & 23 & & & & & & \mathbf{29} & \\ 31 & & & & & & \mathbf{37} & & 39 & \\ \mathbf{41} & & 43 & & & & 47 & & & \end{matrix}

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 {a} is congruent to an integer {b} modulo a positive integer {m} (and write {a \equiv b} (mod {m}) if and only if the remainder of {a} upon division by {m} is {b}. 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.

\displaystyle \begin{matrix} & \mathbf{2} & 3 & & \mathbf{5} & & 7 & \\ & & 11 & & \mathbf{13} & & & \\ \mathbf{17} & & 19 & & & & 23 & \\ & & & & \mathbf{29} & & 31 & \\ & & & & \mathbf{37} & & 39 & \\ \mathbf{41} & & 43 & & & & 47 & \\ \end{matrix}

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 {a \equiv b} (mod {m}) and {c \equiv d} (mod {m}) (where {a}, {b}, {c} and {d} are integers and {m} is a positive integer), then {a + c \equiv b + d} (mod {m}) and {a c \equiv b d} (mod {m}). Therefore, for every integer {n}, since one of {n \equiv 0}, {n \equiv 1}, {n \equiv 2} and {n \equiv 3} (mod 4) holds, one of {n^2 \equiv 0}, {n^2 \equiv 1}, {n^2 \equiv 4} and {n^2 \equiv 9} (mod 4) holds. But {4 \equiv 0} (mod 4) and {9 \equiv 1} (mod 4), and congruence is transitive (if {a \equiv b} (mod {m}) and {b \equiv c} (mod {m}), then {a \equiv c} (mod {m})), so in fact {n^2} 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 {x^2 + y^2}, can only be congruent to one of 0 ({0 + 0}), 1 ({0 + 1}) or 2 ({1 + 1}) 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.

  1. For every odd-even prime number {p}, there is a multiple of {p} which is 2-square.
  2. For every pair of integers {n} and {k} such that {k n} is 2-square and {1 < k}, there is an integer {k'} such that {0 < k' < k} and {k' n} is 2-square.

This works because for each odd-even prime number {p}, we can find an integer {k} such that {k p} is 2-square, by (1), and then we can find a smaller {k} as many times as needed, using (2), until we get to {k = 1}. It is actually harder to prove (1) than (2), so we will begin by proving (2). Suppose {n} and {k} are integers, {k n} is 2-square and {1 < k}. Then {k n = x^2 + y^2}, where {x} and {y} are integers. We want to find integers {k'}, {x'} and {y'} such that {k n' = (x')^2 + (y')^2} and {0 < k' < k}. Due to equation 2, another 2-square integer which is a multiple of {n} can be found by multiplying {x^2 + y^2} by another 2-square integer. If {u} and {v} are integers, then

\displaystyle \left( x^2 + y^2 \right) \left( u^2 + v^2 \right) = (x u + y v)^2 + (x v - y u)^2

Of course, if {u^2} and {v^2} are not both 0, {k \le k (u^2 + v^2)}, and if {u^2 + v^2} are both 0, {k (u^2 + v^2) = 0}, so either way we haven’t found a new integer {k'} such that {0 < k' < k}. But if we choose {u} and {v} so that {u^2 + v^2} is divisible by {k}, then {(x^2 + y^2) (u^2 + v^2)} will be divisible by {k^2}. Therefore, if we can also get {x u + y v} and {x v - y u} to be divisible by {k}, we can divide both sides of the above equation by {k^2} to get

\displaystyle n \frac {u^2 + v^2} k = \left( \frac {x u + y v} k \right)^2 + \left( \frac {x v - y u} k \right)^2,

so, if we let {k' = (u^2 + v^2)/k}, we have a sum of two squares which is equal to {k' n}. And hopefully, if we choose {u} and {v} carefully, we can make it so that {0 < k' < k}. That inequality can also be written as {0 < (u^2 + v^2)/k < k}, i.e. {0 < u^2 + v^2 < k^2} (since {1 < k}). We can therefore ensure that the inequality holds by making sure that both {u^2} and {v^2} are less than {k^2/2}. But we can actually do better than that and make sure that both {u^2} and {v^2} are less than {k^2/4}, by choosing values of {u} and {v} such that {-k/2 < u \le k/2} and {-k/2 < v \le k/2}. Since there are exactly {k} values in this range, we can find values in this range which are congruent to every integer modulo {k}. In particular, we can choose {u} and {v} so that they are in this range and {u} and {v} are congruent to {x} and {y}, respectively, modulo {k}. Then {u^2 + v^2} and {x u + y v} are congruent to {x^2 + y^2} modulo {k}, so, since {x^2 + y^2} is divisible by {k}, both {u^2 + v^2} and {x u + y v} are divisible by {k}. And {x v - y u} is congruent to {x y - y x = 0} modulo {k}, so, since 0 is divisible by {k}, so is {x v - y u}. And that completes the proof of (2). Note that this process allows us to find an actual pair of integers such that {n} is the sum of their squares, if we have a sum of squares which is a multiple of {n} 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 {p}, there are integers {x} and {y} such that {x^2 + y^2} is divisible by {p}. That means that {x^2 + y^2 \equiv 0} (mod {p}), so {x^2 \equiv -y^2} (mod {p}). Now, integers which are congruent to a square integer modulo {p} are called quadratic residues modulo {p}. So what we’re looking for is a pair of quadratic residues modulo {p} which are each other’s negations. The natural thing to do, then, is to investigate which integers are quadratic residues modulo {p}. 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 {-1} is a quadratic residue modulo {p} if and only if {p \equiv 1} (mod 4). Therefore, if {p} is odd-even, there is an integer {x} such that {x^2 \equiv -1} (mod {p}), i.e. {x^2 + 1 \equiv 0} (mod {p}), i.e. {x^2 + 1} is a multiple of {p}. 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 {n} is 2-square if and only if every prime number whose multiplicity in the prime factorisation of {n} is odd is odd-even.

Proof: Suppose {n} is a positive integer. For every prime number {p}, let {\alpha(p)} denote the multiplicity of {p} in the prime factorisation of {n}. Let {s} be the product of all the prime numbers {p} such that {\alpha(p)} is odd. Then {s} is square-free (because its prime factorisation does not contain multiple instances of any prime). Furthermore, {n / s} is square (because the multiplicity of every prime number {p} in its prime factorisation is {\alpha(p)} if {\alpha(p)} is even and {\alpha(p) - 1} if {\alpha(p)} is odd, which is in either case even). Therefore, if {n} is 2-square, {s} is 2-square by conjecture 2, and hence every prime factor of {s} is 2-square, i.e. odd-even, by conjecture 1. On the other hand, if every prime factor of {s} is odd-even, i.e. 2-square, then {s}, as the product of all these prime numbers, is 2-square, and hence {n} is 2-square since {n / s} is square. \Box

We will prove both conjectures at once by showing that if {n} is a 2-square positive integer, then every prime number whose multiplicity in the prime factorisation of {n} is odd is odd-even. The proof uses, again, the fact that {-1} is a quadratic residue modulo {p} if and only if {p \equiv 1} (mod {p}).

Proof: Suppose {n} is a 2-square positive integer, so that {n = x^2 + y^2} where {x} and {y} are integers. Let {d} be the greatest common divisor of {x} and {y}, so there are coprime integers {x'} and {y'} such that {x = d x'} and {y = d y'}. Then

\displaystyle n = (d x')^2 + (d y')^2 = d^2 \left( (x')^2 + (y')^2 \right).

Suppose {p} is a prime number and the multiplicity {\alpha} of {p} in the prime factorisation of {n} is odd. This multiplicity is the sum of its multiplicities in the prime factorisations of {d^2} and {(x')^2 + (y')^2}, respectively. Since {d^2} is square, the former multiplicity is even; therefore, since {\alpha} is odd, the latter multiplicity must be odd, from which we can conclude that it is not 0. In other words, {(x')^2 + (y')^2} is divisible by {p}. That means {(x')^2 + (y')^2 \equiv 0} (mod {p}), so {(x')^2 \equiv -(y')^2} (mod {p}). Now, we can show that neither {x'} nor {y'} is divisible by {p}. First of all, since {x'} and {y'} are coprime, at least one of them must not be divisible by {p}. If {p \mid x'}, then {p \mid (x')^2}, so {(x')^2 \equiv 0} (mod {p}), hence {(y')^2 \equiv 0} (mod {p}) which means {y' \equiv 0} (mod {p}), so {p \mid y'}. If {p \mid y'}, then {p \mid (y')^2}, so {(y')^2 \equiv 0} (mod {p}), hence {(x')^2 \equiv 0} (mod {p}) which means {x' \equiv 0} (mod {p}), so {p \mid x'}. So if one of them is divisible by {p}, the other one is as well, and it follows that neither can be divisible by {p}. What can we do with this information? Well, one of the basic results in number theory states that if an integer {a} is not divisible by a prime {p}, there is another integer {b} such that {a b \equiv 1} (mod {p}), just like how {a (1 / a) = 1}. So there are integers {u} and {v} such that {x' u \equiv 1} (mod {p}) and {y' v \equiv 1} (mod {p}). So we can take the congruence {(x')^2 \equiv -(y')^2} and multiply both sides by {v^2}, giving {(x')^2 v^2 \equiv -(y')^2 v^2} (mod {p}), i.e. {(x' v)^2 \equiv -(y' v)^2} (mod {p}), i.e. {(x' v)^2 \equiv -1} (mod {p}). Therefore, {-1} is a quadratic residue modulo {p}, and that means {p \equiv 1} (mod 4), so {p} is 2-square. \Box

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 ‘{k}-square’ (where {k} is a positive integer) if and only if it can be expressed as a sum of exactly {k} 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.

Footnotes

  1. ^ The multiplicity of a prime number {p} in the prime factorisation of a positive integer {n} is defined as the greatest integer {\alpha} such that {n} is divisible by {p^{\alpha}}. If you think of the prime factorisation of {n} as a bag (a set which can contain multiple elements) of prime numbers, the multiplicity of each prime number {p} in the prime factorisation of {n} can be thought of the number of instances of {p} which the bag contains. If we write {n} as its prime factorisation {p_1^{\alpha_1} p_2^{\alpha_2} \dotsm p_k^{\alpha_k}}, then for every positive integer {i} such that {i \le k}, {\alpha_i} is the multiplicity of {p_i} in the prime factorisation of {n}.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s