Skip to main content
Loading Explore guides…
Number Theory · Acedra
Home
Explore
Mathematics
Number Theory
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
345 segments
Copy
Hide video
0:00
- Welcome to Gresham College, and to this book launch of my "Number Theory: A Very Short Introduction,"
0:07
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.
0:16
I was also fortunate to have been invited to write the very short introduction to combinatorics, which appeared in 2016.
0:28
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,
0:38
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.
0:51
Pierre Fermat on the left, a lawyer in Southern France in the early 17th century.
0:59
Leonhard, an 18th century Swiss mathematician who is probably the most prolific mathematician of all time,
1:07
and Carl Friedrich Gauss, a German mathematician who published a classic text on number theory in the year 1801.
1:16
It was Gauss who claimed that mathematics is the queen of the sciences and number theory is the queen of mathematics.
1:24
So what is number theory?
1:28
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,
1:39
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.
1:54
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.
2:16
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,
2:28
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.
2:43
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?
2:52
I'll tell you about these ones later on.
2:58
So here are some of the questions that I'll be talking about today. The first ones are clearly about numbers,
3:06
such as whether that last number is prime,
3:09
whether any number made entirely of ones is a perfect square, and various problems arising from the calendar.
3:18
But number theory also expands into other areas, such as the geometry of right-angle triangles and the construction of regular shapes.
3:29
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.
3:44
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.
3:59
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?
4:11
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.
4:23
Third is clock arithmetic and the mathematics of the calendar.
4:28
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.
4:44
And if you find any of these topics too technical, just hold on, as I'll soon switch back to more straightforward topics.
4:55
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,
5:07
where we first list all the numbers up to a hundred,
5:10
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.
5:36
You may ask why one isn't a prime.
5:39
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,
5:53
and that this can be done in only one way apart from the order that the primes appear. So we could have written 60
6:01
as two times five times three times two, or some other order, but there must always be two twos, one three, and one five.
6:11
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.
6:36
But we can never list all the primes, because the list goes on forever.
6:40
But how would we prove this?
6:43
Unfortunately, given any prime, there's no rule for listing the next one. For example, what's the next prime after 997?
6:53
It's not at all obvious that it's 1,009,
6:57
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.
7:12
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.
7:23
So how did his proof go?
7:27
Here it is in modern language.
7:31
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.
7:45
We'll now create a new number by multiplying them all together and adding one, and we'll call this capital N.
7:54
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.
8:06
So what can we say about n?
8:09
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.
8:18
So in either case there's a new prime, and this contradicts our assumption that we've listed all of the primes.
8:25
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.
8:50
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,
9:00
which actually isn't prime. It's 59 times 509, so here we get two new primes we didn't have before.
9:12
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.
9:41
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,
10:05
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.
10:19
And the general result along these lines is proved by the German mathematician, Lejeune Dirichlet in 1837.
10:28
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.
10:40
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.
10:57
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.
11:13
And in the same way, there are infinite many prime numbers ending with one,
11:19
or with three, or with seven.
11:27
Let's now turn to something different, numbers that are one less than the power of two.
11:33
They're named after Marin Mersenne, a French mathematician and friar who investigated them in the 17th century.
11:43
If we look at these Mersenne numbers, we'll see that some of them are prime. Two squared minus one is three.
11:51
Two cubed minus one is seven.
11:55
Two to the fifth minus one is 31, and two to the seventh minus one is 127, and these are all primes.
12:05
But other Mersenne numbers are not prime. Two to the fourth minus one is 15, which isn't prime,
12:12
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.
12:25
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,
12:44
and here they're four, six, eight, and nine,
12:48
but is this always the case?
12:53
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.
13:16
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.
13:30
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.
13:53
So why are these numbers of interest, or simply a curiosity?
13:58
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,
14:24
a prime number with almost 25 million digits.
14:31
But another reason for looking at Mersenne primes is that they turn up in connection with a problem that dates from ancient Greek times.
14:41
The Greeks were interested in numbers which they called perfect numbers, whose factors, apart from the number itself, add up to the original number.
14:51
For example, six is perfect because its factors are one, two, and three,
14:57
and these add up to six.
15:00
And 28 is perfect because its factors are one, two, four, seven, and 14,
15:06
and these add up to 28.
15:11
The next two also known to the Greeks were 496 and 8,128,
15:17
and then they're aren't any more of them until 33,550,366.
15:27
So how did the Greeks find these perfect numbers?
15:32
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.
15:46
28 is four times seven, which we can write as two squared times two cubed minus one.
15:54
496 is 16 times 31, which is two to the fourth times two to the fifth minus one.
16:03
8,128 is 64 times 127, which is two to the sixth times two to the seventh minus one.
16:13
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.
16:34
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.
16:51
The next question is, does this give us all the perfect numbers?
16:55
2,000 years after Euclid, Leonhard Euler proved that every even perfect number is of Euclid's type.
17:03
But are there any odd perfect numbers?
17:07
Euler didn't know,
17:09
and nor indeed does anyone.
17:12
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?
17:28
Before we leave prime numbers, let's explore one more type, this time introduced by Fermat.
17:38
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.
17:47
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.
17:59
Fermat found the first few.
18:02
Two to the one plus one, which is three.
18:07
Two to the two plus one, which is five,
18:11
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.
18:31
Fermat noticed that these are all prime and he made the conjecture that every number of this form must be prime.
18:41
So the next one to test is two to the 32 plus one. Is that prime?
18:47
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.
19:03
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,
19:17
and later he found a method that gave this answer more quickly.
19:23
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.
19:40
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.
19:56
But all is not lost, as Fermat primes turned up again
20:00
but in a most unexpected place, the drawing of regular polygons. These are polygons where all the sides and all the angles are equal.
20:11
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.
20:26
Here's how Euclid constructed an equilateral triangle.
20:31
Starting with a line AB,
20:35
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.
20:46
Then draw the circle on the right by taking the center to be B and the radius as BA,
20:55
and then you have two circles. These two circles intersect at the point C.
21:02
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.
21:22
And constructing a regular hexagon is even easier.
21:27
Draw a circle with center O and some radius OA.
21:33
Then with a compass point at A and the same radius, mark off the point B on the circle.
21:41
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.
22:00
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
22:20
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.
22:43
And also by combining the constructions for three and five sides, Euclid constructed a regular polygon with 15 sides.
22:52
But neither Euclid nor anyone else was able to construct regular polygons with seven, nine, 11, 13, 14, 18, or 19 sides.
23:05
Are any of these possible?
23:08
Enter Gauss.
23:11
When aged only 18, he first showed how to construct a regular polygon with 17 sides.
23:20
He then answered the construction question completely by proving a remarkable result,
23:27
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
23:39
multiplied by unequal Fermat primes, which, as I remind you, are the five listed here.
23:48
So for example, we can construct polygons with 30 sides
23:53
because 30 is two times three times five.
23:58
We can do 32 sides because that's a power of two, or 34 sides because that's two times 17,
24:07
or 40 sides because that's two cubed times five.
24:13
But we cannot construct regular polygons with 35 sides because 35 is five times seven and seven is not allowed.
24:23
Or 36 sides, because 36 is two squared times three squared, and we're not allowed to use three twice.
24:32
Or 37, which is not a Fermat prime anyway, or 100, because the factor five occurs twice.
24:42
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.
24:58
Let's now leave prime numbers for a while and look at perfect squares.
25:04
The first 10 of these are listed here. One squared is one, two squared is four, three squared is nine, and so on.
25:16
You notice that none of these squares ends with two, three, seven, or eight,
25:23
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,
25:33
so no perfect square can end in two, three, seven, or eight.
25:40
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.
26:02
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.
26:30
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.
26:43
No perfect square has the form four N plus two or four N plus three,
26:50
and this is because if N is even, say it's twice K, then N squared is four times something,
27:00
and if N is odd, equal to two K plus one, say, then N squared is four times something plus one.
27:10
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.
27:29
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.
27:47
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,
28:01
giving us eight times something, plus one.
28:06
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.
28:36
Perfect squares also feature prominently in the geometry of right-angle triangles.
28:43
From our school days we remember the Pythagorean Theorem, which was probably not due to Pythagoras himself. It was originally a result about areas,
28:54
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,
29:09
and today I'm interested in when these side lengths are all whole numbers,
29:15
such as the three, four, five triangle, where three squared plus four squared is five squared. That's nine plus 16 is 25.
29:27
The five, 12, 13 right-angle triangle, with five squared plus 12 squared is 13 squared. 25 plus 144 is 169.
29:41
And the 15, eight, 17 triangle, with 15 squared plus eight squared is 17 squared. Well 225 plus 64 is 289.
29:51
What other examples are there, and can we find them all?
29:58
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.
30:15
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.
30:24
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.
30:34
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.
30:42
So we can assume that a and b cannot both be even.
30:47
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,
30:57
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.
31:06
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.
31:22
And to be definite, we'll always take a to be odd and b to be even.
31:28
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.
31:50
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.
32:05
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.
32:18
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.
32:28
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.
32:40
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.
32:57
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.
33:18
And using these formulas, we can compile a list that would eventually include all right-angle triangles.
33:28
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?
33:49
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.
34:01
But 29 cannot be two xy. It cannot be b, because that's even,
34:09
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.
34:20
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.
34:30
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.
34:44
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.
34:55
It then follows that a is 15 squared minus 14 squared, which is 29, as we expected,
35:02
b is two times 15 times 14, which has 420,
35:08
and c is 15 squared plus 14 squared, which is 421.
35:14
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.
35:35
Before we leave perfect squares, I'd like to show you a couple of results named after Fermat.
35:42
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,
36:00
but 42 cannot be written as the sum of two squares.
36:05
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.
36:26
So we can rule out any numbers of the form four n plus three, such as 43.
36:33
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.
36:46
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.
36:58
We've just ruled out all the primes of the form four n plus three,
37:03
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.
37:15
Moreover, this can happen in only one way.
37:19
So here are some examples. Five is a prime of the form four n plus one. Five is four plus one.
37:28
13 is nine plus four.
37:32
17 is 16 plus one.
37:36
29 is 25 plus four.
37:42
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.
37:58
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.
38:07
This is a very famous result in mathematics.
38:13
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,
38:20
but what about higher powers such as cubes, or fourth powers? Can we find positive numbers a, b, and c,
38:32
with a cubed but b cubed equals c cubed?
38:35
Or a to the fourth plus b to the fourth is c to the fourth?
38:41
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,
38:52
it would give rise to another solution with smaller numbers.
38:56
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.
39:11
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,
39:22
and he claimed to have a truly marvelous proof, but the margin is too small to present it.
39:29
I too have a truly marvelous proof, but this lecture is too short for me to give it to you.
39:36
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.
39:55
Let's now leave squares and look at some clock arithmetic.
40:00
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,
40:11
and writing mod 12 reminds us that we're using a 12 hour clock.
40:18
Similarly, if it's 10 o'clock and seven hours pass,
40:23
then it's five o'clock, so 10 plus seven is five mod 12.
40:31
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.
40:45
This way of calculating is called modular arithmetic or clock arithmetic, and it was introduced by Gauss in his number theory book of 1801.
40:55
And more generally, we say that a is the same as b mod n
41:01
if a and b leave the same remainder when divided by n.
41:07
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.
41:26
Gauss worked out all the rules for this type of arithmetic.
41:30
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,
41:43
and if it's Saturday, then in three days, it will be Tuesday.
41:50
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.
42:07
Saturday plus three days is Tuesday. Six plus three is two mod seven.
42:15
Well, using this idea, we can carry out calculations on the calendar.
42:22
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.
42:35
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.
42:58
Carroll's method is based on four numbers, which are then added mod seven.
43:05
The first number is the century number.
43:08
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.
43:23
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.
43:41
Third is the month number, where Carroll gave a complicated rule, but it's easier just to memorize this table of numbers.
43:50
And last is the day number, which is just the day of the month.
43:54
And there's also an extra condition, which we won't need today.
44:00
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.
44:10
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.
44:24
For the century number, we take the first two digits of the year. The year is 2020, so the first two digits are 20,
44:32
and divide it by four, giving a remainder of zero.
44:38
Subtracting this remainder zero from three gives three, and doubling the result gives six, so six is our century number
44:49
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.
45:01
Also four divides into eight two times, so we have one plus eight plus two, and that's 11.
45:12
For the month number, the number for September is five,
45:17
and for the day number, the 28 is 28,
45:22
and if you add all these numbers together, you get six plus 11 plus five plus 28, which is 50,
45:29
and 50 is one more than a multiple of seven,
45:33
so the answer is one, which is Monday, which is correct.
45:43
How about the question I posed earlier?
45:46
In which years of the century does February have five Sundays?
45:52
For this to happen, February must have 29 days, so it must be a leap year.
45:58
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.
46:10
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.
46:32
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,
46:45
and this is exactly divisible by seven. So adding 28 years to 2004 gives 2032, 2060, 2088.
47:01
So the only years in the century where February has five Sundays is 2004, 2032, 2060, and 2088.
47:15
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.
47:30
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
47:40
and calculate a to the power p minus a, then the result is always exactly divisible by p.
47:51
For example, if we choose a to be eight and the prime p to be 37,
47:57
then we find without calculating it that eight to the 37 minus eight is exactly divisible by 37,
48:08
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.
48:25
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,
48:39
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,
48:52
but before that, how do we prove Fermat's little theorem?
48:57
We can do so using algebra, but here's a different method that I rather like, by counting necklaces, colored necklaces.
49:07
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.
49:19
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.
49:41
Now, how many strings of colored beads can there be?
49:45
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.
50:00
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.
50:32
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.
50:44
And we can use this result to tell us about the shuffling of cards.
50:50
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.
51:03
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?
51:13
We can answer this with Fermat's little theorem.
51:19
Where does each card move after the first shuffle?
51:23
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.
51:36
For example, the card that starts in position one
51:40
ends up in position two,
51:44
and the card that starts in position 27
51:48
moves to position 54, which mod 53 is position one.
51:55
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.
52:10
So after one shuffle, the card in position x has moved to position two x, mod 53,
52:19
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,
52:34
and if the pack has now returned to its original order, then this must be the same as position x,
52:41
and that's true for each card.
52:44
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,
53:02
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.
53:16
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,
53:35
but the question I posed at the beginning of the lecture involved shuffling a pack with two jokers.
53:43
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.
53:56
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.
54:05
So how do we get 'round this difficulty?
54:10
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,
54:28
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.
54:48
So the pack is restored to its original order after 20 shuffles, and we can check as before
54:57
that no smaller number of shuffles works.
55:02
So the answer to our original problem is 20 shuffles. Raymond, can you pass me that piece of paper?
55:09
We've just used Fermat's result so that the prime p does not divide the number a.
55:16
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.
55:24
But what can we say if we replace p by a number that isn't prime?
55:29
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.
55:49
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?
56:08
It's called Euler's totient function, or phi function, denoted at Gauss's suggestion by the Greek letter phi.
56:18
Well, given any whole number n, five n counts for numbers up to n that have no factors in common with n.
56:25
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.
56:43
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,
56:57
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.
57:39
So now last, in the last five minutes, to our credit cards.
57:45
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
58:09
and that at one stage it uses Euler's theorem.
58:14
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.
58:43
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.
59:00
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.
59:19
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.
59:29
Here, he's chosen e to be 11.
59:33
He then publicly announces the two numbers, capital N and E, but not p and q, its factors, which only he knows.
59:42
So N and E are the public key, which is known to anyone who wants to find it out.
59:50
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.
1:00:03
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.
1:00:18
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.
1:00:29
Bob now has to decode it.
1:00:33
Because e five N have no factors in common, it can be shown that there are numbers, oops,
1:00:47
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.
1:01:05
In our example, 11 M was one mod 1,008,
1:01:08
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
1:01:24
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.
1:01:37
Don't worry about the details. The important thing is that the whole process simply relies on two calculations.
1:01:44
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
1:02:15
your Christmas present problems for this year?
1:02:18
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.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat