To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

# Lucas–Carmichael number

In mathematics, a Lucas–Carmichael number is a positive composite integer n such that

1. if p is a prime factor of n, then p + 1 is a factor of n + 1;
2. n is odd and square-free.

The first condition resembles the Korselt's criterion for Carmichael numbers, where -1 is replaced with +1. The second condition eliminates from consideration some trivial cases like cubes of prime numbers, such as 8 or 27, which otherwise would be Lucas–Carmichael numbers (since n3 + 1 = (n + 1)(n2 − n + 1) is always divisible by n + 1).

They are named after Édouard Lucas and Robert Carmichael.

• 1/3
Views:
678 470
268 313
564 133
• Liar Numbers - Numberphile
• Something special about 399 (and 2015) - Numberphile
• Fool-Proof Test for Primes - Numberphile

#### 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.

## Properties

The smallest Lucas–Carmichael number is 399 = 3 × 7 × 19. It is easy to verify that 3+1, 7+1, and 19+1 are all factors of 399+1 = 400.

The smallest Lucas–Carmichael number with 4 factors is 8855 = 5 × 7 × 11 × 23.

The smallest Lucas–Carmichael number with 5 factors is 588455 = 5 × 7 × 17 × 23 × 43.

It is not known whether any Lucas–Carmichael number is also a Carmichael number.

## List of Lucas–Carmichael numbers

The first few Lucas–Carmichael numbers (sequence A006972 in the OEIS) and their prime factors are listed below.

 399 = 3 × 7 × 19 935 = 5 × 11 × 17 2015 = 5 × 13 × 31 2915 = 5 × 11 × 53 4991 = 7 × 23 × 31 5719 = 7 × 19 × 43 7055 = 5 × 17 × 83 8855 = 5 × 7 × 11 × 23 12719 = 7 × 23 × 79 18095 = 5 × 7 × 11 × 47 20705 = 5 × 41 × 101 20999 = 11 × 23 × 83 22847 = 11 × 31 × 67 29315 = 5 × 11 × 13 × 41 31535 = 5 × 7 × 17 × 53 46079 = 11 × 59 × 71 51359 = 7 × 11 × 23 × 291 60059 = 19 × 29 × 109 63503 = 11 × 23 × 251 67199 = 11 × 41 × 149 73535 = 5 × 7 × 11 × 191 76751 = 23 × 47 × 71 80189 = 17 × 53 × 89 81719 = 11 × 17 × 19 × 23 88559 = 19 × 59 × 79 90287 = 17 × 47 × 113 104663 = 13 × 83 × 97 117215 = 5 × 7 × 17 × 197 120581 = 17 × 41 × 173 147455 = 5 × 7 × 11 × 383 152279 = 29 × 59 × 89 155819 = 19 × 59 × 139 162687 = 3 × 7 × 61 × 127 191807 = 7 × 11 × 47 × 53 194327 = 7 × 17 × 23 × 71 196559 = 11 × 107 × 167 214199 = 23 × 67 × 139 218735 = 5 × 11 × 41 × 97 230159 = 47 × 59 × 83 265895 = 5 × 7 × 71 × 107 357599 = 11 × 19 × 29 × 59 388079 = 23 × 47 × 359 390335 = 5 × 11 × 47 × 151 482143 = 31 × 103 × 151 588455 = 5 × 7 × 17 × 23 × 43 653939 = 11 × 13 × 17 × 269 663679 = 31 × 79 × 271 676799 = 19 × 179 × 199 709019 = 17 × 179 × 233 741311 = 53 × 71 × 197 760655 = 5 × 7 × 103 × 211 761039 = 17 × 89 × 503 776567 = 11 × 227 × 311 798215 = 5 × 11 × 23 × 631 880319 = 11 × 191 × 419 895679 = 17 × 19 × 47 × 59 913031 = 7 × 23 × 53 × 107 966239 = 31 × 71 × 439 966779 = 11 × 179 × 491 973559 = 29 × 59 × 569 1010735 = 5 × 11 × 17 × 23 × 47 1017359 = 7 × 23 × 71 × 89 1097459 = 11 × 19 × 59 × 89 1162349 = 29 × 149 × 269 1241099 = 19 × 83 × 787 1256759 = 7 × 17 × 59 × 179 1525499 = 53 × 107 × 269 1554119 = 7 × 53 × 59 × 71 1584599 = 37 × 113 × 379 1587599 = 13 × 97 × 1259 1659119 = 7 × 11 × 29 × 743 1707839 = 7 × 29 × 47 × 179 1710863 = 7 × 11 × 17 × 1307 1719119 = 47 × 79 × 463 1811687 = 23 × 227 × 347 1901735 = 5 × 11 × 71 × 487 1915199 = 11 × 13 × 59 × 227 1965599 = 79 × 139 × 179 2048255 = 5 × 11 × 167 × 223 2055095 = 5 × 7 × 71 × 827 2150819 = 11 × 19 × 41 × 251 2193119 = 17 × 23 × 71 × 79 2249999 = 19 × 79 × 1499 2276351 = 7 × 11 × 17 × 37 × 47 2416679 = 23 × 179 × 587 2581319 = 13 × 29 × 41 × 167 2647679 = 31 × 223 × 383 2756159 = 7 × 17 × 19 × 23 × 53 2924099 = 29 × 59 × 1709 3106799 = 29 × 149 × 719 3228119 = 19 × 23 × 83 × 89 3235967 = 7 × 17 × 71 × 383 3332999 = 19 × 23 × 29 × 263 3354695 = 5 × 17 × 61 × 647 3419999 = 11 × 29 × 71 × 151 3441239 = 109 × 131 × 241 3479111 = 83 × 167 × 251 3483479 = 19 × 139 × 1319 3700619 = 13 × 41 × 53 × 131 3704399 = 47 × 269 × 293 3741479 = 7 × 17 × 23 × 1367 4107455 = 5 × 11 × 17 × 23 × 191 4285439 = 89 × 179 × 269 4452839 = 37 × 151 × 797 4587839 = 53 × 107 × 809 4681247 = 47 × 103 × 967 4853759 = 19 × 23 × 29 × 383 4874639 = 7 × 11 × 29 × 37 × 59 5058719 = 59 × 179 × 479 5455799 = 29 × 419 × 449 5669279 = 7 × 11 × 17 × 61 × 71 5807759 = 83 × 167 × 419 6023039 = 11 × 29 × 79 × 239 6514199 = 43 × 197 × 769 6539819 = 11 × 13 × 19 × 29 × 83 6656399 = 29 × 89 × 2579 6730559 = 11 × 23 × 37 × 719 6959699 = 59 × 179 × 659 6994259 = 17 × 467 × 881 7110179 = 37 × 41 × 43 × 109 7127999 = 23 × 479 × 647 7234163 = 17 × 41 × 97 × 107 7274249 = 17 × 449 × 953 7366463 = 13 × 23 × 71 × 347 8159759 = 19 × 29 × 59 × 251 8164079 = 7 × 11 × 229 × 463 8421335 = 5 × 13 × 23 × 43 × 131 8699459 = 43 × 307 × 659 8734109 = 37 × 113 × 2089 9224279 = 53 × 269 × 647 9349919 = 19 × 29 × 71 × 239 9486399 = 3 × 13 × 79 × 3079 9572639 = 29 × 41 × 83 × 97 9694079 = 47 × 239 × 863 9868715 = 5 × 43 × 197 × 233

## References

• Richard Guy (2004). "Section A13". Unsolved Problems in Number Theory (3rd ed.). Springer Verlag.
• Lucas–Carmichael number at PlanetMath.org.