Name: 世界最大の素数をどうやって見つけたのか - Numberphile (How they found the World's Biggest Prime Number - Numberphile)
Uploaded: 2021-01-14T10:15:40.000Z
Duration: 12 min 32 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

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,

to 不定詞

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.

If anyone is curious, it's 1,490 pages, but I've double-sided them.

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! 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 then I check: is ten a multiple of 5?

And because ten is two times five, ten is a multiple of five, I know five is a prime number.

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.

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

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.

And you see if that is a multiple of the number you're checking, seven. And it is!

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

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.

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.

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.

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.

So actually that is not a good way to go about it.

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.

you just need to keep track of the remainder

And we can do a quick example, if you want, to show how that works.