by Robin Wilson
What happens if we now add two Jokers to the pack, making 54 cards in total? Carrying out a similar analysis, we seek the smallest value of n for which . Now is not prime, and we can no longer apply Fermat’s result directly. But Fermat’s little theorem tells us that , and so . It also tells us that , and so . Combining these results (which we can, because , we deduce that , and so the order of the cards is certainly restored after 20 shuffles.
Can this happen earlier? If so, the number of shuffles must be a factor of 20—that is, 2, 4, 5, or 10. But
None of these works, so the order of the cards is restored for the first time after 20 shuffles.
Generalizing Fermat’s little theorem
We’ve presented Fermat’s little theorem, that if p is a prime number and a is any integer that isn’t divisible by p, then . But what happens if p is replaced by a composite number? Is Fermat’s result still true, and if not, can we adapt it so that it holds in this more general case?
To show that Fermat’s result can fail when the modulus is not prime, let’s look at congruences (mod 10), and let (which is coprime to 10). Then , which is not congruent to 1 (mod 10).
Euler’s φ-function
Before we answer the questions above, we’ll first need to introduce what Euler called the ‘totient function’; the choice of the Greek letter φ (phi) to denote it was made by Gauss in 1801. We define it as follows:
For each positive integer n, let φ(n) be the number of positive integers up to n that are coprime to n—that is, the number of positive integers for which .
For example, , because the numbers (up to 10) that are coprime to 10 are 1, 3, 7, and 9; likewise, , where the relevant integers are 1, 3, 7, 9, 11, 13, 17, and 19. A table of values of φ(n) for appears in Table 5:
Table 5. Values of φ(n), for
There are a few things to notice here. For a start,
If p is a prime number, then ,
because every number up to p is coprime to p, except for p itself.
Also, , because every number up to p2 is counted, except for the p multiples of p: for example, , because we count every number up to 9 except for 3, 6, and 9. Likewise, for any power pe,
For example,
Also, if p and q are different primes, then
because we need to discount the p multiples of q and the q multiples of p, and then restore the number pq (which we had discounted twice). We’ll need this result later.
More generally, if , where a and b are coprime, then : for example, , and so
This multiplicative idea holds in general: if n is any product of numbers that are coprime in pairs, then φ(n) is the product of the φ-values of the separate numbers: for example,
if , then
We can also rewrite this product as
or as
and both of these forms are useful. In general, if the number n is written in canonical form as a product of primes—that is, if , then
This can also be written as
for example, 100 has prime factors 2 and 5, and so
as we saw earlier.
These formulas can be used for calculation, and also to prove some general results about φ(n). For example, we can prove that
If , then φ(n) is even,
as indicated in our table of φ-values. This is because either n is a power of 2 (larger than 2) or it has an odd prime factor p. In the former case, if , where , then , which is even. In the latter case, the formula for φ(n) must include the factor which is even, and so φ(n) is even.
But some even numbers can never appear as φ-values: for example, our table includes the even numbers 2, 4, 6, 8, 10, 12, 16, and 18, but not 14. To see why, suppose that . Now if n has a prime factor p, then must divide 14, and this can happen only when p is 2 or 3. So n must be 2r, or 3s, or , for some numbers r and s, and so , or , or , respectively. But none of these has 7 as a factor, and so φ(n) cannot be 14.
Euler’s φ-function has some interesting properties. For example, what do we get if we’re given a number n and we add up the φ-values of all its factors? If , then its factors are 1, 2, 5, and 10, and their sum is
More generally, it turns out that if we add up the φ-values of the factors of any number n, then we get n itself.
Euler’s theorem
We’ll now return to the task of extending Fermat’s little theorem about the powers of a number (mod p) to powers of a number (mod n), where n may be composite. When we introduced Fermat’s result we started by looking at the powers of certain numbers (mod 7). We’ll now imitate the process by looking at the first few powers of certain numbers (mod 9):
It turns out that, apart from the powers of 0, 3, and 6, every 6th power is 1.
Now , and we can summarize this by saying:
If a is coprime to 9, then .
This result is a special case of the result we were seeking:
Euler’s theorem: If n is a positive integer, and if a is any integer with , then .
For example, if and , then and , and we deduce that , which is correct because
To see why Euler’s theorem is true, let’s imitate what we did earlier and look at the first few positive multiples of the numbers coprime to 9—that is, 1, 2, 4, 5, 7, and 8—and reduce them (mod 9). Multiplying these numbers by 4 gives 4, 8, 16, 20, 28, 32, and reducing them (mod 9) gives 4, 8, 7, 2, 1, 5. Likewise, multiplying them by 7 gives 7, 14, 28, 35, 49, 56, and reducing them (mod 9) gives 7, 5, 1, 8, 4, 2. In each case we get a rearrangement of the numbers 1, 2, 4, 5, 7, and 8.
To prove Euler’s theorem in this case, we’ll mimic the proof of Fermat’s little theorem. Multiplying the numbers 1, 2, 4, 5, 7, and 8 by a (where ) gives 1a, 2a, 4a, 5a, 7a, and 8a, and reducing these (mod 9) gives 1, 2, 4, 5, 7, and 8, though possibly in a different order. So, on multiplying them all together, we get
Cancelling the numbers 1, 2, 4, 5, 7, and 8 (which are all coprime to 9) then gives , as we saw above.
The general proof is similar. We begin by listing the φ(n) numbers up to n that are coprime to n—we’ll call them b1, b2, …, bk, where . We then multiply them by a, to give the multiples b1a, b2a, …, bka, and reduce them (mod n). The results will all be different, and must therefore be b1, b2, …, bk in some order.
Multiplying these multiples of a together and equating the two products, as above, gives
Cancelling the terms b1, b2, …, bk (which are all coprime to n) then gives
as we wished to prove.
We conclude this section by noting that if n is a prime number p, then , and we get , which is Fermat’s little theorem, as we’d expect.
Factorizing large numbers
Before we see how Euler’s theorem makes its appearance in cryptography, let’s consider briefly the subject of trying to factorize a number into its prime factors.
Many real-life processes are irreversible: for example, it’s easy to squeeze toothpaste from a tube but difficult to reverse the operation, and it’s easy to break an egg but impossible to ‘unbreak’ it, especially if it’s Humpty Dumpty.
Another example is the factorization of large numbers. It’s generally straightforward to multiply two primes together, but if we’re given the product, then it’s often more difficult to factorize it into its two prime constituents: for example, we can easily multiply 23 and 89 to give 2047, but given the number 2047 it may take us some time to find its factors by hand. If the primes are large—say, 250 digits—then their product can easily be calculated by machine, but no current computer can factorize their 500-digit product in a reasonable amount of time.
A traditional method for testing whether a given number n is prime is due to Fermat, and works particularly well when n is the product of two numbers that are close to each other. The method is based on the fact that
To apply Fermat’s method, we first find the smallest integer m that’s √n or larger, and we calculate the numbers
until we reach a square. Then, if (say), we have
which gives a factorization.
For e
xample, if , we check that , and so we take . Then:
So .
Fermat used his method to factorize the number .
Noting that , he took and calculated as follows:
Now , and so
giving him a factorization.
Fermat’s approach to factorization is the basis of several rather more sophisticated methods for factorizing large numbers. One of these is called the quadratic sieve method which seeks some numbers among the above differences whose product is a square, rather than simply being a square. Another method, due to Euler and based on an idea of Mersenne, led to the factorization . Many other methods have been described, but no efficient algorithm has ever been discovered.
RSA public key cryptography
We’ve just seen that multiplying two prime numbers is comparatively simple, but factorizing a large number into its prime factors can be extremely difficult. It’s from this asymmetric process that a method for secretly encrypting messages has been devised. It was proposed in 1973 by Clifford Cocks, formerly of the secret World War II codebreaking unit at Bletchley Park in England, but remained classified until 1997. Independently rediscovered in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman, it’s now known by their initials as RSA encryption. It’s essentially this method that is used to preserve intelligence information, and it provides us with an excellent example of how results in pure mathematics that were investigated for their own interest (such as Euler’s theorem) can later be applied in unexpected ways in highly practical situations.
Suppose that Alice wishes to send a very secret message to Bob, in such a way that no eavesdropper who might intercept it can decode it. Bob first selects two large primes, p and q, and calculates their product, . He also chooses a number e that is coprime to φ(N)—that is,
Bob then publicly announces the numbers e and N, but he doesn’t release N’s factors, p and q. The numbers e and N are the public key that’s known to all, while Bob remains the only person who knows p and q, and therefore φ(N).
Alice can now send her secret message. She first converts it to a numerical form—for example, by writing , —and calls the resulting message M. Knowing the numbers e and N, she can then calculate the number , and send it to Bob, the only person who can decrypt it. But how can he do so?
To recover M, Bob first calculates a number m for which . To do so, he can use Euclid’s algorithm from Chapter 2: because , he can find integers m and n for which , and so .
Then, on receiving the encrypted message E and knowing m, he calculates
But, by Euler’s theorem, , and so . It follows that , and so all that Bob needs to do is to calculate Em (mod N) in order to retrieve Alice’s original message M.
As an example of the calculations involved, suppose that the public key consists of the numbers and . Bob knows that , and so he can calculate
and check that , as required.
The congruence now becomes . By using Euclid’s algorithm, Bob finds that
so that , and so he takes . Having received Alice’s coded message as E, Bob now calculates E275 (mod 1073), and so recaptures her original message.
Chapter 7
Conjectures and theorems
In this chapter we’ll explore some further topics that are related to prime numbers. We’ll start with two problems that we met in Chapter 1, on sums of primes and twin primes, and follow this by investigating the distribution of prime numbers. We then turn our attention to lists of primes that are equally spaced, and to a fuller exploration of unique factorization. This chapter presents several of the deepest results in number theory, and includes some examples of recent work in the subject.
Two famous conjectures
In this section we explore two conjectures on primes that are very easy to state but have never yet been proved. Their difficulty is linked to the fact that they involve addition or subtraction, whereas the primes are mainly concerned with multiplication.
Goldbach’s conjecture
On 7 June 1742, the German mathematician Christian Goldbach wrote a letter to Euler about writing numbers as the sum of primes. This contained a claim that is now known as ‘Goldbach’s conjecture’, but which Euler described as ‘a completely certain theorem, although I cannot prove it’:
Goldbach’s conjecture: Every even number that is larger than 2 can be written as the sum of two primes.
In Chapter 1 you saw some instances of this, and further examples are and .
Goldbach’s conjecture is now known to be true for all even numbers up to , and so finding a counter-example seems extremely unlikely.
A major advance in settling Goldbach’s conjecture was made in 1966 by the Chinese mathematician Chen Jingrun, who proved that every even number that is larger than 2 can be written as the sum of a prime number and an ‘almost prime’—that is, another number that is either a prime or a number with just two prime factors. His work involved some systematic sieve methods, an area of number theory whose origins can be traced back to the sieve of Eratosthenes which we met in Chapter 3.
A result that seems related to Goldbach’s conjecture had already been proved a few years earlier, in 1937, by the Russian mathematician Ivan Matveevich Vinogradov:
From some point onwards, every odd number can be written as the sum of three primes.
Here, the phrase ‘from some point onwards’ might seem to indicate that only a small number of cases remain to be checked—which is a finite task that could quickly be carried out by hand, or by computer. But in practice, the point from which the result had been proved true was massive, with millions of digits, and checking the remaining cases was way beyond the capacity of any existing computers. However, in 2013, and following much further theoretical work by several people, the Peruvian mathematician Harald Helfgott (working in France, with computational help from the British number theorist Dave Platt) managed to reduce, and eventually to eliminate, the huge gap between what had been proved for large numbers and what was already known for small numbers, giving the following result:
Every odd number that is larger than 5 can be written as the sum of three primes.
What has this to do with Goldbach’s conjecture? Well, if Goldbach’s conjecture is true, then every even number (≥ 4) is the sum of at most two primes p and q, and adding 3 tells us that every odd number (≥ 7) is the sum of at most three primes (p, q, and 3). But unfortunately the argument doesn’t work the other way around: Helfgott’s achievement doesn’t yield a proof of Goldbach’s conjecture, but it does provide a weaker form of it. For if n is an even number that is larger than 8, then can be written as the sum of three primes. Also, , and so
Every even number that is larger than 6 can be written as the sum of four primes.
The twin prime conjecture
The second conjecture concerns twin primes which, as you saw in Chapter 1, are pairs of primes that differ by 2. Those up to 100 are
There are thirty-five pairs of twin primes up to one thousand, over eight thousand pairs up to one million, and over three million pairs up to one billion. The largest known pair has over fifty thousand digits!
In 1846 the following conjecture was formulated by the French number theorist Alphonse de Polignac:
Twin prime conjecture: There are infinitely many pairs of twin primes.
For many years, number theorists have tried to prove this, but with little success. Then, in 1966, and associated with his work on Goldbach’s conjecture, Chen Jingrun used sieve methods to prove that there are infinitely many prime numbers p for which is either a prime or an almost prime.
Among other more recent investigations were proofs that the twin prime conjecture is true if one is allowed to assume certain additional results. Then, suddenly and unexpectedly, a major breakthrough was made in June 2013 by the Chinese-born American mathematician Yitang Zhang. Using some of this earlier work, but without needing to assume any other results, he proved that infinitely many pairs of prime numbers differ by at most 70 million. This is a very
far cry from the desired result, with 70 million instead of 2, but it was the first result of its kind and it created a whole cottage industry of mathematicians seeking to reduce the gap to something more manageable.
At first, the gap came down from 70 million to around 42 million, and then something rather remarkable happened. Mathematicians are used to writing up their research and then publishing it in polished form in journals, a process that can take a year or more: this means that much time may elapse before their results become widely known. But from around 2009 various mathematicians—notably, Tim Gowers from Cambridge and Terry Tao from Los Angeles—had proposed a more collaborative approach, known as the Polymath project, in which contributors from around the world could work on problems publicly by pooling their ideas, feeding in comments, and suggesting improvements. Advances could thereby be made and shared at a much faster rate, while individual contributors would still receive due credit for their ideas.
In June 2013 Tao initiated Polymath8, a project entitled ‘Bounded gaps between primes’, in which contributors were invited to improve Zhang’s result. Within a few weeks, with contributions from many people, the gap had decreased from 42 million to 387,620, and then to about 12,000, and after another month to 4680.
This was followed by a lull in activity, and new ideas were needed. By this time, James Maynard, who had gained his doctorate in Oxford and was then in Montreal, appeared on the scene with a different approach, also discovered independently by Tao. By the end of 2013 Maynard had reduced the gap to 600 and, as he wrote at the time: