Tag Archives: primes

Large and small sets

For some infinite sets {S = \{x_1, x_2, x_3, \dotsc\}} of positive integers, the sum of the reciprocals of the members of {S}, i.e.

\displaystyle \frac 1 {x_1} + \frac 1 {x_2} + \frac 1 {x_3} + \dotsb,

diverges. Such sets are said to be large. For example, {\mathbb N}, the set of all the positive integers, is large, because the harmonic series diverges. On the other hand, for some infinite sets {S} the sum of the reciprocals of the members of {S} converges instead; such sets are said to be small. For example, for every integer {p} greater than 1, the set of all the positive integral {p}th powers is small, because the series

\displaystyle 1 + \frac 1 {2^p} + \frac 1 {3^p} + \dotsb

converges. There is thus an interesting distinction between two different sizes of infinite sets of positive integers. Let’s have a look at some other infinite sets of positive integers and see whether they are large or small.

For every positive integer {m}, the set of all the positive integral multiples of {m} is easily seen to be large, due to the fact that the harmonic series diverges, and dividing the harmonic series by {m} yields the series

\displaystyle \frac 1 m + \frac 1 {2 m} + \frac 1 {3 m} + \dotsb.

In fact, this proof can easily be generalised to show that for every set {S} of positive integers and every positive integer {m}, {\{m n : n \in S\}} is large if and only if {S} is large.

What about the set {S} of all the positive integers which are not multiples of {m}? The sum of the reciprocals of the members of {S} can be written as the difference

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) - \left( \frac 1 m + \frac 1 {2 m} + \frac 1 {3 m} + \dotsb \right).

The minuend and subtrahend of this difference are both equal to {\infty}, so the sum of the reciprocals of the members of {S} cannot be immediately seen from writing it like this. However, if we take out the factor of {1 / m} from the subtrahend, we get

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) - \frac 1 m \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right),

and then we can remove the common factor of {1 + 1 / 2 + 1 / 3 + \dotsb} to get

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) \left( 1 - \frac 1 m \right).

It is easy to see that the value of this expression is also {\infty}. So {S} is large, as well.

In fact, for every finite set of pairwise coprime positive integers {p_1}, {p_2}, … and {p_{\ell}}, the set {S} of all the positive integers which are not multiples of any of these integers is large, too. This is because, if we let {H} be the value of the harmonic series, then, using the inclusion-exclusion principle, the sum of the reciprocals of the members of {S} can be written as

\displaystyle H - \sum_{k} \frac H k + \sum_{k_1, k_2} \frac H {k_1 k_2} - \dotsb + \frac {(-1)^{\ell} H} {k_1 k_2 \dotsm k_{\ell}},

in which, for every integer j such that 1 \le j \le \ell, the jth term is a sum over all the finite sets of j integers k such that 1 \le k \le \ell. By factorising this expression, we can rewrite it as

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_{\ell}} \right),

and it is easy to see that the value of this expression is {\infty}.

Generalising from this, one might expect that if we let {P = \{p_1, p_2, p_3, \dotsc\}} be the prime numbers, so that the members of {P} are pairwise coprime and every integer is a multiple of a member of {P}, then

\displaystyle   H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \left( 1 - \frac 1 {p_3} \right) \dotsm = 1. \ \ \ \ \ (1)

To prove this rigorously, all that is needed is to note that for every positive integer {n},

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_n} \right) = 1 + K,

where {K} is the sum of the reciprocals of the integers greater than 1 which are not multiples of any of the first {n} prime numbers. The least such integer is {p_{n + 1}}, so {K} is smaller than the sum of the reciprocals of the integers greater than or equal to {p_{n + 1}}. Therefore,

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_n} \right) < 1 + \frac 1 {p_{n + 1}} + \frac 1 {p_{n + 1} + 1} + \frac 1 {p_{n + 1} + 2} + \dotsb.

As {n} tends towards positive infinity, the sum of the reciprocals of the integers greater than or equal to {p_{n + 1}} tends towards 0, because it can be written as {H - H_{p_{n + 1} - 1}}, which is less than {H - H_n}, and by definition {H_n} tends towards {H} as {n} tends towards positive infinity. So the right-hand side of the inequality above tends towards 1, and an application of the squeeze theorem completes the proof.

Rearranging (1) to solve for {H} yields

\displaystyle H = \left( \frac 1 {1 - 1 / p_1} \right) \left( \frac 1 {1 - 1 / p_2} \right) \left( \frac 1 {1 - 1 / p_3} \right) \dotsm,

