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.