- Welcome to Gresham College, and to this book launch of my "Number Theory: A
Very Short Introduction," It's one of the latest
in the popular series of very short introductions, which Oxford University Press has produced over the past 25 years. I was also fortunate to have been invited to write the very short
introduction to combinatorics, which appeared in 2016. I've always been interested
in the history of mathematics, and in the book, and in this lecture, you'll meet four of the prime figures who feature throughout my story, the Greek mathematician, Euclid
of Alexandria, top right, who wrote his classic texts, "The Elements," in the third century, BC, and who probably didn't look like this. Pierre Fermat on the left, a lawyer in Southern France
in the early 17th century. Leonhard, an 18th century
Swiss mathematician who is probably the most prolific
mathematician of all time, and Carl Friedrich Gauss, a German mathematician who
published a classic text on number theory in the year 1801. It was Gauss who claimed that mathematics is the queen of the sciences and number theory is the
queen of mathematics. So what is number theory? Basically, it's the branch of mathematics that's primarily concerned with our ordinary counting numbers, one, two, three, et cetera, sometimes called the positive integers, and it's concerned with whether they're odd or even, or are
perfect squares or cubes, or can be divided exactly by
seven or some other number, or have some other, or have
some other such property. Particularly important
throughout the subject are the prime numbers, which we can think of as the
building blocks of the subject, like atoms in chemistry, and which are the only numbers whose only factors are itself and one. For example, 11, 13, 17,
and 19 are all prime. We can't split them up into factors. But 15 and 18 are not, because 15 is three times five and 18 is two times nine, which we can then write as
two times three times three, but we must be careful, because some numbers that look as though they might be prime numbers, such as 91 and 323, are not, because 91 is seven times 13 and 323 is 17 times 19. So it's not always easy to spot whether a given number is prime. For example, how about the three numbers at the bottom of the screen? I'll tell you about these ones later on. So here are some of the questions that I'll be talking about today. The first ones are clearly about numbers, such as whether that last number is prime, whether any number made entirely of ones is a perfect square, and various problems
arising from the calendar. But number theory also
expands into other areas, such as the geometry of
right-angle triangles and the construction of regular shapes. You'll also see applications
to the shuffling of cards and even some more practical matters such as the security of your credit cards, which is based on the
result on prime numbers that dates back to the 18th century. Number theory, once an abstract
branch of pure mathematics that was studied for its own sake, is now also central to
the study of cryptography and two other subjects
of practical importance. So here are the subjects
I'll be talking about today. First, prime numbers. How many are there? How are they distributed? And how do they arise in geometry? Next, perfect squares. How can we recognize them? What do they tell us about
right-angle triangles? And I'll also show you two
results related to Fermat. Third is clock arithmetic and the mathematics of the calendar. And finally, yet another result of Fermat is generalization by Euler and applications to the
counting of necklaces, the shuffling of cards, and as promised, protecting
your credit cards. And if you find any of
these topics too technical, just hold on, as I'll soon switch back to more straightforward topics. So let's start with prime numbers. Here's a table of the
primes up to a hundred. It's been produced by
an ancient Greek method called the Sieve of Eratosthenes, where we first list all the
numbers up to a hundred, then cross out the multiples of two, that is four, six, eight, et cetera, then the multiples of three, six, nine, 12, 15, et cetera, actually six and 12 have
already been crossed out, then those of five, and then seven, until we get the numbers
that appear in yellow here. These are the primes. You may ask why one isn't a prime. The answer lies on a fundamental property of our number system that we can get every number by multiplying primes together. For example, 60 is two times
two times three times five, and that this can be done in only one way apart from the order
that the primes appear. So we could have written 60 as two times five times three times two, or some other order, but there must always be two
twos, one three, and one five. But if we took one to be a prime, we could then write six as two times three or two times three times one, or two times three times
one times one, and so on, and we'd lose this fundamental property of factorization into
primes in only one way. That would be a great loss, so we choose to make one not a prime. But we can never list all the primes, because the list goes on forever. But how would we prove this? Unfortunately, given any prime, there's no rule for listing the next one. For example, what's the
next prime after 997? It's not at all obvious that it's 1,009, but Euclid, in his book, "The Elements," came up with a very different approach. Here it is in the earliest
surviving copy of the elements, from AD 888 in the
Bodleian Library in Oxford. And here's an English
version of Euclid's proof. The thing to notice is
it's a geometric argument. Instead of numbers, he used
the length of various lines. So how did his proof go? Here it is in modern language. Let's make the assumption that the list does not go on forever and that these are the only primes. We'll call them p one p two p three, and so on, up to p n. We're assuming there are no others. We'll now create a new number by multiplying them all
together and adding one, and we'll call this capital N. Then each of our primes divides the quantity in
brackets, their product, and so none of them can
divide the number n, which is got by adding one to it. So what can we say about n? Because it's not divisible
by any of our primes, it must itself be a new prime, or possibly be made up of new primes. So in either case there's a new prime, and this contradicts our assumption that we've listed all of the primes. So our assumption must have been wrong. We cannot list all the primes, and so the list must go on
forever, and incidentally, both of these possibilities
for n can occur. If the only primes that we knew were two, three, five, and seven, then n would be their product. That's 210 plus one, which is 211, and this is a prime that
we didn't have before. But if the only primes that we
knew were the ones up to 13, then multiplying them
together and adding one gives n is 30,031, which actually isn't prime. It's 59 times 509, so here we get two new
primes we didn't have before. But we can say more. We can adapt Euclid's proof to prove that the list of primes of the form four n plus three goes on forever. These are the primes which have three more than a multiple of four, such as three itself, or seven, which is four plus three, or 11, which is two fours
plus three, and so on. So these are all primes of
the form four n plus three. We can also prove there
are infinitely many primes that are one more than a multiple of four, the primes of the form four
n plus one, such as five. That's four plus one. 13, three fours plus one, and 17, four fours plus one, and so on. So there are infinitely many primes of the form four n plus
one and four n plus three, but we obviously can't say the same for numbers of the form four n plus two, because these numbers are all even, and so none of them can be
prime apart from two itself. And the general result along these lines is proved by the German mathematician, Lejeune Dirichlet in 1837. In this tour de force, he showed that there are
infinitely many primes of the form an plus b for any numbers a and b, as long as a and b have
no factors in common. This result was and still is
extremely difficult to prove, but it includes the cases four n plus one and four n plus three, because four has no factors
in common with one or three. And if we now take a to
be 10 and b to be nine, which also have no factors in common, we see there are infinitely many primes of the form 10 n plus nine. That is infinitely many prime
numbers ending with nine. And in the same way, there are infinite many prime
numbers ending with one, or with three, or with seven. Let's now turn to something different, numbers that are one less
than the power of two. They're named after Marin Mersenne, a French mathematician and friar who investigated them in the 17th century. If we look at these Mersenne numbers, we'll see that some of them are prime. Two squared minus one is three. Two cubed minus one is seven. Two to the fifth minus one is 31, and two to the seventh minus one is 127, and these are all primes. But other Mersenne numbers are not prime. Two to the fourth minus one
is 15, which isn't prime, and two to the sixth minus one is 63. Two to the eighth minus one is 255, and two to the ninth minus one is 511, and none of these is prime. So looking at the powers
of two that appear here, it's very tempting to believe that two to the N minus one is always prime when the exponent, the power n, is prime, here they're two, three, five, and seven, and that it's never prime when
the exponent n isn't prime, and here they're four,
six, eight, and nine, but is this always the case? The answer is partly. It's not difficult to show
that if n is not prime then two to the n minus
one isn't prime either. But if n is prime, we
have to be more careful. For example, if we take
the next prime, 11, we have two to the 11
minus one, which is 2,047. Now, this may look prime, but it isn't. It's 23 times 89. So if n is prime, then two to the n minus one
may or may not be prime. Mersenne himself came up with
a list of primes of this form, which is why they're named after him. He made a few false claims and
he left out a couple of them, but it was an impressive
list for the time, especially because he correctly included two to the 127 minus one, which is a prime number with 39 digits. So why are these numbers of
interest, or simply a curiosity? It turns out that if we're
looking for new primes, then Mersenne and primes
turn out to be our best bet. For example, the last 17
primes that have been found have all been of this kind, including the most recently discovered one in December, 2018, which is two to the 82,589,933 minus one, a prime number with
almost 25 million digits. But another reason for
looking at Mersenne primes is that they turn up in
connection with a problem that dates from ancient Greek times. The Greeks were interested in numbers which they called perfect numbers, whose factors, apart
from the number itself, add up to the original number. For example, six is perfect because its factors are
one, two, and three, and these add up to six. And 28 is perfect because its factors are one, two, four, seven, and 14, and these add up to 28. The next two also known to
the Greeks were 496 and 8,128, and then they're aren't any
more of them until 33,550,366. So how did the Greeks find
these perfect numbers? To see why they found them,
let's factorized them. We find that six is two times three, which we can write as two to the one time two squared minus one. 28 is four times seven, which we can write as two squared times two cubed minus one. 496 is 16 times 31, which is two to the fourth times two to the fifth minus one. 8,128 is 64 times 127, which is two to the sixth times two to the seventh minus one. And the other one, 33,550,336, is 4,096 times 8,191, which is two to the 12th times two to the 13th minus one. So in each case it's a power of two multiplied by a Mersenne
prime, in fact the next one. Well all of this was known to Euclid, who's book, "The Elements," includes a proof that the product of two to the n minus one and two to the n minus
one is a perfect number, as long as the second of
these numbers is prime. The next question is, does this give us all the perfect numbers? 2,000 years after Euclid,
Leonhard Euler proved that every even perfect
number is of Euclid's type. But are there any odd perfect numbers? Euler didn't know, and nor indeed does anyone. If there are any odd perfect numbers, there'll be absolutely huge, more than 10 to the power 1,500, so they probably don't
exist, but who knows? Before we leave prime numbers, let's explore one more type, this time introduced by Fermat. Instead of looking at
prime numbers of the form two to the n minus one, let's consider primes of the
form two to the n plus one. It turns out that these can be prime only when n is itself a power of two, two to the two to the n plus one. So let's look at some of these. Fermat found the first few. Two to the one plus one, which is three. Two to the two plus one, which is five, Two to the four plus one, which is 17. Notice that the exponents
are powers of two. Two to the eighth plus one is 257, and two to the 16th plus
one, which is 65,537. Fermat noticed that these are all prime and he made the conjecture that every number of
this form must be prime. So the next one to test
is two to the 32 plus one. Is that prime? Well, unfortunately it's a 10
digit number, over 4 billion, and Fermat's pocket
calculator didn't go that far. So Fermat never found out whether his conjecture was true or not. But once again, Leonard
Euler came to the rescue. After doing many calculations, he discovered that two to the 32 plus one can be evenly divided by 641, and later he found a method that gave this answer more quickly. But even Euler was
stuck with the next one, two to the 64th plus one,
which was a 20 digit number, which also turns out not to be prime, but its smallest prime
factor is over 200,000, so it's not surprising
that Euler missed it. But worse was to come. Many other Fermat numbers are now known, and none of them has
turned out to be prime. So Fermat's conjecture has turned out to be rather an unfortunate one. But all is not lost, as
Fermat primes turned up again but in a most unexpected place, the drawing of regular polygons. These are polygons where all the sides and all the angles are equal. The ancient Greeks were very interested in trying to construct these, whereby constructing
they allowed themselves to use only an unmarked ruler, no measuring allowed,
and a pair of compasses. Here's how Euclid constructed
an equilateral triangle. Starting with a line AB, use the compasses to draw
the circle on the left, where the center is A
and the radius is AB, so that gives you the left-hand circle. Then draw the circle on the right by taking the center to be B and the radius as BA, and then you have two circles. These two circles
intersect at the point C. Now A, the length AB, is the same as AC, because each is the radius
of the left hand circle, and the length BA is equal to length BC because each is the radius
of the right hand circle, so all three sides are equal and we have an equilateral triangle. And constructing a regular
hexagon is even easier. Draw a circle with center
O and some radius OA. Then with a compass point
at A and the same radius, mark off the point B on the circle. Then with the compass point
at B and the same radius, mark off the point C, and then in the same way,
the points D, E, and F, and if you adjoin these
six points together, that gives us a regular hexagon. What other polygons can we draw? Well, Euclid also showed
how to construct a square and a regular pentagon using just an unmarked
ruler and compasses, and he also showed how to double the number of sides of a regular polygon. So starting with the equilateral triangle with three sides, we can
construct regular polygons with six, 12, and 24 sides, and starting with a square, then doubling, we can construct regular polygons with eight, 16, and 32 sides, and starting with a regular pentagon, we can construct ones
with 10, 20, and 40 sides. And also by combining the constructions for three and five sides, Euclid constructed a regular
polygon with 15 sides. But neither Euclid nor anyone else was able to construct regular polygons with seven, nine, 11,
13, 14, 18, or 19 sides. Are any of these possible? Enter Gauss. When aged only 18, he first showed how to construct a regular polygon with 17 sides. He then answered the
construction question completely by proving a remarkable result, that a regular polygon with n sides can be constructed by ruler and compasses if and only if n is obtained
by taking some power of two multiplied by unequal Fermat primes, which, as I remind you,
are the five listed here. So for example, we can
construct polygons with 30 sides because 30 is two times three times five. We can do 32 sides because
that's a power of two, or 34 sides because that's two times 17, or 40 sides because that's
two cubed times five. But we cannot construct
regular polygons with 35 sides because 35 is five times seven
and seven is not allowed. Or 36 sides, because 36 is two
squared times three squared, and we're not allowed to use three twice. Or 37, which is not a Fermat prime anyway, or 100, because the
factor five occurs twice. So to answer the question I
mentioned at the beginning, we cannot draw a regular
polygon with a hundred sides, but it's remarkable
that these Fermat primes occur in such a problem. Let's now leave prime numbers for a while and look at perfect squares. The first 10 of these are listed here. One squared is one, two squared is four, three squared is nine, and so on. You notice that none of these squares ends with two, three, seven, or eight, and this is true in general because if we squared any
larger number, like 27, it must end with the same
digit as if we'd squared seven, so no perfect square can end
in two, three, seven, or eight. One interesting result
about perfect squares is if we add up the first
few positive odd numbers, then we always get a square. One is one squared,
one plus three is four, which is two squared, one plus three plus five is nine, which is three squared, and so on. We can prove this quite
easily by arithmetic, but more informative is
this geometric picture, which was supposedly known to the Pythagoreans of ancient Greece, that shows why it's true. Here, each L-shape has
an odd number of dots, one dot, three dot, five
dots, seven dots, and so on, and they all fit together
to make a perfect square. We also notice that every square is either a multiple of four, such as 16, or is one more than a
multiple of four, such as 25. No perfect square has
the form four N plus two or four N plus three, and this is because if N is even, say it's twice K, then N squared is four times something, and if N is odd, equal
to two K plus one, say, then N squared is four
times something plus one. So numbers made up entirely of ones, such as 11, 111, 1,111, and so on, cannot be perfect squares because they are all three
more than a multiple of four, and that's not allowed. Another nice result is if N is odd then its square must be one more than a multiple of eight, and we can see this
from our earlier result. If N is two K plus one, then N squared is four times
K times K plus one, plus one. But K times K plus one is the product of two consecutive numbers, and if you had two consecutive numbers, one must be odd and
the other must be even, so that product is even, giving us eight times something, plus one. But a much more attractive way
of illustrating this result is to draw a picture like the one here, where there are eight triangles of dots, plus an extra one in the middle. So in this case, we have nine square dots are made of eight lots
of 10 dots, plus one, and so has the form eight n plus one, and this works whatever number N is. Perfect squares also feature prominently in the geometry of right-angle triangles. From our school days we remember
the Pythagorean Theorem, which was probably not
due to Pythagoras himself. It was originally a result about areas, but it tells us that if a, b, and c are the lengths of the sides
of a right-angle triangle with c the longest side, or hypotenuse, then a squared plus b
squared equals c squared, and today I'm interested
in when these side lengths are all whole numbers, such as the three, four, five triangle, where three squared plus
four squared is five squared. That's nine plus 16 is 25. The five, 12, 13 right-angle triangle, with five squared plus
12 squared is 13 squared. 25 plus 144 is 169. And the 15, eight, 17 triangle, with 15 squared plus eight
squared is 17 squared. Well 225 plus 64 is 289. What other examples are there, and can we find them all? Well, we can easily get more examples by scaling up the size of these triangles. For example, from the
three, four, five triangle, we can scale up by 10 to
get a 30, 40, 50 triangle where 30 squared plus 40
squared is 50 squared. Or from three, four, five we can scale up by two to
get a six, eight, 10 triangle with six squared plus eight
squared equals 10 squared. But these scalings
aren't very interesting, so we'll assume that no
scalings have taken place and that a, b, and c
have no common factors. And in fact, we can assume
that any two of them have no common factor
because any such factor would then have to divide the third. So we can assume that a
and b cannot both be even. We can also assume that
they cannot both be odd, because then a squared and b squared would be one more than a multiple of four, so that c squared would be two
more than a multiple of four, and squares cannot be two more than a multiple of four, as we've seen. So one of a, b, and c is
odd and the other is even, as in our first examples. Three and four, one odd, one even, five and 12, 15 and
eight, one odd one even. And to be definite, we'll always take a to
be odd and b to be even. Well, by using similar
arguments which I won't go into, we can eventually prove that a, b, and c have the forms shown here, for some whole numbers, x and y. A is x squared minus y squared. B is two xy, and c is x
squared plus y squared. You can check that with these expressions, a squared plus b squared
is indeed c squared, and moreover, we can show
that x is greater than y, that x and y have no common factors, and that one is even and the other is odd. So let's see some examples of this. Here's what we had before. A has this form, x
squared minus y squared. B is two xy. C is x squared plus y squared, where x and y have these properties. So let's take some examples for x and y. If x is two and y is one, then a is two squared minus
one squared, which is three. B is two times two times
one, which is four, and c is two squared plus
one squared, which is five, so we get the right angle triangle with sides three, four, five. If x is three and y is two, then a is three squared minus
two squared, which is five, b is two times three
times two, which is 12, and c is three squared plus
two squared, which is 13, and we get the triangle
with sides five, 12, 13. And if x is five and y is two, then a is five squared minus
two squared, which is 21, b is two times five
times two, which is 20, and c is five squared plus
two squared, which is 29, and we get the right angle triangle with sides 21, 20, and 29. And using these formulas,
we can compile a list that would eventually include
all right-angle triangles. Now, earlier I asked for
all right-angle triangles with a side of length 29,
and we just found one. As we've just seen, by taking
x to be five and y to be two, we found the triangle
with sides 21, 20, and 29, but are there any others? Well, because 29 is a prime number, the size can have no common factor, and so we can again use the
expressions for a, b, and c, when there's no scaling involved. But 29 cannot be two xy. It cannot be b, because that's even, and so 29 must either be c, which is x squared plus y squared, or 29 must be a, which is
x squared minus y squared. But if 29 is x squared plus y squared, then the only possibility
is x is five and y is two, and we have the solution we had before. And if 29 is X squared minus y squared, we can factorized that into
two factors as shown here, and because 29 is prime, one of those factors must be
29 and the other must be one. So x plus y is 29, x minus y is one. and we can solve those equations to give x is 15 and y is 14. It then follows that a is
15 squared minus 14 squared, which is 29, as we expected, b is two times 15 times 14, which has 420, and c is 15 squared plus
14 squared, which is 421. So this is the only other
right-angle triangle with a side of length 29. The sides are 29, 420, and 421. Those are the only two
right-angle triangles with 29 as one of the sides. Before we leave perfect squares, I'd like to show you a couple
of results named after Fermat. In our study of right-angle triangles, we've been looking at sums of two squares, and we might ask what
numbers can be written as the sum of two squares. For example, 41 is five
squared plus four squared, but 42 cannot be written
as the sum of two squares. How do we look at this? Well, because all squares have the form four n or four plus one, four n plus one, the sum of two squares must be of the form four n or four n plus one, which is got by adding a
four n and a four n plus one, or four n plus two, adding
two of those odd numbers. So we can rule out any numbers of the form four n plus three, such as 43. We notice also that some numbers are sums of squares in more than one way. For example, 65 is 64 plus
one, but it's also 49 plus 16. Well, it turns out that we can deal with the general question of which numbers can be written
as the sum of two squares if we can first decide which prime numbers are the sum of two squares. We've just ruled out all the primes of the form four n plus three, but as claimed by Fermat
and later proved by Euler, every prime number of
the form four n plus one can be written as the sum of two squares. Moreover, this can happen in only one way. So here are some examples. Five is a prime of the
form four n plus one. Five is four plus one. 13 is nine plus four. 17 is 16 plus one. 29 is 25 plus four. 41 is 25 plus 16, and you can make up
some more for yourself, but it's a remarkable result proved all those years ago by Euler and conjected by Fermat. But the other result of
Fermat I want to mention is his famous last theorem, because it was the last of
his theorems to be proved. This is a very famous
result in mathematics. When we're looking at
right-angle triangles, we found positive numbers a, b, and c with a squared plus b
squared is c squared, but what about higher powers such as cubes, or fourth powers? Can we find positive numbers a, b, and c, with a cubed but b cubed equals c cubed? Or a to the fourth plus b to
the fourth is c to the fourth? Fermat himself found an ingenious argument to show that there are no
solutions for the fourth powers. In his method of infinite descent, he showed that if there were a solution, it would give rise to another
solution with smaller numbers. And then that in turn would give rise to yet another solution with yet smaller numbers,
and so on forever, but you can't keep on reducing
the numbers forever and ever, so the original equation
couldn't have had a solution. Now, Fermat believed that there are no positive number solutions to a to the n plus b to the n and c to the n for any power n larger than two, and he claimed to have
a truly marvelous proof, but the margin is too small to present it. I too have a truly marvelous proof, but this lecture is too short
for me to give it to you. In any case, Fermat's conjecture was eventually proved in 1995, 350 years after he first mentioned it, by Andrew Weil's, then
at Princeton University and now at Oxford. Let's now leave squares and
look at some clock arithmetic. If it's nine o'clock and six hours pass, then it's three o'clock. So we can write nine plus six is three, and writing mod 12 reminds us that we're using a 12 hour clock. Similarly, if it's 10
o'clock and seven hours pass, then it's five o'clock, so 10 plus seven is five mod 12. It actually turns out
to be more convenient to write zero rather than 12, so eight plus four is 12 o'clock. In other words, eight
plus four is zero mod 12. This way of calculating is
called modular arithmetic or clock arithmetic, and
it was introduced by Gauss in his number theory book of 1801. And more generally, we say
that a is the same as b mod n if a and b leave the same
remainder when divided by n. So 15, nine plus six is 15. 15 is three mod 12, because they leave the same
remainder when you divide by 12. And 17 is five mod 12. And another way of saying this is that a minus b can be divided by n. Gauss worked out all the rules
for this type of arithmetic. But we don't have to stick
to arithmetic mod 12. We can also use it for the
seven days of the week. For example, if it's Thursday, then in four days, it would be Monday, and if it's Saturday, then in three days, it will be Tuesday. If we number the days of the
week from day zero, Sunday, day one is Monday, up to
day six, which is Saturday, we can then write these statements as Thursday plus four days is Monday, four plus one is one mod seven. Saturday plus three days is Tuesday. Six plus three is two mod seven. Well, using this idea, we can carry out
calculations on the calendar. Several people have produced methods for finding the day of
the week for a given date, including Gauss himself, and also the mathematician John Conway, who died earlier this year. Here's a method devised
by Charles Dodgson, better known as Lewis Carroll, the author of "Alice's
Adventures in Wonderland," and it was published under his pen name. So let's see how it works in detail, first quickly in general, and then more slowly for a specific date. So let's have a look at this. Carroll's method is based on four numbers, which are then added mod seven. The first number is the century number. What century are we in? To find this, we divide the first two digits of
the year, in our case 20, by four, subtract the remainder from three and double the result. Next is the year number. Here Carroll's rule is to divide the last two digits of the year by 12 and then add the quotient, the remainder, and the number of times that four divides into the remainder. You'll see how this works in a minute. Third is the month number, where Carroll gave a complicated rule, but it's easier just to
memorize this table of numbers. And last is the day number, which is just the day of the month. And there's also an extra condition, which we won't need today. So let's see how this works in practice, and if it seems rather complicated, Carroll himself claimed to be
able to apply it in his head in around 20 seconds. So let's see how it
works for today's date, the 28th of September, 2020,
as you can see on the right. So here, the general method is on the left and we'll work through it, and the example is on the right. For the century number, we take the first two digits of the year. The year is 2020, so the
first two digits are 20, and divide it by four,
giving a remainder of zero. Subtracting this remainder
zero from three gives three, and doubling the result gives six, so six is our century number For the year number, we take the last two digits of the year, which is also 20 for 2020, divide it by 12, giving
one remainder eight. Also four divides into eight two times, so we have one plus eight
plus two, and that's 11. For the month number, the number for September is five, and for the day number, the 28 is 28, and if you add all these numbers together, you get six plus 11 plus
five plus 28, which is 50, and 50 is one more than
a multiple of seven, so the answer is one, which
is Monday, which is correct. How about the question I posed earlier? In which years of the
century does February have five Sundays? For this to happen, February must have 29 days,
so it must be a leap year. Now, the 1st of January,
2001 was a Monday, or you can start with any
other date who's day you know, so you can easily check that the 1st of February was a Thursday. Now, the number of days in
any non-leap year is 365, which is one more than
a multiple of seven, so the 1st of February,
2001 was a Thursday, 1st of February, 2002 is a Friday, 1st of February, 2003 is a Saturday, and 1st of February, 2004 is a Sunday. So that's one answer, 2004. Also, the cycle of days
repeats every 28 years because the total number
of days in 28 years is 28 times 365 plus seven leap days, and this is exactly divisible by seven. So adding 28 years to 2004 gives 2032, 2060, 2088. So the only years in the century where February has five Sundays is 2004, 2032, 2060, and 2088. For my final topic, I want to look at another result of Fermat and the generalization of it by Euler. If parts of this get too technical, don't worry about the details, but try to follow the general story. One form of Fermat's little
theorem, as it's often called, tells us if you choose any whole number a and any prime number p and calculate a to the power p minus a, then the result is always
exactly divisible by p. For example, if we choose a to be eight and the prime p to be 37, then we find without calculating it that eight to the 37 minus eight
is exactly divisible by 37, and we can also get another
version of Fermat's results, which we'll need in a
moment, by dividing by a, and we can do this if p doesn't divide a, and it tells us that a to
the p minus one minus one is also exactly divisible by p. For example, when a is two and p is 53, we see that two to the power 52 minus one is exactly divisible by 53, which we can also write
using our clock arithmetic as two to the 52 is one mod 53, and I'm going to use
that result in a minute, but before that, how do we
prove Fermat's little theorem? We can do so using algebra, but here's a different
method that I rather like, by counting necklaces, colored necklaces. Our necklaces will have p beads, and there are a colors available, and in our colorings, we're going to use at least two colors. First of all, notice, as
you can see on the left, that necklaces can be rotated. So the necklace on the left, which is red, blue, red, red, yellow, is the same as if we start with blue, blue, red, red, yellow, red, and also the same as the
other ones shown on the left. Now, how many strings of
colored beads can there be? Well, the total number is
you've got a for the first, a colors for the first bead, a for the second bead, a
for the third, and so on, so that gives us a total of
a to the power p for p beads. But we must exclude all the
strings in just one color, such as red, red, red, red, red, and there are a of these,
one for each color. So this seems to give us a to the p minus a strings of beads, but we're taking these and
making them into necklaces, and for necklaces, each one
is counted p times over, so we have to divide that number by p, so the number of different
colored necklaces is a to the p minus a divided by p. But the number must be,
it must be a whole number, so a to the p minus a must be exactly divisible by p, as we wanted to prove. And we can use this result to tell us about the shuffling of cards. Starting with a normal pack of cards, we can do a riffle shuffle. That is, we divide into two piles as shown in the middle, and then shuffle it so
the cards in the two piles alternate as shown on the right. Now, if you carry on shuffling
the pack in the same way, how many shuffles do you need before every card returns
to its original position? We can answer this with
Fermat's little theorem. Where does each card move
after the first shuffle? You can check that the card
originally in position x moves to position two x, or to position two X mod 53 when two x is larger than 52. For example, the card that
starts in position one ends up in position two, and the card that starts in position 27 moves to position 54, which
mod 53 is position one. So the new ordering of the
cards, as shown on the right, is 27 one, 28 two, 29 three, and so on, to 51 25, 52 26. So after one shuffle,
the card in position x has moved to position two x, mod 53, and after two shuffles, it then moves to position four x mod 53, and so on. So after n shuffles, it moves to position two to the nx, mod 53, and if the pack has now
returned to its original order, then this must be the same as position x, and that's true for each card. So two to the n times x
is the same as x mod 53 for each card in each case. If we now divide by x, this tells us that two
to the n is one mod 53, and we want to find the numbers
n for which this is true, but as we saw before, with
Fermat's little theorem, two to the 52 is one mod 53, so the pack is returned
to its original order after 52 shuffles. But is that the smallest
possible number of shuffles? Well, if it happened after fewer shuffles, then the number of those shuffles would have to divide 52, it turns out, and you can check as I've done below that none of them works. So the answer to this question is 52, but the question I posed at
the beginning of the lecture involved shuffling a pack with two jokers. So we now have 54 cards, and doing what we did earlier tells us that two to the n is now one
mod 55 instead of mod 53. But this time we can't use
Fermat's little theorem to deduce that the smallest
number of shuffles is 54, because 55 isn't a prime number. So how do we get 'round this difficulty? Well, if 55 divides exactly
into two to the n minus one, then so do five and 11,
and these are both primes, so we can apply Fermat's
little theorem to each one, telling us that two to
the four is one mod five, and two to the 10 is one mod 11. How do we combine these? Raising the first one to
the fifth power tells us that two to the 20 is one mod five, and squaring the second one tells us that two to 20 is also one mod 11, and combining these,
which we're allowed to do, tells us that two to the 20 is one mod 55. So the pack is restored
to its original order after 20 shuffles, and
we can check as before that no smaller number of shuffles works. So the answer to our original
problem is 20 shuffles. Raymond, can you pass
me that piece of paper? We've just used Fermat's result so that the prime p does
not divide the number a. Then a to the P minus one
can be divided exactly by p. That is, a to the p
minus one is one mod p. But what can we say if we replace p by a number that isn't prime? Unlikely as it may seem,
and we'll see in a minute, our answer, which is due to
Euler, arises in cryptography, which will be our final example and is fundamental in such security issues as how our credit cards be kept safe. So number theory can be
used to solve problems that are even more important
than the shuffling of cards. Now, just as Fermat's result tells us that the number a raised
to the power p minus one is one more than a multiple p, so Euler's more general formula tells us that for two numbers a and n, a raised to some power is one
more than a multiple of n, but what is this power? It's called Euler's totient
function, or phi function, denoted at Gauss's suggestion
by the Greek letter phi. Well, given any whole number n, five n counts for numbers up to n that have no factors in common with n. For example, if n is 10, the number with factors in common with 10 are the even numbers,
two, four, six, and eight, and the numbers five and 10 itself, so the only numbers with no
factors in common with 10 are one, three, seven and nine,
and there are four of them, so phi of 10 is four. Likewise, if n is 12, then the
numbers would count to one, not two, three, or four, five, not six, seven,
not eight, nine, or 10, 11, not 12, so phi of 12 is also four, and we can easily check
that for any prime number p, five p is p minus one, because
we don't count p itself, and this tells us that if p is prime, then Euler's theorem
reduces to Fermat's theorem, which we had above. And we can also prove that
if p and q are both primes, then phi, their product, pq, is p minus one times q minus one. For example, and we'll
need this in a minute, 1,073 is a product of
the primes, 29 and 37, so phi of 1,073 is 29 minus
one times 37 minus one, 28 times 36, or 1,008. So now last, in the last five
minutes, to our credit cards. RSA cryptography is
named after the initials of Rivest, Shamir, and
Adleman, who found it in 1978, not knowing that it had
earlier been invented at Bletchley park by Cliff
Cox, but kept secret. Now, this may look daunting, but don't worry too much
about the details just yet. The main points are that the whole process of securing your credit cards appears on this one page and that at one stage
it uses Euler's theorem. It also relies on the fact
that we can easily multiply two prime numbers together, but we can't usually go
the other way around. Even, we can multiply
seven and 13 to give 91, but turning it around,
factorizing 91 as seven times 13 wasn't immediately obvious. And for large primes, multiplying is effectively
a one way process, like squeezing toothpaste from the tube or breaking eggs to make an omelet. So let me now just explain why
your credit cards are safe. Suppose that Alice wishes to
send a secret message to Bob in such a way that it
cannot be intercepted by an eavesdropper sometimes called eve. Bob first selects two prime, large primes, with maybe 200 digits each, and multiplies them to
get the number N as pq. In our simplified example, p and q were 29 and 37 and N is their product, 1,073. Bob then calculates five
N as we did earlier, and we got the 1,008, and
he then chooses a number e with no factors in common with it. Here, he's chosen e to be 11. He then publicly
announces the two numbers, capital N and E, but not
p and q, its factors, which only he knows. So N and E are the public key, which is known to anyone
who wants to find it out. Now, to encode her message, Alice first converts it to numerical form, for example, by taking A is
one, B is two, and so on, and calls it capital
M, so M is the message. Knowing e and capital N, she then calculates M to the power e and takes the result, mod N, and calls this capital E. This is her coded message,
which she sends to Bob. So she knows e and N, and she knows her own message M. She calculates M to the e mod N, and that's the message
that she sends to Bob. Bob now has to decode it. Because e five N have
no factors in common, it can be shown that
there are numbers, oops, because e and five N have
no factors in common, it can be shown that our
numbers little m and little n satisfy in this equation here so that n times e is one mod phi N, and from this, he can calculate N, so basically it's a method of calculating this number little m. In our example, 11 M was one mod 1,008, and Bob can then calculate N to be 275, and this is where
Euler's theorem comes in. M to the power phi N is one mod phi N, and it follows from this
by a line of algebra which I won't go into that calculating each of the M mod N gives Alice's message M. Alice message is E to the, in this case, two to the 75 mod 1,0073. Don't worry about the details. The important thing is
that the whole process simply relies on two calculations. Alice calculates N to the e mod N. Bob calculates E to the M mod N, and that is the whole of the reason that your credit card is secure. Now, I hope you'll remember that next time you use your credit card, and if not, then the
obvious place to look it up, and all the other topics and problems I've been talking about,
and much else besides, is in the book I've been launching today. May I encourage you to give it to all your friends for
Christmas in order to solve your Christmas present
problems for this year? Moreover, you will probably
lose all your friends as a result, so this will solve your Christmas present
problems next year too. Thank you for listening.
