In mathematics, a Lucas–Carmichael number is a positive composite integer n such that
 if p is a prime factor of n, then p + 1 is a factor of n + 1;
 n is odd and squarefree.
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 n^{3} + 1 = (n + 1)(n^{2} − n + 1) is always divisible by n + 1).
They are named after Édouard Lucas and Robert Carmichael.
YouTube Encyclopedic

1/3Views:678 470268 313564 133

Liar Numbers  Numberphile

Something special about 399 (and 2015)  Numberphile

FoolProof 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 BailliePSW 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.