so we now have a way of expressing the harmonic series as an infinite product. This is quite interesting in its own right, but it can also be used to prove a rather surprising result. By taking the natural logarithm of both sides, we see that

\displaystyle \ln H = \ln \left( \frac 1 {1 - 1 / p_1} \right) + \ln \left( \frac 1 {1 - 1 / p_2} \right) + \ln \left( \frac 1 {1 - 1 / p_3} \right) + \dotsb.

The natural logarithm of {\infty} is {\infty}, so this means the series on the right-hand side diverges. For every positive integer {n}, the {n}th term of the series on the right-hand side, {\ln (1 / (1 - 1 / p_n))}, can also be written as {\ln (1 + 1 / (p_n - 1))}, and this number is less than or equal to {1 / (p_n - 1)} (in general, for every real number {x} greater than {-1}, {\ln (1 + x) \le x}). If {n} is greater than 1, then this number, in turn, is less than or equal to {1 / p_{n - 1}}, because {p_n - 1} is greater than or equal to {p_{n - 1}}. And {1 / (2 - 1)}, i.e. 1, is less than or equal to 1. So, by the comparison test, the series

\displaystyle 1 + \frac 1 {p_1} + \frac 1 {p_2} + \frac 1 {p_3} + \dotsb

diverges, too. This shows that the set consisting of 1 as well as all the prime numbers is large, but it is then an immediate consequence that the set of all the prime numbers, not including 1, is large (since we can subtract 1 from the above series and the value of the result will still have to be {\infty}).

This is a rather interesting and surprising result. The set of all the prime numbers is large, but for every positive integer {p}, the set of all the positive integral {p}th powers is small, which means that, in a certain sense, there are more prime numbers than positive integral {p}th powers.

Advertisements

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}.

The definition of a prime number

The standard definition of a prime number is an integer greater than 1 which is only divisible by itself and 1. While this definition is the simplest to state and often the easiest to work with, it’s not very motivated. And it has the pecularity that a prime number is required to be greater than 1. Why is this complication in the definition?

Obviously, the requirement is just a convention—and one which wasn’t even followed until the 20th century; many 19th-century mathematicians called 1 a prime number—but the convention does make quite a lot of sense. I hadn’t realised until recently just how much sense it made. The explanation I’d always heard was the same one given in Hardy & Wright’s Introduction to the Theory of Numbers. Using the standard definition, it is a theorem that every positive integer n is the product of a finite sequence of prime numbers (p_1, \dotsc, p_k) which is unique up to a permutation (i.e. every finite sequence of primes whose product is n is a permutation of (p_1, \dotsc, p_k)). But if 1 was considered a prime number, n would also be the product of every finite sequence obtained by inserting any number of terms equal to 1 into (p_1, \dotsc, p_k), so the theorem as stated would not be true. Of course, we could fix this by saying “unique up to a permutation or having any number of terms equal to 1 inserted or removed” rather than “unique up to a permutation”. Since the uniqueness is already qualified in the statement of the theorem, it doesn’t seem like a strong argument against the definition that another qualification would have to be added.

Even though 1 is not a prime, nobody has ever argued that 1 should be called composite. This is because with 1 not considered composite, the definition of a composite number is simple and clearly motivated: a composite number is a positive integer which is the product of a pair of smaller positive integers (we might call such a pair a decomposition of the composite number). The motivation for this definition is that smaller numbers may be easier to work with than the original, larger number. Clearly, 1 is not composite by this definition since it has no smaller factors.

Every composite factor in the decomposition of a composite number can be decomposed itself, and the same thing can be done with the composite factors in the resulting decomposition. Since there is only a finite number of positive integers smaller than each positive integer, there will always eventually be no composite factors left in the decomposition, so every composite number can be decomposed into non-composite factors. Now I can state my favourite definition of a prime number: a prime number is a non-composite number that is present in a decomposition of a composite number. Or in other words, prime numbers are the fundamental factors which all composite numbers are built out of. In fact, all numbers can be regarded as being built out of prime numbers, since each prime number is the product of a sequence whose only term is itself, and 1 is the product of the empty sequence, which is vacuously a sequence of prime numbers. It’s therefore very clear from this definition why primes are interesting. And it’s also clear that 1 is not a prime, because if 1 were present in the decomposition of a composite number n, the other number in the decomposition would have to be n, which isn’t smaller than n! Think of it this way: a prime is a non-composite number which you can divide a composite number by to make it smaller. But dividing by 1 wouldn’t make it smaller.

