Number Theory: Queen of Mathematics

Number Theory: Queen of Mathematics

SUBTITLE'S INFO:

Language: English

Type: Robot

Number of phrases: 1490

Number of words: 8733

Number of symbols: 35084

DOWNLOAD SUBTITLES:

DOWNLOAD AUDIO AND VIDEO:

SUBTITLES:

Subtitles generated by robot
00:00
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
00:33
will meet four of the prime figures who feature throughout my story the greek mathematician euclid of alexandria top right who wrote his classic text the elements in the third century bc and who probably didn't look like this pierre pierre fermar on the left a lawyer in southern france in the early 17th century leonard euler an 18th century swiss mathematician who is probably the most
01:03
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 etcetera sometimes called
01:36
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 of 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
02:09
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 3 times 5 and 18 is 2 times 9 which we can then write as 2 times 3 times 3. 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 7 times 13 and 323 is 17
02:41
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 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
03:16
calendar but number three 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 to more practical matters such as the security of your credit cards which is based on a result on prime numbers that dates back to the 18th century number theory once an abstract branch of
03:47
pure mathematics that was studied for its own sake is now also central to the study of cryptography and to 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
04:18
and i'll also show you two results related to fema third is clock arithmetic and the mathematics of the calendar and finally yet another result of fairmar 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
04:49
straightforward topics so let's start with prime numbers here's a table of the primes up to a hundred it's being produced by an ancient greek method called the sieve of eratosthenes where we first list all the numbers up to 100 then cross out the multiples of 2 that is 4 6 8 etc then the multiples of 3 6 9 12 15 etc actually 6 and twelve have already been crossed out
05:25
then those are 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 relies on a fundamental property of our number system that we can get every number by multiplying primes together for example 60 is 2 times 2 times three times five and that this can be done in only one way apart from the order that the primes appear
05:58
so we could have written 60 as 2 times 5 times 3 times 2 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 2 times 3 times 1 times 1 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
06:30
to make one not a prime but we can never list all the primes because the list goes on forever but how how would we prove this unfortunately given any prime there's no 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 1009 but euclid in his book the elements came up with a very different approach
07:01
here it is in the earliest surviving copy of the elements from ad 888 in the borderline library in oxford and here's an english version of euclid's proof the thing to note is that 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
07:36
call them p1 p2 p3 and so on up to pn 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 1 to it so what can we say about n because it's
08:09
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 2 3 5 and 7
08:40
then n would be their product that's 210 plus 1 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
09:15
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 eleven 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
09:48
such as five that's four plus one thirteen three fours plus one and seventeen four fours plus one and so on so there are infinitely many primes in 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
10:19
and the general result along these lines was proved by the german mathematician lejeune de riesli in 1837 in this tour de force he showed that there are infinitely many primes of the form a n 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
10:50
because four has no factors in common with one or three and if we now take a to b ten and b to be nine which also have no factors in common we see there are infinitely many primes for the form ten n plus nine that is infinitely many prime numbers ending with nine and in the same way there are infinitely many prime numbers ending with one 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 they're named after maram mercen a french mathematician and friar who investigated them in the 17th century if we look at these mercen numbers we'll see that some of them are prime two squared minus one is three two cubes minus one is seven two to the fifth minus one is thirty one
11:58
and two to the seventh minus one is a hundred and twenty seven and these are all primes but other mercen numbers are not prime two to the fourth minus one is fifteen which isn't prime and two to the six minus one is sixty-three two to the eighth minus one is two hundred and fifty-five and two to the ninth minus one is fif is five hundred and eleven and none of these is prime so looking at the powers of two that appear here it's very tempting to believe that two
12:30
to the n minus one is always prime when the exponent the power n is prime here they're 2 3 5 and 7 and that it's never prime when the exponent n isn't isn't prime and here they're 4 6 8 and 9. but is this always the case the answer is partly it's not difficult to show that if n is not prime then 2 to the n minus 1 isn't prime either
13:02
but if n is prime we have to be more careful for example if we take the next prime 11 we have 2 to the 11 minus 1 which is 2 2047. now this may look prime but it isn't it's 23 times 89 so if n is prime then 2 to the n minus 1 may or may not be prime messenger himself came up with a list of primes of this form which is why they're named after him
13:36
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-1 which is a prime number with 39 digits so why are these numbers of interest or are they simply a curiosity it turns out that if we're looking for new primes then mercen primes turn out to be our best bet for example the last 17 primes that have been found
14:08
have all been of this kind including the most recently discovered one in december 2018 which is true to the 82 589 9333 minus one a prime number with almost 25 million digits but another reason for looking at medicine primes is that they turn up in connection with a problem that dates from ancient greek times
14:41
the greeks are interested in numbers which they call perfect numbers whose factors apart from the number itself add up to the original number for example 6 is perfect because its factors are 1 2 and 3 and these add up to six and twenty eight is perfect because its factors are one two four seven and fourteen and these add up to twenty eight the next two also known to the greeks were 496
15:15
and 8128 and then there aren't any more of them until 33 million 550 366. so how did the greeks find these perfect numbers to see why they found them let's factorize them we find that six is two times three which we can write as two to the one times two squared minus one twenty eight is four times seven which couldn't write as two squared
15:50
times two cubed minus one 496 is 16 times 31 which is 2 to the fourth times 2 to the fifth minus 1. 8128 is 64 times 127 which is two to the sixth times two to the seventh minus one and the other one uh thirty three million five hundred fifty thousand three hundred and thirty six is four thousand and ninety six times eight thousand 8 191 which is 2 to the 12th times 2 to the 13th
16:25
minus 1. so in each case is a power of 2 multiplied by a mersenne prime in fact the next one well all of this was known to new to euclid whose 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 two thousand years after euclid then the
16:57
deuter 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 number or numbers they'll be absolutely huge more than 10 to the power 1500 so they probably don't exist but who knows before we leave prime numbers let's explore one more
17:32
type this time introduced by fema 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 is the n plus one so let's look at some of these female found the first few two to the one plus one which is three two to the two
18:07
plus one which is five two to the four plus one which is seven which is seventeen notice that the exponents are powers of two two to the eighth plus one is two hundred and fifty-seven and two to the sixteenth plus one which is sixty-five thousand five hundred and thirty-seven female 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 2 to the 32
18:44
plus 1 is that prime well unfortunately it's a 10 digit number over 4 billion and fairmont's pocket calculator didn't go that far so fairman 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 2 to the 32 plus 1 can be evenly divided by 641
19:17
and later he found a method that gave this answer more quickly but even euler was stuck with the next one 2 to the 64th plus 1 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 worst was to come many other female numbers are now known and none of them has turned out to be prime so fairmar's
19:49
conjecture has turned out to be rather an unfortunate one but all is not lost as farmer primes turned up again but in the most unexpected place the drawing of regular polygons these are polygons where all the size and all the angles are equal the ancient greeks are very interested in trying to construct these whereby constructing they allow themselves to use only an unmarked ruler no measuring allowed and a pair of compasses
20:26
here's how how euclid constructed an equilateral triangle starting with a line a b use the compasses to draw the circle on the left where the center is a and the radius is a b so that gives you the left hand circle then draw the circle on the right by taking the center to bb and the radius is ba and then you have two circles these two circles intersect at the point c
21:02
now a the length a b is the length is the same as ac because each is a radius of the left hand circle and the length b a 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 a with center o and some radius o a then with the compass point a and the same radius mark off the point b
21:38
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 join 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 rule and compasses and he
22:12
also showed how to double the number of sides of a regular polygon so starting with an equilateral triangle we can con with three sides we can construct regular polygons with 6 12 and 24 sides and starting with a square then doubling we can construct regular polygons with 8 16 and 32 size and starting with a regular pentagon we can construct ones with 10 20 and 40 size
22:43
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 7 9 11 13 14 18 or 19 size are any of these possible enter gauss when age only 18 he first showed how to construct a regular polygon with 17 sides he then answered the construction
23:22
question completely by proving a remarkable result that a regular polygon with n sides can be constructed by ruler encompasses if and only if n is obtained by taking some power of 2 multiplied by unequal fairmont primes which is i remind you of the 5 listed here so for example we can construct polygons with 30 sides
23:53
because 30 is 2 times 3 times 5. we can do 32 sides because that's a power of 2 or 34 sides because that's 2 times 17 or 40 sides because that's 2 cubed times 5. but we cannot construct regular polygons with 35 sides because 35 is 5 times 7 and 7 is not allowed or 36 sides because 36 is 2 squared
24:27
times 3 squared and we're not allowed to use 3 twice or thirty seven which is not a female prime anyway or a hundred because the factor five occurs twice so to answer so to answer the question i mentioned at the beginning we cannot draw a regular polygon with a hundred size but it's remarkable that these female primes occur in such a problem let's now leave prima five numbers from for a while
25:01
and look at perfect squares the first ten of these are listed here one squared is one two squared is four three squared is nine and so on and you notice that none of these squares ends with 2 3 7 or 8. and this is true in general because if we square 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 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 1 plus 3 plus 5 is 9 which is 3 squared and so on we can prove this quite easily by arithmetic but more informative
26:06
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
26:40
such as twenty-five 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
27:12
as eleven hundred and eleven one one one one 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
27:47
but k times k plus 1 is the product of two consecutive numbers and if you have 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
28:21
and made of eight lots of ten ten 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 size of a right angle
28:58
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 3 4 5 triangle where 3 squared plus 4 squared is 5 squared that's 9 plus 16 is 24 25. the 5 12 13 right angle triangle with 5 squared
29:31
plus 12 squared is 13 squared 25 plus 144 is 169 and the fifteen eight seventeen triangle with fifteen squared plus eight squared is seventeen squared well two two five plus sixty four is two eight nine 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 3 4 5 triangle
30:06
we can scale up by 10 to get a 30 40 50 triangle with 30 squared plus 40 squared is 50 squared or from 345 we can scale up by 2 to get a 6 8 10 triangle with 6 squared plus 8 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
30:38
will 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 the multiple of four so that c squared would be two more than the 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
31:13
five and twelve fifteen 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 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 2xy 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 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 2xy c is x squared plus y squared where x and y have these properties so let's take some examples for x and y
32:21
if x is 2 and y is 1 then a is 2 squared minus 1 squared which is 3. 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 size three four five if x is 3 and y is 2 then a is 3 squared minus 2 squared which is 5. b is 2 times 3 times 2 which is 12 and c is 3 squared plus 2 squared which is 13 and we get the triangle with size 5 12
32:54
13. and if x is 5 and y is 2 then a is 5 squared minus 2 squared which is 21 b is 2 times 5 times 2 which is 20 and c is 5 squared plus 2 squared which is 29 and we get the right angle triangle with size 21 20 and 29 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 the side of length 29 and we just found one as we've just seen by taking x to be 5 and y to be 2 we found the triangle with size 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 these expressions for a b and c when there's no scaling involved
34:01
but 29 cannot be 2xy 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 5 and y is 2 and we had the solution we had before and if 29 is x squared minus y squared we can factorize that into two factors as shown here
34:37
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 fifteen and y is fourteen it then follows that a is fifteen squared minus fourteen squared which is twenty nine as we expected b is 2 times 15 times 14 which is 420 and c is 15 squared plus 14 squared
35:10
which is 421. so this is the only other right angle triangle with a side of length 29 the size of 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 fema in our study of right angle triangles we've been looking at sums of two squares
35:47
and we might ask what numbers can be written as the sum of two squares for example 41 is 5 squared plus 4 4 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 4n or 4 plus 1 4n plus 1 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
36:20
or four n plus two adding two of those odd numbers so we can rule out any numbers of the form 4n plus 3 such as 43 and we notice also that some numbers are sums of squares in more than one way for example 65 is 64 plus 1 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 a sum of two squares if we can first decide which prime numbers
36:55
are the sum of two squares we've just ruled out all the primes of the form for n plus three but as claimed by fema and later proved by euler every prime number of the form four n plus one can be written as the sum of two squares and moreover this can happen in only one way so here are some examples five is a prime of the four four n plus one five is four plus one thirteen
37:29
is nine plus four seventeen is sixteen plus 1. 29 is 25 plus 4. 40 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 conjectured by fairmont but the other result of fermara i want to mention is his famous last theorem because it was the last of his theorems
38:04
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 squared plus b squared equals c square with a cubed plus b cubed equals c cubed or a to the fourth plus b to the
38:37
fourth is c to the fourth fermar 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
39:11
now female believed that there are no positive number solutions to a to the n plus b to the n is 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 fairmar's conjecture was eventually proved in 1995 350 years after he first mentioned it
39:44
by andrew wiles 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 past then it's five o'clock so ten plus seven
40:26
is five mod twelve it actually turns out to be more convenient to write zero rather than twelve so eight plus 4 is 12 o'clock in other words 8 plus 4 is 0 mod 12. this way of calculating is called modular arithmetic or clock arithmetic and was introduced by gauss in his number theory book of 1801 and more generally we say that a
40:58
is the same as b mod n if a and b leave the same remainder when divided by n so fifteen nine plus six is fifteen fifteen is three mod twelve because they leave the same remainder when you divide by twelve and seventeen is five mod twelve 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
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 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 monday up to day six which is saturday we can then write these statements
42:00
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
42:36
dodson 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 carol's method is based on four numbers which are then added mod seven the first number is the century number
43:08
what century we're 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 carol'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 carol 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 carol 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
44:17
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
44:52
digits of the year which is also 20 for 2020 divided by 12 giving one remainder eight also four divides into eight two times so we have one plus eight plus two and that's eleven for the month number the number for september is five and for the day number 28 is 28. and if you add all these numbers together you get 6
45:25
plus 11 plus 5 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 first of january 2001 was a monday or you can start with any
46:02
any other date whose day you know so you can easily check that the first of february was a thursday now the number of days in any non-leap year is 365 which is one more than the multiple of seven so the first of february 2001 was a thursday first of february 2002 is a friday first of february 2003 is a saturday the 1st of february 2004 is a sunday so that's one answer 2004. also the cycle of days repeats every 28
46:35
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 20 28 years to 2004 gives 2032 2016 2088 so the only years in the century where february has five sundays is 2004
47:06
2032 2060 and 2088. for my final topic i want to look at another result of fermar 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 females 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
47:45
then the result is always exactly divisible by p for example if we choose a to be 8 and the prime p to be 37 then we find without calculating it that 8 to the 37 minus 8 is exactly divisible by 37. and we can also get another version of females result 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 a to the p minus 1
48:20
minus 1 is also exactly divisible by p for example when a is 2 and p is 53 we see that 2 to the power 52 minus 1 is exactly divisible by 53 which we can also write using our clock arithmetic as 2 to the 52 is 1 mod 53 and i'm going to use that result in a minute but before that how do we prove fairmar'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 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
49:30
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 total numbers 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
50:04
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
50:37
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 cars 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 fairmont's
51:15
little theorem where does each card move after the first shuffle you can check that the card originally in position x moves to position 2x or to position 2x mod 53 when 2x is larger than 52. for example the car that starts in position one ends up in position two and the card that starts in position 27 moves to position 54 which mod 23
51:51
mod 53 is position one so the new order in the cards is shown on the right is 27 1 28 2 29 3 and so on to 51 25 52 26. so after one shuffle the card in position x has moved to position 2x mod 53 and after two shuffles it then moves to position four x
52:23
mod 53 and so on so after n shuffles it moves to position two to the n x 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 2 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 2 to the n is 1 mod 53 and we want to find the numbers n for
52:59
which this is true but as we saw before with fairmont's little theorem 2 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 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 this question is 52.
53:35
but the question i posed at the beginning of the lecture was involved shuffling a pack with two jokers so we now have 54 cards and doing what we did earlier tells us that 2 to the n is now 1 mod 55 instead of mod 53. this time we can't use fairmon'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 around this difficulty well if 55 divides exactly into 2 to the n minus 1 then so do 5 and 11 and these are both primes so we can apply fairmont's little theorem to each one telling us that 2 to the 4 is one mod five and two to the ten and two to the ten is one mod eleven how do we combine these raising the first one to the fifth power tells us that two to the twenty is one mod five and squaring the second one tells us um
54:40
the two to the 20 is also one mod 11 and combining these which we're allowed to do tells us that 2 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 that no smaller number of shuffles works so so the answer to our original problem is 20 shuffles raymond can you pass me that piece of paper we've just used fairmont's result that
55:11
the prime p does not divide the number a then h 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
55:45
than the shuffling of cards now just as fairmon's result tells us that the number a raised to the power p minus one is one more than a multiple of 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 total function or phi function denoted at gauss's suggestion by the greek letter phi
56:18
well given any whole number n 5n counts the 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 of the even numbers 2 4 6 and 8 and the numbers 5 and 10 itself so the only numbers with no factors in common with 10 are 1 3 7 and 9 and there are four of them so 5 of 10 is 4. likewise if n is 12 then the numbers would count a one not two three or four five not six
56:50
seven not eight nine or ten eleven not twelve so five twelve is also four we can easily check that for any prime number p 5 p is p minus 1 because we don't count p itself and this tells us that if p is prime then euler's theorem reduces to fair mass theorem which we had above and we can also prove that if p and q are both primes then five their product pq is p minus one times q minus one for example and we'll need this in a
57:22
minute 1073 is the product of the primes 29 and 37 so 5 of 1073 is 29 minus 1 times 37 minus 1 28 times 36 or a thousand and eight so now at last in the last five minutes to our credit cards rsa cryptography is named after the initials of rivest shamir and edelman who found it in 1978 not knowing that it had earlier been invented at bletchley park by cliff
57:55
cox but kept secret now this mo 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 7 and 13 to give 91
58:26
but turning it around factorizing 9107 plus times 13 wasn't immediately obvious and for large primes multiplying is effectively a one-way process like squeezing toothpaste from a 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
58:59
bob first selects two prime large primes with maybe 200 digits each and multiplies them to give the number n is pq in our simplified example p and q were 29 and 37 and n is their product 1073. bob then calculates 5n as we did earlier and we got 1008 and he then chooses a number e with no factors in common with it here he's chosen e to be 11.
59:32
he then publicly announces the two numbers capital n and e but not p and q it's 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 convert converts it to numerical form for example by taking a as one b is two and so on and calls it capital m so m is the message knowing e and capital n she then
01:00:06
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 okay so she knows e and n so she can 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 and 5 n have no factors in common
01:00:36
it can be shown there are numbers oops um so uh because e and five n have no factors in common it can be shown the numbers little m and little n satisfying this equation here so that m times e is one mod phi n and from this he can calculate n so basically there's a method of calculating this number little m in example in our example 11 m was one mod thousand eight and bob can then calculate m to be 275
01:01:12
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 but calculating that calculating e to the m mod n gives alice's message m alice's message is e to the in this case 2 to the 75 mod 1073. don't worry about the details the important thing is the whole process simply relies on two calculations alice
01:01:44
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 your credit card is secure and 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
01:02:16
problems for this year moreover you'll probably lose all your friends as a result so this will solve your christmas present problems for next year too thank you for listening

DOWNLOAD SUBTITLES: