So. Welcome, everyone. I, i work in the mathematics department and occasionally give talks like this. I'm going to tell you a bit about prime numbers today. You might well imagine most people know what a prime number is in case you don't, let me just take you through what the definition is. So prime numbers, something that can't be broken down really into any of the factors.
So that number is like two and three and five and six definitely isn't because it's three times two and we don't usually consider one to be a prime factor. A prime number. That's something I'll tell you a little bit about in a moment. So we start listing these prime numbers. These are what they look like. They seem to go on a little randomly. They go to three, five, seven, 11, 13, 17, and so on.
And then they go on. They get slightly more rare. But the issue is still the list seems to go on for quite a way. And in fact, the list goes on forever. And that's something I hope to prove today might be a little bit hard. So I'll try and take you through through that proof. You might wonder why people are interested in prime numbers.
And that's something I want to give you a sense of today. So if you think about the times, you might have bought something from an Internet company, perhaps like Amazon or something like that, downloaded something or had your parents do it for you. It's actually prime numbers that's making all that secure that your parents credit cards aren't being sort of their numbers aren't being found out by other people.
What makes it all secure is actually prime numbers. I want to say a little bit about that as well. And people also test out really fast computers trying to find the next big prime number. This is the largest known prime number at the moment, too, to the 57 million or so it was found earlier this year. It's got 17 million digits. Okay. So you never run out of prime numbers. They go on forever. And that's the biggest one we know at the moment.
So let's let's see a little bit about why prime numbers are important. So if you if I gave you any number like, well, six is the easy one up there you can write six is two times three, oh, three times two. But that's basically the same thing you can write 24 well, 24 is two times two times two times three. But every number can be broken down into prime numbers. Every whole number can be broken down like that. Some of them, like this big number, are actually just prime and that's just it.
And over numbers like six and 24 can be broken down into smaller things. Do you know how I can get this slide? Is all here still? No. No one knows. Okay. I was going to use the board as well anyway. I'll. I'll. You'll be seeing that will find all numbers in fact can be written in this way so everything can be broken down. And that sort of makes them like the atoms of multiplication, everything. If you think of this lot like a, a numbers, a molecule really can be broken down.
There's certain way into these atoms and 24 can just be written as two times, two times two times three, and only in that way, rarely you could rejig the numbers around and put them in a different order. But really there's just those ways of doing it. Okay. And this is why we sort of think that, one, it really shouldn't be counted as a prime number. So if you if you thought one was a prime number, well, then what I just told you would be wrong. There's you can write six is two times three.
But if one was a prime number you could also Roger is one times two times three. And that would be a different way of doing it. A One times one, times two times three. So I think I've worked out how to get these balls up. Let me. That looks promising. Okay. So because of that, you want to say every number can be broken down in a unique way. And so we don't really want to say one is a prime number. I've got to stand here doing this. Let's just nothing.
That's far enough for now. So how would you find these out? Let me give you an example here. You need to find some patterns area. So if I said how would you break down a number into fact, I'll get this off the board for now. One seven. 1794. Okay. How would you break this down into all its numbers that make it up? And I think you all must know that if that number ends in knots, then it's got a factor of ten in there or a factor of two and a factor of five.
So, you know, if you you can divide this by two and five and you'd get one seven, nine four. And because this number ends in two, sorry, engine four, you know, it's an even number and it's divisible by two itself. And if you break that down further, you're going to get eight, nine, seven. Now, it might not be very apparent to you. So that's divided by two. That was divided by two and five. What about eight, nine, seven?
Does anyone know what eight, nine, seven might be factored by three goes into it because you can. Perhaps he's. I'm not sure how he spelled it. Perhaps the easiest thing is to say, well, nine hundreds of multiple of three three goes into the 900. And this is just 300, 900. So if you divide by three, you get 299. Now, does anyone know what goes into 299? Perhaps. Is that a sneak preview for the next ball? They know. But other than that, this is a bit hard.
And you sat there thinking, is that prime or just three go into it? No, the seven. Well, you'd have to go and check. And actually it turns out that 299 is 13 times 23, but it take you a while to go and check that. So in the end, this is 13 times 23 and you've ended up getting all the factors. We've got a two, a five, a two, a three, a 13 and a 23.
But I hope you can see now that if you're starting to get bigger numbers and obviously doesn't have a two or three that goes in, it might take you quite a while, even with a calculator to work out just how this is going to affect Horizon there. Yet that's one of the ways that the actual Internet security is based, that actually factories in these things can get quite hard if you've got really big numbers.
Anyway, let me let me take you through this proof. I imagine you haven't seen much in the way proof. So let me go through this slowly and I'll try and give you an example on the next slide to show how this works. So, so if you don't quite get all this, don't worry. But this is sort of like a proof from several thousand years ago.
You can see a Greek mathematician called Euclid proved in about 300 B.C. He lived in Alexandria, now in Egypt, and he proved there are actually infinitely many prime numbers. And he had a very clever way of doing these called proof by contradiction. So we sort of like say to ourselves, let's pretend this is false and try and make some conclusions and get to a point where actually we've ended up with some nonsense. So we know we started with a wrong, wrong starting place.
So what he says is, let's suppose there were just finite many prime numbers that the list stops. It doesn't go on forever. It actually stops. And if you've only got so many of those prime numbers, you could list them all. And what is clever idea is if you've just got so many prime numbers like P1, P2 up to P.K., these are all the prime numbers, Euclid fault there might be. What he did is he multiplied them all together and added one OC.
And why he did that is because if you multiply all those numbers together and add one, you've definitely got a number. Now that none of the other numbers that you had divided it. Okay, if you divide them main, they all leave remainder one, none of them go in. But that new number, that really big number he's probably created and doesn't have any of your known prime numbers as factors. So the only possibility is now over. It's prime.
Or if you went and looked at its prime factors, they wouldn't be on your list. You've deliberately found something that's new, gives you a new prime number one way or another. So just in case that might seem a little bit confusing, let's try and do it with an example and see what Euclid's method would have done. So I'm like, Let's say we were really quite lazy and we only fault there were two prime numbers, two and five, which is a very good effort, at least in them all.
But let's say we started with that. Then what Euclid would say is take you two and you five, multiply them together, add one, and that gives us 11. Now, either this new number, 11 is prime, or if we factories 11, we get some numbers that aren't two or five. So in this case, here we get 11 and that's a new prime. So we've got one more on our list. So we might say, okay, maybe we've got them all. Now let's take two and five and 11.
I think I've got them all. Well, Euclid would say multiply them all together, add one and you got 111 and it isn't prime actually 111, but it's prime factors which are three and 37 and new ones not on our list. So if, however, we felt fault, we'd got all the prime numbers, he had a way of saying, multiply them all together, add one, and I'm guaranteed to get you a new prime number. So that means you can never list them all. The list must go on forever.
But anyway, the reassuring thing is we're never going to run out of prime numbers. You can always find bigger and bigger and larger prime numbers. And there's nothing images actually from in this museum. This is you played our statue of Euclid. I guess no one really quite knows what he looks like. And this is a statue of him in the museum. He wrote very famous books called The Elements. And there's been more editions of The Element than probably any book except the Bible.
I mean, this was really the mass book of the maps books until really the start of the 20th century. So a very famous Greek mathematician. So if I if I gave you some examples a bit like this again and said, which of these a prime how easy would some of them be to find? Does anyone want to make any cross a few off my list and say such and such isn't prime going. Okay. And we know that because what what factor of using. Okay.
So even if there's any even ones that we know they're not going to be prime anyone else cross any of the areas of. Yeah. The second one because. Okay. So you know if something ends in five or not, it's divisible by five in any one spot. Any of the others. We are going. Oh, I'd love to have a think about that. It depends. What? Whether 273 is divisible by seven. Yes, it is. It is divisible by seven. Very small. And it's also divisible by three. But good, good sport.
What about any of the others? Yep. Uh, I don't think so. Why do you think it is? Uh, no, definitely isn't, I'm afraid. Isn't divisible by three. Can anyone spot the fall four and what that might be divisible by? Anyone. Because he's got a certain pattern to it doesn't it. 337337. And they won't think of you doing very well. Sorry. 14 no football. All the lost ones are old so 14 could divided also be an even number now 337 you see divides the four four.
Can anyone see how many times 337 goes into the fourth one. No. So 1001 times. It's just that's why it sort of repeated like that. It's 337 times. 2001 is the fourth one. But you can see they're getting a bit harder and. Here are some tricks for simple things. Obviously, it's fairly easy to work out whether something is divisible by two and it's not too hard for four, and eight over five is also fairly easy, mainly because we just use decimal and that's base ten.
So two and five factors of tightness that makes a bit easier if you want to pull the numbers in all the digits in a number like for example, 2732, one few other two and seven and three and two and one. You get what, nine, 12, 14, 15 and because 15 is divisible by three, so is that number. That's a trick you might not have seen before if you had to pull the digits and it's divisible by three that so the number would have been and the same worked for nine as well.
If you add up all the numbers and it's divisible by nine the sum, so would the original number. So that number isn't divisible by nine because 15 is not divisible by nine. But these are just tricks for small numbers. If you wanted to work out some of the others, they're getting a bit hard as it happens. 100 and fall 7 to 9 is prime. It's quite a large prime. It would take you quite a while to work this out.
This other big number, though, is actually not prime, but you'd have to try all the prime numbers until eventually you got to 331 to find a factor that's going to take you quite a while. You'd have to try 66 prime numbers before you actually got to the 67th prime number, and that's going to take you a long time. So find verifying that's prime and showing that isn't would take quite a while and there were only six digits long those numbers.
Okay. So this is what I'm sort of getting out wave with some of these aspects. If you're going to guarantee some of these pricing, you basically have to go to the square root. I imagine you've come across ideas of square roots. So the square root of four is two, square root of nine is three. You'd have to go up to the square root checking all the prime numbers, and if none of them divided it, then it was prime.
So if you wanted to check the 104,729 was prime, you got to try every prime number, really quite a few of them, 66 until you get up to 323. And then by that point, you've actually checked his prime. But that's really quite a hard thing to do. So actually working out in general, this sort of factorisation is quite hard even for computers once the numbers start getting quite big. So that's really why we use it in security.
Here's a novel way, a clever way. Do it due to a Frenchman man from the 17th century fermor. So if a P is a prime, an end is a whole number, then the prime number will divide. And the P minus sign. That's a theorem that you might meet at university if you studied maths there, but we're only really interested in it from a point of view of helping test prime numbers.
So if we just check it here, what his theorem says is that for something like five, which is definitely five, definitely prime five divides two to the power of five minus two. So two to the power, five minus two is 30 to -2 and we get 30 and five also divides three to the five minus three because that's 240 and five will also divide fall to the five minus four because that's 1020.
And so if you turn it on its head and say, well, suppose I had a number that didn't this theorem didn't hold for then I knew it wasn't prime could be useful the oval way round. Well having to check all these factors you could do one possibly big calculation, but one calculation and get it right. And so you could say to yourself, well, if P is prime, it's going to divide two to the P minus two.
So if I have a number that isn't prime or if I have a number N and it doesn't divide two to the N minus two, then I won't be prime. And sometimes that's an easy thing to work through. Then when you've got a large number and you're trying to work out all its possible factors, so that could be a way of crossing it off. The trouble is there are some nasty numbers out there that still satisfy all these tests. So we thought we'd call these things pseudo primes, and they do this.
They satisfy all this without being prime themselves. It won't be very obvious, but 561 is one of these numbers, so 561 satisfies all. This Theorem 561 would always divide added to the 561 minus sign, but it isn't itself prime. So there are some annoying numbers out there that sort of like even if you checked with this, you wouldn't be 100% sure they were prime. You just you'd think they were probably prime. But there are annoyingly 100 there are infinitely many of these false primes out there.
So actually working out whether some of these prime are not can be quite, quite hard. There are ways of quickly showing something isn't, but there are these false primes out there. Let me change topic a little bit here, first of all. So that's so picture of wiles. This is on true now? I'm afraid so. So the new maps built in which you're actually going to I think after this or some of you it's called the Andrew Wiles building.
And the Andrew Wiles building was named unsurprisingly after Andrew Wiles, who is here doing Master Oxford. He's the man who proved Fermat's Last Theorem, which was one of the really famous theorems of mathematics that been unproved for 350 years. And he came along and proved it in the nineties. But so you may well be seeing the new Andrew Wiles building after this. Fermat was an important mathematician in the 17th century.
Let's change topic a little bit now and think to ourselves, how is this going to be useful? Well, I'm talking about in the real world because you might be thinking prime numbers are nice enough, but what point are they? Well, actually, you use them a lot without really knowing. It's like I say, if ever you buy anything off the Internet, then you basically are using prime numbers.
So what's the setup in the Internet? You've got yourself your computer and you sort of like on the Internet with a Internet company. How are they going to be able to get from you, your or your parents credit card number to them without anyone that saying, you know, intercepting the communication or anyone who would like to steal your computer or something like that. How can you be sure that your credit card number will be safe?
And you got to remember, there are millions and millions of people out there using the Internet all the time to buy things. Well, there are always all sorts of problems with communications in front of you if you want to and code sorry. If you want to read a good book on this, there's a book by Simon Singh. Just call the code book. It's a very good read for finding out about how people used to communicate in secret over the years.
It's not it's not hugely mathematical, but there's. So it's a very good read. And so some of this detail will be in that book as well. So how might you do this? If you think to yourself, I'd like to keep a secret, but I want to, you know, share it with a few friends, but only those friends so that it really is secret amongst us, but no one else. Well, they used to do this many, many years ago by just using a very simple cipher. What you might do is you've got this message you want to send.
What you could do is just change every letter in some way that you was agreed. Okay. You and all your friends would know that this was how you were going to communicate. You were going to scramble your message by taking a word and swapping letters, for example. Let me give you an example here. So what you do is at the top here, you've got yourself what's called the key.
Whenever you see a nay, you're going to replace it by a G. Whenever you see a B, you're going to replace it by a P. Whenever you see your name, you're going to replace it by a Q. So if I get a phrase like Oxford Mathematics, if I've done this right. O became L and X became W and F became N and so on. But if you sort of like manage to, oh, if you lost this message or your friends lost it. Anyone just picking this up, would it know what they said?
Okay, this would be a scrambled message and they wouldn't know anything about what you've been trying to say to one another. The trouble is, once you start saying a lot to one another over, people could stop making guesses as to what the how it got scrambled. Because the I mean, there's all sorts of problems here. One is, how do you carefully get this private key to all your friends?
And then if you keep communicating enough, people can start making guesses as to what you might have been writing. So if I had a page, you know, quite a long bit of text and I used my key to scramble it all, sent it to you, but you accidentally got intercepted. What what letter do you think might appear most in the scrambled, uh, scrambled work? Can anyone make a guess? If I was using this copier, what do you think would appear most? G. G. You're going for G because. H on the ray.
He's a very common light. That's a good suggestion. There would be a lot of GS, but it wouldn't be the most common one. Does anyone know? It would be J? But there would be a lot of GS, but the probably be most j's because E's the most common letter in the English alphabet. Does anyone know what the second most common is? No. Afraid not. If we could be a while. I suppose we have to have this. It's gone. No, no, it's actually t. T is the next most common one.
But you can see you're already guessing the way people are. If you saw a lot of JS, you'd be thinking, maybe that came from me. Maybe that came from T. And then if you saw, like saw a lot of things that were maybe T something e you might be thinking to yourself, that's perhaps an H that was the something between them. This is what Phumzile call frequency analysis. So here are the how common the English letters are.
So you can see E appears most commonly at 12.7% of the time on t is the next most common one at 9.1. But as common as someone said, and this is also pretty common as well. So there's you could sort of once you add a lot of text, you could start making educated guesses. You wouldn't want to just go in randomly and start thinking this might be that and this might be that, but you could do some frequency analysis.
So it was actually Islamic mathematicians around 800 A.D. that actually started being able to break down this code. So you can't just use a set, especially in this day of modern computers. You can't just sort like use a SCI for the way they used to do back in Roman times or something like that. It would just be much too easy to crack. So you don't have to be a bit smarter.
Also, if you were sort of like an Internet company, perhaps someone like Amazon or something like that, they've got millions and millions of customers, even if they came up with something a bit better than this. Are they really going to have to send all this to all the customers around the world and be sure that everyone sort of like taking good care of it and not leaving it on the bus and various things like that.
They're really going to have to come up with something better than that. So this is this has always been an issue of what I call private keys. How do you get the key to your friends? Because if if maybe one of your friends isn't not trustworthy or they lose it all, it just gets intercepted. All your enemies. Because we might be talking about this at wartime. All your enemies can now have it. And these are either competitor companies or their enemies at war time.
Security is a major issue. You know, we've we've, you know, personal details with secrets, with things like that could be majorly important. This information gets kept secret. So these are guys. So we've asked Jemmy and Adam, and they gave their initials to what is basically the most used bit of mass really, I guess in the world today. It's a mass or it's a large part of the mathematics behind Internet security.
If you give over your credit card details, send it on to some Internet company, it would be they sell some version of this. That's basically keeping it a secret. It's actually it's reasonably new mass because this came in 1977, which I guess might seem a long time ago to you people. But yeah, I remember 1977, and that's quite new for mathematics. 1977, they came up with this idea. It uses what I told you about earlier Fermat's Little Theorem.
So it's 17th century maths and the Chinese remainder theorem, which is even older maths. So the actual maths behind this, you could explain to Fermat. I need to understand it. Fine. What he'd be astonished about is how you've got to know about prime numbers that are like hundreds and millions of digits long. He'd have no idea about the modern computer age. He wouldn't know how you'd be able to come up with a prime number of 17 million digits, like we mentioned earlier.
So I'm going to tell you a little bit about how prime numbers are used in this. So this is sort of the we don't really want to use a private key system. We want to use a public key system. It's a bit better. So what the Internet company does is tell all its customers or really the customers computers, how they're going to be able to scramble their message so that you can send on your credit card details in a careful way.
You won't be able to unscramble them, but you will be able to scramble them. And that's quite, quite so. So what they do, the Internet company sends to your machine something called the public key. They don't mind if it gets lost the Internet company, because all it is is a means of scrambling. Okay. Then your computer gets it. You go and you buy what you want on the Internet and you send your details on.
And only the Internet company knows how to scramble it, unscramble it, decrypt it is a fancy word. Okay. And what makes this secure and what makes this basically mean that no one's going to be able to break it is if you multiply numbers together, that's easy. Any computer can do it quite quickly, even if the numbers are huge. But if you're going to have to raise it, then it takes a long, long time.
Okay. So if I gave a computer a very large number and said, please go and work out its factors, especially if there were many of them and the factors were big, it might sit there for ages and ages and years and years and in fact, millennia and millennia before we actually came up with the answer. So that's why the system secure. So if you multiply two large numbers together, it's easy.
If you then gave the computer that product and said find them, then it might sit there working for a long, long time. And this is what's called a one way function where it's very easy to go one way, an incredibly hard, at least computation wise to come backwards. So let me give you a few more details here.
So what what goes on in your computer is the Internet company gives you all computer, just two numbers and an E. And actually what goes on in the computer is very simple, is called the encryption power. And the number is huge. It might be like a thousand digits long. And it's only got two factors. He's got two prime numbers as its factors. All this system is still a cipher. It's like taking those 26 letters we had before and moving them around and rearranging them as 26.
But we're not using 26 anymore. We're now using N. And so N is about ten to the power of a thousand, a huge, huge number. And so if you thought to yourself, you know, where am I? E's on my TS amongst these ten to the thousand numbers, you just can't do frequency analysis anymore. It's just too, too big. You're going to have to find other ways of doing it. So it's still a cipher, but we're using a number much, much bigger than 26 now.
And all your computer does. I mean, it might be explained a bit more. Is something called clockwork arithmetic or modular arithmetic that I've just explained in different ways here. You want to send them your credit card details? Let's say this is some number and and I'm probably going to be less than nine. But if not, you could send it by beat your message. So let's say M is bigger. That is less than. All your computer does is take that number E that the Internet company gave it.
Raise it to the power e divide by the number n and you get some remainder. It goes so many times does and and that leaves some remainder. And the remainder is just what gets sent off. So it's very big numbers are involved, but the actual maths is really quite simple. You raise it to the power e you divide by N and whatever the remainder is you send on this is now your scrambled message and if someone intercepted it, it would just be gobbledegook to them. They wouldn't know anything about it.
Maybe there were people there thinking I could break that. That would be easy enough to break. So let's talk about cracking it. How would you crack this? Let me actually let me go back. One slide here. If you've got any public key system, what you have told people how to do is encrypt. That's a bit like giving someone half of an English French dictionary. Okay, let's say I gave you the English French half of the dictionary. And I said to you, What does this mean? What does your de mean?
And Thursday. Okay. How long do you think it would take you not knowing that and we've only the English French. But what would you have to do to work out? Jeopardy meant Thursday. Why would it take you a while? Yeah. You'd have to just keep looking. You wouldn't know where to start. But in principle, if you sat there and sat there and sat there and eventually got to TS, then you'd work out that Jody met Thursday but would tell you ages.
So if I gave you the English French half of the dictionary and said, make the other half, you could tell you a long, long time. But if someone tells you how to encrypt or change something into a different language, you always have in principle a way of getting it back. But that's going to have to take you a long, long time for this to be secure. And it would take you a long, long time because you'd have to sort of like take in words.
All I know is I've been turned to add numbers and then you'd have to work out all these calculations and then sort of alphabetise the other half to get back. That's going to take for ages. Another thing you might try and do is just actually work out what the factors of that end is. The end is this thousand digit number somewhere in your computer. If you can go and work how those factors are. You can break the code. But that's going to take you pretty much forever. Okay.
And the Internet company tomorrow or probably even later this afternoon, are going to be using different prime numbers. So you don't have the rest of the universe to sort of like work this through. You've only got sort of like perhaps the next ten, 15 minutes before another set of numbers are used. So it's pretty secure. At the offer end, the the Internet company has got what matters. They've got the factors. Then they know those. And because of that, they can work out the decryption power.
So when you've sent on your scrambled message, see? Okay, here. Then at the other hand, they just raise it to a decryption power d known only to then divide again by N and as if by magic. But it's just Fermat's Last Theorem and the Chinese remainder theorem. When you divide by an impulse out, they now know your credit card details what you want to buy, where they need to send it. All the information comes out, so it's really just quite simple maths that is going on.
Okay. So I can say here, if you wanted to go and try and crack this, then you could do this by trying to do all the scrambling, rearrange the scrambling, and make the other half of the dictionary. That would take forever, pretty much all you could try to rise in this number, and that's pretty much going to take forever as well. So it's a very, very secure system. Okay. Let me sort of like draw this to a close a bit by talking a little bit about how the primes are distributed.
So I hope you now at least see that primes can be really quite useful. They're funnier primes and it's very easy to ask very hard questions about them. You can do all sorts of things. Like if you look at if you look at this list, you can see you've got three and five next to an end of a five and seven, 11 and 13, 17, 17 and 1929 and 31. These are what are called twin primes, apart from two no number, that's even as prime.
So all primes are old apart from two. And this means that the nearest two of them could be together is just a difference of two. And you can see quite a few examples here, 29 and 31, 71 and 73. And these are called twin primes. And people want to know whether or not they're infinitely many twin primes. And no one knows. No one's close to knowing, really at the moment there's been progress with that problem.
Just this year, a lot of mathematicians got excited about various results related to that, but no one actually knows whether there are infinite many, many primes, just two apart. So it's very easy to ask very hard questions about these sorts of things. One thing we do sort of understand, though, is just how frequent they are because they might look a bit random, but long term we can actually get a fairly good sense of how how often they pop up.
And that's something called the Prime Number Theorem. Okay. And my guess is you might not have met this idea before, so let me just tell you what a factorial is. You've probably seen it on your calculator. Uh, is this an and then an exclamation mark? And if you've never been sure what it was, it just multiplies all the numbers up to it together. So three factorial is one times. Two times three, which is six.
Four factorial is one times two. Three times four, which is 24 and five factorial c is 126. Factorial 720. Why am I mentioned in this is because you can use this idea to show there are quite large gaps amongst the primes. If I said to you, find me 100 numbers, one after another that none of them are prime. I'm not. You might be thinking to yourself, that's impossible. Around 100 numbers, one after another. They aren't prime, but there are gaps like that in amongst the primes.
And you can actually see that using this idea. Okay. So there are large gaps in the prime, in the primes, as large as you want them to be. If I if I take an factorial plus two and you're some number two was in that product ten factorial. So two divides N factorial and factorial is one times two all the way up to end. And if I add to this number, still going to be divisible by two. If you look at the next number, if any is bigger than three, then three will divide and factorial.
Okay. It'll also divide three. So the next number is divisible by three. And if it's bigger than four or five or more than four will be in four factorial. Go into four factorial and also be divisible by four. So the first number's divisible by two. The next one by three. The next one by four. If I choose n as large as I want it to be. Here is a list of numbers. One after the over. I have no primes.
So, for example, here, five factorial plus 222 is divisible by 223 is divisible by 320 fours, divisible by four, 125 divisible by five. So if I used N is 101, I'd actually have 100 numbers one after ANOVA, none of which are prime. So there's gaps as large as you want in amongst the prime numbers. But at the same time, we sometimes think that infinitely often there's two just next door to one another. So you get you get odd sort of like spurts of prime numbers and then huge gaps.
Here's another thing you might have seen on your calculator, but perhaps never quite know what it was. So this is called the Aladdin function. Okay. Which is a I'm not going to use that much here, but Aladdin is basically stands for natural logarithm. You can work it out on your calculator. That's a graph of what it looks like. Aladdin of One is not a line of larger numbers. Aladdin of a number between two and three is one.
You can work out a few things about it, but I'm just going to use it here to tell you a little bit about primes. It's got these nice properties. It basically takes multiplication and turns it into additions. So if you take a line of a product, you just add the values of that line. And it's not a line. Numbers aren't very big compared with what originally you had. So why a line of a million is just 13.8. Okay.
So it takes quite large numbers and gives you quite small ones, but you don't really need to know much about it. But it does come up in this next theorem. So this is gives you a sense that actually primes do follow some sort of pattern. You might think to yourself, how many numbers are there? How many prime numbers are there? Less than a million or a billion or a trillion. And you can get pretty good estimates for that without actually working them all out.
And that's what mathematicians suspected since 18th century proved at the end of the 19th century, that if you have want to work out how many prime numbers there are less than, say, about a billion. You work out a billion divided by a line of a billion. And that would give you a pretty good estimate of how many prime numbers there are without having to work them all out. And in fact, here's a picture of the graph. Okay.
So I'm not sure you can actually see this in this slide, but there are actually two lines there. So the top line, the blue one, is how many prime numbers there are less than all these numbers and the N divided by. So X divided by a line of X is the estimate. And it's always a bit of an underestimate, at least initially. Okay. So it gives you a bit of an underestimate here, but it makes a pretty good estimate of how many they are. And long term, they're basically pretty much the same number.
Well, what this twiddle is means on the previous slide is that if you divide how many prime numbers there are, by your estimate, long term, that number goes to about one. So pretty much is 100% long term, but it's estimated. Anyway, I'm almost done here. So let me let me try and give you a sense of, first of all, how hard it is to factor ice things. Using this prime number theory. From what I said to you, how many how many prime numbers am I going to have to try?
How many factorisation I'm going to have to try to actually work out, say whether something in the order of ten to the 20 is actually prime. So I've got a 20 digit number, not a thousand digit number like we had in our say, a 20 digit number. To test whether it's really prime or not. I've got to try potentially all the prime numbers up to its square root. All right.
And if you use the previous theorem to work out how many calculations I'd have to do, it ends up being about two RU ten divided by this number. And so just to give you an example here, if I was trying to work out whether a number with 20 digits actually was prime, and let's say it was I'm going to try all these that many calculations to actually work out where it was. I'm just for this 20 digit number. I've got to do 400 million. Trial factorisation of quite large numbers. Okay.
So just a 20 digit number is going to be quite hard to check. It's prime. I might have to do 400 million calculations to actually work that out. There are over all sorts of ways of trying to test this, but it's always going to be a hard thing to check. So as I said here, there's actually it's actually quite easy to make claims about prime numbers that might be very hard to prove.
Here are a few things we do know to be true. If you take all the prime numbers on and they are inverses, so I'll call a reciprocal. You take all the sums. That's some keeps getting bigger and bigger and bigger and basically goes off to infinity. So that becomes large. And Euler prove that if you take any what's called arithmetic progression. So something like perhaps three, seven, 11, 15, 19, 23 and so on. So you start with a certain number and then you have a common difference all the time.
Now you can see here I've got various things that are prime. And I've got various things that aren't. Well, there's got to more primacy about the next one isn't. A man called Jerry Schley. He went and proved all these sequences will always have infinitely many primes in them. Okay, so for any sequence like that, yes, you'll get some things that aren't prime, but there will be infinitely many primes in those. He proved that.
And a man called Chevy chef who was a Russian mathematician, he showed that there'll always be a prime number between any N and it's double. So if I gave you ten and 20, there's a prime number between those. If I gave you a hundred and $200, always be a prime number between those, perhaps lots of them. But you proved that. Always be a prime number before between those and then just to finish. Uh, these are things we don't know.
Can't every hole number, every even number be written as the sum of two primes? If I gave you ten, you can write it as three and seven. If I gave you 12, that's five and seven. If I gave you 20, this is three and 17. Oh, you know, no one knows if every eve number can be written like that. We we've checked it up to about sort of like ten to the 20 or something like that. It's probably true, but only takes one counterexample to show it isn't.
And no one knows the answer. No one knows whether it's possible to write every eve a number as the sum of two primes. Keep trying if you wish. But people, like I say, have gone up to ten to the 20, and that hasn't. I'm no one's found one yet. And then there are over important types of primes, primes of this form two to the P minus one, and no one knows whether they're infinitely many of those either. So problems are an important thing.
The very easy to describe in some ways very useful in things like Internet security. But it's also very easy to ask very hard questions about them. So I think I'm going to finish there. Is anyone got any questions they might want asking? Like you say, if you want to find out more about how to create secure codes and how to scramble messages carefully, then Simon Singh's books, very good. If you want to have a read on this further.
Okay. I think I'll hand over to Zarina if she's in the audience. Thank you.