Number Theory: A Very Short Introduction

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 example, 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 E^m (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 E²⁷⁵ (mod 1073), and so recaptures her original message.

Chapter 7Conjectures 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