Lucas–Carmichael number

Transcription

>> DR GRIME: Let's have a look at one of these tests that they have, that they apply to see if a number is prime or not. Well we're going to use a fact I have mentioned before when talking about primes and we're going to use Fermat's Little Theorem. It's a theorem about prime numbers and what it says is that if you have a number which I'll call 'a' and I'm going to raise it to a power 'prime number' so that's called 'p prime', and I subtract the original number then I say that this is divisible by p. There you go. So if a number is prime that's always true for whatever number 'a' you pick. So, let's do an example of this, let's pick a prime. We know 5 is a prime, is it? Isn't it? Yeah, OK. So 5 is a prime, so let's use that and we'll pick, well, let's see. 1⁵, that's going to be easy. 1⁵ - 1 = 0. Is it divisible by 5? Yes, we say 0 is divisible by 5. What about 2? 2⁵ - 2 to get 30. Hey, and that's divisible by 5 as well. Let's just finish it off. 3⁵ - 3, that's 240 so these are all divisible by 5. 4⁵ - 4, divisible by 5 again. What about 5? Yeah, well I think this one's a bit more obvious, so that's divisible by 5 too. And that's always going to be true if the number is prime. And this is what Fermat proved in the 17th century, this is absolutely true for all primes. Let's try another number, I'll try another number with you. I'm going to try the number 341. Does that pass my test? 2³⁴¹ - 2. That's my test. Now that's going to be a really large number. Computers can have methods that make this easier so that's going to be a really large number. I'm not going to write that down. Huge number, but I can tell you now that this number is divisible by the number we're testing. It was 341. Thumbs up. Yeah, great. So it's passed the test. Let's try another one, let's try another test. Do it with 3 then. If we do this, 3³⁴¹ - 3. Is this divisible? And this is where it fails the test. So this one is not divisible. Now, if it's not divisible that tells me it's a composite number. There only needs to be one exception, it's very easy to fail this test. The more you pass, the more evidence you are, that you are a prime and if you fail at all then you are a composite number. Only composite numbers fail. If you have a composite number and it passes the test here, this number 2 in this case is called a Fermat liar. Ooooh, it's not really prime, it's lying. It tells me it's prime and it's not. Naughty! This number here 3, which actually shows that it was composite after all, is called a Fermat witness. The innocent bystander. He goes in to a witness protection program in case 2 comes and chases after him, yeah. Brady, you ask a good question though. What would happen if there was a number that was composite that passed every test up to the size of the number. Is it possible? Yes it is. There are numbers that will pass this test for every test you apply. Those are called Carmichael numbers, they have a name. The first Carmichael number is 561. So what that means is 2⁵⁶¹ - 2 is divisible. 3⁵⁶¹ - 3, that passes the test. So does 4. And all the way down to 560 to the power 561 and it passes the test each time. >> BRADY: Must be prime! >> DR GRIME: Must be prime! Must be prime! Unfortunately, it's not. 561 is equal to 3 by 11 by 17. >> BRADY: Those are cool numbers. >> DR GRIME: Those are really cool numbers and there infinitely many Carmichael numbers. The third Carmichael Number is mathematician's favourite 1729. Nice. >> BRADY: Lovely. >> DR GRIME: Lovely. Now, what do you reckon Brady? Do you think this is a good test, or not? >> BRADY: Well, until you told me about Carmichael numbers I thought it was a good test. Now I think it's almost useless if you're looking for perfection. Well it is useless. >> DR GRIME: Yeah, well, it's not perfect. You're absolutely right. So, if you checked all numbers less than 25 billion, the number of numbers that would fail the test if you used 'a' was 2, alright? If 'a' was 2. The number of numbers that fail that particular version of that test is 2183 out of 25 billion. That's just using 2. So only a small fraction fail this test, or give you things that you don't want. Tell you that you have a prime when you don't have a prime. And you can apply other numbers anyway, so to pass this test is actually quite a high bar. >> BRADY: So it is a good test. >> DR GRIME: So, it's a fairly, yeah. It's a fairly good test. Now there are other tests though, there are better tests that use pretty much the same idea. Almost exactly the same idea so if you understood that you'll understand the other tests as well. There's one called the Baillie-PSW test, pretty much uses the same idea as that. Actually uses two tests in conjunction so you have to pass them both. Yes, if you pass that test you're probably a prime. In fact, they have found no counter examples. So anything that passes the test so far has actually been a prime. There's been no sneaky composite numbers. No counter example to it. And they've checked large numbers for this. If you do find a counter example, if you find a cheeky composite number that passes the test, the authors originally offered a prize. You could win $30. $30 could be yours. Now don't worry, since then the amount of the prize, it's gone up since then. You can now win over $600. $620 in fact. Think of that. Think of that. Think what you could do with that money. Ooh, you could buy yourself a choc ice every day. Every day for a year. Twice on Sundays. >> DR GRIME: In 2002, they published, or mathematicians published a new method to test for primes and finally they found a fast way that was 100%. This is now one of the latest things.