Hopefully, that explanation makes the requirement that prime numbers are not 1 make more sense to you. It worked for me, at least!

The harmonic series

The harmonic series is the expression

1 + \frac 1 2 + \frac 1 3 + \frac 1 4 + \dotsb,

whose value is an infinite sum. Since the terms in the series become arbitrarily small as one goes further in (since for every positive real number \varepsilon and every positive integer n greater than \lceil \frac 1 \varepsilon \rceil, the nth term is smaller than \varepsilon), one might expect the series to converge a finite value, but this is not the case—its value is actually infinite. Having terms which become arbitrarily small eventually is a necessary, but not sufficient, property of convergent series, and the harmonic series is the usual example brought up to show that this property is not sufficient.

Proving that the value of the harmonic series is infinite can be done easily, but not in an obvious manner. It involves grouping the terms in a clever manner so that the series can be seen to have the same value as one which obviously diverges to infinity. \frac 1 2 on its own makes up the first group. The next group contains \frac 1 3 and \frac 1 4. The next group contains 4 terms, \frac 1 5, \frac 1 6, \frac 1 7 and \frac 1 8. It continues on in the same way, with each group containing twice as many terms as the last group, so that the last terms in each group are the powers of two. The first term, 1, is outside of this sequence, so it can be considered not part of any group.

Now, consider the series obtained by replacing every term with the power of two that is the final one in its group. This series will look like this:

1 + \frac 1 2 + \frac 1 4 + \frac 1 4 + \frac 1 8 + \frac 1 8 + \frac 1 8 + \frac 1 8 + \dotsb

None of the terms have been increased in size by this replacement—they have only gotten smaller if they changed at all. Therefore, if we can show that the sum of this new series is infinite, the sum of the harmonic series, since it must be larger, must also be infinite. To see that the sum of the new series is infinite, just add up the terms in each group. The first group just contains \frac 1 2. The second group contains 2 instances of \frac 1 4; these add up to \frac 1 2. The third group contains 4 instances of \frac 1 8; these add up to \frac 1 2 as well. Clearly, every single group adds up to \frac 1 2, so the series is the same as the following one:

1 + \frac 1 2 + \frac 1 2 + \frac 1 2 + \dotsb

which is obviously infinite. This completes the proof that the value of the harmonic series is infinite.

A similar strategy can be used to examine all the series of the form

1 + \frac 1 {2^p} + \frac 1 {3^p} + \frac 1 {4^p} + \dotsb

where p is an arbitrary real number. Clearly if p < 1, every term in this series will be greater than the corresponding term in the harmonic series, so its value must be infinite since it has to be larger than the value of the harmonic series. So the only interesting case is where 1 < p.

If you try grouping the terms in the exact same way here, you’ll find that the first group will add up to \frac 1 {2^p}, the second will add up to \frac 2 {4^p} = \frac 1 {2^{2 p - 1}}, the third will add up to \frac 4 {8^p} = \frac 1 {2^{4 p - 1}}, and so on. If 1 < p, all these quantities are different; in fact, they are getting smaller and smaller. This suggests that possibly, the series doesn’t diverge at all—maybe it converges now instead.

In order to find out whether it converges, we just have to change how we group the terms slightly: we’ll shift them to the left by one term, so that 1 comprises the first group, \frac 1 {2^p} and \frac 1 {3^p} comprise the second group, and so on. Now rather than ending with a power of two, each group begins with a power of two. We will still replace the terms in each group with the power of two in the group, so that each term which changes gets replaced by a larger term. This gives a new series that looks like

1 + \frac 1 {2^p} + \frac 1 {2^p} + \frac 1 {4^p} + \frac 1 {4^p} + \frac 1 {4^p} + \frac 1 {4^p} + \dotsb.

The sum of this new series must be larger than the sum of the old one. So if we can prove that the new series has a finite sum, that would mean the old series couldn’t have an infinite sum. In fact, since all the terms in the old series are positive, it would imply something slightly stronger, that the old series must converge to a finite sum (the possibility that the old series has no defined sum at all would be ruled out). I’ll explain how this leap of logic can be made in a later post, since the reasoning required for it is slightly more complex than what’s required for most of the content in this post.

