If you want to check a normal number if it's prime, a small one, you just see if any numbers divide into it. You can get slightly smarter. You've only got to check if primes divide into it, and you've only got to check if primes up to the size of the square root of the number you're checking or not. And so you got a few shortcuts you can make. This number, however, when you're finding ... look at the size of this thing, right! There's no way you could just go through and check every conceivable prime factor of this number to see if it itself is prime. In fact, there's a much more clever way of doing it. We'll, I have successfully divided it up by three, so I don't know if that technically doesn't count. I mean, I've taken a prime, and I've split it up into three parts. Albeit, not three equal parts. If anyone is curious, it's 1,490 pages, but I've double-sided them. so it's about 250 pages a volume. Okay, so you want to find primes. Previously I showed you the Lucas numbers. Which I prefer to Fibonacci numbers. These are the vastly superior "Luca" or "Lucas" numbers. They start with 1 and 3 instead of 1, 1 Fibonacci and they carry on like this. You get 4, you get 7, you get 11, I need to make sure I get this correct. otherwise it'll be very very embarrassing. What's that going to be? Fift... 47. So there's the first one, two, three, four, five, six, seven, eight, nine, ten. So Brady, can you give me any number, one to ten inclusive. What would you like, one to nine, - or ten? What do you want? Five Five! All right, we're going to see if five is prime. Now a lot of people at home, because people who watch Numberphile tend to be into mathematics know that five is prime - spoiler. Let's say we don't know. Say "I don't know if five's prime or not? Let's double check." I'm going to count along to the fifth Lucas number. One, two, three, four, five. I'm going to subtract one off that number. And if I subtract one I get ten. And then I check: is ten a multiple of 5? And it is. And because ten is two times five, ten is a multiple of five, I know five is a prime number. WHAT?! Probably. So, give me another number that's not prime... just you know six.
-six
-SIX! I wonder if six is prime. Let's check six. One, two, three, four, five, six. Take one off. Seventeen. Seventeen is not a multiple of six. Six is definitely not prime. And so this Lucas test will rule out a number that's not prime. So you can comprehensively prove that a number is not prime by using this test, even though you don't know what any of the factors are. If it does pass then we call it a Lucas pseudoprime. It's very likely it's going to be prime. It's not guaranteed at this point. This is a very easy test. It's a good first filter to check if a number is prime or not, and you don't even have to look at its factors. So for a number this big, first of all we need something a little bit more clever and secondly we want to be sure. Right so we want a similar test which guarantees that it's prime if we find it. And that's what I'm going to do now. All right, for the big fellows we're going to need a different sequence and again it's our friend Lucas. What a guy. What a mathematician. And a guy called Lehmer who we never met because he lived much later after him and he was a French and American but together they came up with this method which uses the following sequence. You start with four this time and after that you square the previous number and subtract two. So four squared is sixteen. Sixteen subtract two is fourteen. And then we do the same thing. We square fourteen, and we subtract two and you get 194. You then square 194, subtract two, you get 37,634. They get big very quickly. So the next one's a bit of a monster. So you got from 37 thousand something something something up here to one billion, four hundred and sixteen million, three hundred and seventeen thousand, nine hundred and fifty four. And then now, you can feel what's going to happen, we're about to square this guy. We're getting roughly twice as long each time. The next number, hold on, is two billion .... it escalates very quickly and you get some massive numbers in there. and actually it becomes incredible very unwieldy very quickly to do anything with it. We'll fix that problem in a moment. Let's start by proving the number is prime. We're going to use a small Mersenne prime on this sequence to start with. I'm going to use seven because it is one less than two cubed. So the way you check a Mersenne prime against this list, is you take the power, which for seven is 3. You subtract one off that which is two. And you find what's in the second position in the list. So the second number is fourteen. And you see if that is a multiple of the number you're checking, seven. And it is! Look at that. So fourteen is a multiple of seven, so seven is definitely prime. ??? Let's recap on that very quickly. If you've got two, to some p prime power there minus one and that equals some mystery number. If the p minus oneth position in this sequence is a multiple of that number, that number is definitely prime. And there's no ifs or buts or maybes. We know it is absolutely prime. And if it's not a multiple of that number, it's definitely not prime. And so this is a primality test. You can check if a number's prime or not. And you never have to look at its factors. This is what Lucas used. He managed to prove that two to the one hundred twenty seven minus one is definitely definitely prime by finding the one hundred and twenty sixth term in this sequence. and proving it was a multiple of that number that came out the other side. He also amazingly managed to prove that two to the sixty seven minus one is not prime. But he never found a single factor for that number. He was able to prove this is not prime without finding a number that divides into it. I think that amazing. It was much later on, decades later, someone actually found what the factors were. We knew they were there. We just didn't know what they were. But we knew it wasn't prime. That prime is actually the biggest prime that was found by hand. All primes after that have been done by computer. So to check this number here, what we'd have to do is continue the sequence, find the seventy four million, two hundred and seven thousandth, two hundred and eightieth position, and check if it was a multiple of this monstrosity. Now that actually is going to take a ridiculous amount of computing power. You can see how big these numbers get. They're going to get ludicrously large. So actually that is not a good way to go about it. Let's make our life easy. Because when you're search through for this guy here all you care is whether or not the seventy four million, two hundred and seven thousand, two hundred and eightieth position is a multiple of it or not all you really want to know are the remainders once you've divided by this number. And so as you go along you don't have to keep track of the entire Lucas Lehmer sequence you just need to keep track of the remainder mod this number as you go along. So you can keep simplifying it down each step of the way. And we can do a quick example, if you want, to show how that works. One of my most absolute favourite Mersenne primes is eight thousand one hundred and ninety one which is two to the thirteen subtract one And so to check this number we'll have to find the twelfth term in the Lucas Lehmer sequence. But we only have to find it mod 8191. So to start with it's the same. You'd have four, you'll have to square that you'll get fourteen, you'll square that you get 194 let's get these right. Then the next number should be 37,634 but that's bigger than the number we care about And so actually we need the remainder of that number once we've divided through this number. In that case it's only four thousand, eight hundred and seventy. That's easier. And then we square that, subtract two, get the remainder once we remove multiples of the number we care about and you end up with three thousand nine hundred and fifty three followed by five thousand nine hundred and seventy. And you can see this time, these are staying much more manageable in size. Okay then, one hundred and twenty eight. And the twelfth term is zero. If you square that, subtract two you get a multiple of eight thousand one hundred and ninety one. and because that zero with no remainder, we know whatever that massive ridiculous number should have been in the sequence it's definitely a multiple of eight thousand one hundred and ninety one. Therefore that is definitely prime. And we didn't have to check a single factor of that number. Okay, so this is what the computer at the university of Missouri did. Although obviously it does a slightly more efficient version of this and there's nice things you can do with the way it handles the binary versions of these numbers Anyway, it's a fancy version of going along this sequence finding the result modulo this ridiculous number But you can do that just by subtracting it off until you get a number smaller than it so that's not so bad Once it got to that position it looked at the answer there was no remainder and normally there's a remainder the vast majority of the time you'd check a number of this size spend a month on it. The computer would get to the end and go, "Aww, there's a remainder." Well, it's a computer. It's got no emotions. It would just send back the remainder to the central server. On this occasion it was zero. The computer had no idea what it had done. It sent that off back to the central server and that was it. We had found the biggest prime number known to humankind. So the problem is this method only works for Mersenne primes. But the problem is that every single time you do it it's a month of processing work all right. So you think, how many - I mean this is millions and millions of months but obviously we only have to check the way Mersenne primes work and there are some fantastic Numberphile videos on Mersenne primes You only got to worry about prime values up here. If this hadn't been prime if that had not worked the next one we checked would have been the next prime up after this. So we're gradually ticking up through those primes. You're right, in the bigger scheme of things there aren't that many. But it's still it's a month every time you want to check one, so. I mean definitely, everyone download GIMPS, the computer program, and run it and maybe you'll be the person who finds the next one of these. Matt if they put some of the world's more high-powered computers onto the case here for like a few months, would they burn through this. Like is it silly that we're just using little small computers in universities? Yeah, it's a very good point. If we had very big high powered computer like if Google went "yeah, you know what guys? Borrow the server." You know what, I reckon if Google wanted to they could just go and find the next one. If they just say, "everyone just stop searching for a day, we've got something to do with our computers." But then again, I mean, what are they going to achieve, they're going to find a bigger one and then everyone's like, "Oh okay." and start searching for the next one. I mean the point of this is kind of the hunt. And the fact that thousands of people run the program and any one of those people could find the next one that, for me, is the beauty of the project. It could be anyone sitting at home running their computer could make a substantial find like this, they could contribute something to mathematics And for all of eternity you would be the human that found prime number What would it mean to you if your computer found the next big one? OMG! I would be so excited if I found the next- I would - I would absolutely love to find it. Very small confession; I don't run GIMPS on my computer. I run a competing prime number searching outfit called PrimeGrid. And PrimeGrid searches for other types of primes. They look for like Germain primes and other ones. And so currently GIMPS has the top fifteen biggest primes, they've found them all. PrimeGrid, is a lot less likely you'll find a prime, which is a bit sad for me. But if you do find, in a few categories, they're going to come in at something crazy big. And so I like- I play for the underdog. So I support PrimeGrid because I like the fact that they are doing different types. I mean these GIMPS guys are just in it for glory. They're just going for easy - low hanging, easy big ones. They're just picking them off one after another and getting all the recognition. But you know, I like the fact that, as we speak, at home my computer is doing maths so I don't have to. So the question everyone has is "what does it begin and end with?" Ending, I don't have. Everyone loves the last number. But the trouble with the last number is you know it's not going to be an even number, you know it's not going to be a five, you know it's not going to be a zero. Turns out it's a one. There it is.
