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
Added 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

From Wikipedia, the free encyclopedia

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.

YouTube Encyclopedic

  • 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.
This page was last edited on 14 May 2018, at 21:38
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.