We can, indeed, prove that this new series converges. Let’s add up the terms in each group again. The first group is just 1. The second group has 2 instances of \frac 1 {2^p}, which add up to \frac 2 {2^p} = \frac 1 {2^{p - 1}}. The third group has 4 instances of \frac 1 {4^p}, which add up to \frac 4 {4^p} = \frac 1 {4^{p - 1}}. So the resulting series looks like

1 + \frac 1 {2^{p - 1}} + \frac 1 {4^{p - 1}} + \frac 1 {8^{p - 1}} + \dotsb,

which can also be written as

1 + 2^{1 - p} + (2^{1 - p})^2 + (2^{1 - p})^2 + \dotsb

Perhaps you can see why I’ve written the series in this way: it’s just a geometric series with the common ratio 2^{1 - p}! Since 1 < p so 1 - p < 0, 2^{1 - p} < 1, so this series has a finite value equal to \frac 1 {1 - 2^{1 - p}}. So now we can conclude that the original series has a finite value no greater than \frac 1 {1 - 2^{1 - p}}, which can also be written as \frac {2^{p - 1}} {2^{p - 1} - 1}, if we multiply the top and bottom of the fraction by 2^{p - 1}.

Oh, and I almost forgot to say: what, then, is the finite value of

1 + \frac 1 {2^p} + \frac 1 {3^p} + \frac 1 {4^p} + \dotsb

then? This is a considerably harder question to answer. In fact, there isn’t really any way to express the value in a simpler manner than the above series. However, there is a fairly easy way to show that the series can be expressed as an infinite product instead. If we let the value of the series be denoted \zeta(p) (this is standard notation; \zeta is called the zeta function), then it can be seen that

\frac 1 {2^p} \zeta(p) = \frac 1 {2^p} + \frac 1 {4^p} + \frac 1 {6^p} + \frac 1 {8^p} + \dotsb

which is just the original series with all the terms with an odd denominator omitted. That means if we subtract this from the original series, we get the series all the terms with an even denominator omitted.

\left( 1 - \frac 1 {2^p} \right) \zeta(p) = 1 + \frac 1 {3^p} + \frac 1 {5^p} + \frac 1 {7^p} + \dotsb

Now we can divide this through by \frac 1 {3^p} to get rid of all the terms whose denominators are not multiples of 3. Then subtracting this from \left( 1 - \frac 1 {2^p} \right) \zeta(p) gives us the original series with all the terms whose denominators are multiples of 2 or 3 omitted. We can continue in the same manner, dividing through by \frac 1 {q^p} for every prime number q, to get rid of all the terms except the first one.

\left( 1 - \frac 1 {2^p} \right) \left( 1 - \frac 1 {3^p} \right) \left( 1 - \frac 1 {5^p} \right) \left( 1 - \frac 1 {7^p} \right) \zeta(p) \dotsb = 1

A simple rearrangement allows us to express \zeta(p) as an infinite product.

\begin{array}{rll}  \zeta(p) &= \left( \frac 1 {1 - 2^{-p}} \right) \left( \frac 1 {1 - 3^{-p}} \right) \left( \frac 1 {1 - 5^{-p}} \right) \left( \frac 1 {1 - 7^{-p}} \right) \dotsb \\  &= \frac {2^p} {2^p - 1} \frac {3^p} {3^p - 1} \frac {5^p} {5^p - 1} \frac {7^p} {7^p - 1} \dotsb  \end{array}

It doesn’t really feel like we have found out what, say, \zeta(2) is if all we can say is that it’s equal to \frac 4 3 \frac 9 8 \frac 25 24 \dotsb as well as 1 + \frac 1 4 + \frac 1 9 + \frac 1 16 + \dotsb Still, this is an interesting identity. Also, since we know that \zeta(1) is infinite, this tells us that the infinite product

2 \frac 3 2 \frac 5 4 \frac 7 6 \dotsb

is infinite. Now, since the numerators in this infinite product are simply the prime numbers, this yields a proof that there are infinitely many prime numbers. Because if there was a finite number of primes, 2 \cdot 3 \cdot 5 \cdot 7 \dotsb would be a finite product, and so would 2 \cdot 4 \cdot 6 \dotsb (the product of all numbers one less than a prime). Therefore the ratio \frac {2 \cdot 3 \cdot 5 \cdot 7 \dotsb} {2 \cdot 4 \cdot 6 \dotsb} of these two products would be finite too, but this ratio can also be written as the product above, which we know is equal to the harmonic series and hence infinite.