Don't take life too seriously: it's just a temporary situation

Carmichael – Lucas (numeri di)

Teoria dei numeri 

Dato un intero positivo D della forma 4k o 4k + 1, un numero naturale composto n si chiama “numero di Carmichael – Lucas rispetto a D” se è primo rispetto a D e pseudoprimo di Lucas rispetto a qualsiasi coppia di interi P, Q, tali che D = P2 – 4Q, con n e Q primi tra loro.

 

Mentre i numeri di Carmichael sono pseudoprimi di Fermat rispetto a qualsiasi base, i numeri di Carmichael – Lucas sono pseudoprimi rispetto a qualsiasi sequenza di Lucas (fissato D).

 

Il primo a considerarli fu Hugh C. Williams, nel 1977, che dimostrò che se n è un numero di Carmichael – Lucas rispetto a D, per ogni suo fattore primo pp meno Jacobi(D, p) divide n meno Jacobi(D, n), dove Simbolo di Jacobi(D, n) indica il simbolo di Jacobi.

Di conseguenza se n è uno pseudoprimo di Lucas rispetto a 1, è un numero di Carmichael – Lucas rispetto a 1.

 

Dai lavori di Williams segue che se Scomposizione di n come prodotto di fattori primi:

  • se n è un numero di Carmichael – Lucas,Minimo comune multiplo di p(k)^(e(k) – 1) * (p(k) – (D | p(k))), calcolato su tutti i primi p(k) che dividono n divide n – (D | n), dove Simbolo di Jacobi(D, n) indica il simbolo di Jacobi;

  • se n è un numero di Carmichael – Lucas, n non è multiplo di quadrati;

  • viceversa se n non è multiplo di quadrati e Minimo comune multiplo di p(k)^(e(k) – 1) * (p(k) – (D | p(k))), calcolato su tutti i primi p(k) che dividono n divide n – (D | n), n è un numero di Carmichael – Lucas;

 

Un numero di Carmichael – Lucas rispetto a n è anche un numero di Carmichael – Lucas rispetto a 4n.

 

Mentre i numeri di Carmichael devono avere almeno tre fattori primi, esistono numeri di Carmichael – Lucas che sono il prodotto di due soli fattori, come 323 (rispetto a 5).

 

La tabella seguente mostra i numeri di Carmichael – Lucas rispetto a n minori di 106, per n fino a 20.

n

Numeri di Carmichael – Lucas

1

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633

4

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633

5

323, 6601, 6721, 11663, 17119, 19043, 30889, 34561, 35207, 39203, 51983, 90287, 104663, 121103, 138601, 142883, 150121, 163081, 186961, 199801, 252601, 266071, 268801, 283361, 381923, 399001, 506521, 512461, 655201, 685583, 736163, 798571, 852841, 925681

8

35, 385, 899, 2915, 6083, 6601, 10403, 15841, 18241, 20909, 22499, 23219, 34561, 37345, 39203, 45961, 49105, 52633, 53041, 60059, 72899, 74305, 86241, 107801, 133951, 135749, 155819, 160921, 162401, 186961, 194833, 196811, 203699, 213443, 283361, 311905, 315001, 344641, 362881, 410041, 427349, 430417, 469201, 501337, 502945, 675683, 700321, 837899, 966779, 980099

9

1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 658801, 670033, 748657, 825265, 838201, 852841, 997633

12

35, 143, 323, 385, 455, 595, 665, 899, 935, 1045, 1295, 1547, 1729, 1763, 2639, 2737, 2821, 2915, 3289, 3599, 3655, 3689, 4355, 4465, 5005, 5183, 5291, 6083, 6479, 6721, 7021, 7055, 8099, 8569, 8855, 8911, 9215, 9361, 10153, 10403, 10439, 10465, 11305, 11663, 11951, 15841, 17119, 17423, 17641, 18095, 18239, 19043, 19981, 20705, 20909, 20999, 22499, 22607, 23219, 23435, 25415, 29315, 29341, 30745, 30889, 31535, 32399, 34561, 34595, 35207, 36863, 37259, 37345, 38665, 39203, 44099, 46079, 46189, 46657, 47879, 49283, 51359, 51983, 52633, 52649, 53041, 54839, 55981, 56581, 57239, 57599, 63503, 63973, 66385, 66563, 67199, 68255, 70741, 71497, 72215, 72899, 73439, 73535, 73645, 74305, 74399, 76589, 76609, 76751, 78913, 79523, 79883, 80011, 80189, 81719, 82621, 90287, 91945, 94393, 94535, 97343, 103285, 104195, 113183, 113221, 115921, 117215, 118405, 120581, 120959, 121103, 122617, 122759, 126217, 128843, 133951, 135749, 138565, 138601, 141155, 146329, 147455, 150121, 152279, 155701, 158401, 160921, 160979, 162719, 163081, 163799, 166439, 166463, 168299, 172081, 176399, 185003, 185185, 186623, 188461, 191101, 191807, 192151, 194327, 194545, 195299, 196559, 199801, 207901, 207935, 208559, 209077, 213443, 216359, 223901, 230159, 230399, 248941, 254881, 256139, 256409, 265895, 268801, 270865, 272483, 273239, 289007, 290339, 293761, 294409, 303031, 311905, 314821, 316511, 317735, 324899, 328321, 334153, 340561, 348517, 352079, 352835, 359999, 362881, 364895, 369721, 374543, 381923, 388079, 391391, 396253, 396899, 399001, 403651, 404639, 412163, 418285, 430199, 432181, 435455, 435599, 436645, 442513, 446039, 455039, 464185, 483479, 485459, 488881, 491855, 492803, 495935, 506521, 508679, 512461, 516559, 521101, 530881, 545905, 547561, 553679, 558145, 560735, 566137, 570505, 576719, 582001, 590519, 592703, 597793, 628705, 630721, 635999, 638495, 644221, 646415, 651419, 651937, 653939, 655201, 656099, 658801, 663299, 664631, 670033, 675683, 679535, 683279, 683353, 685583, 709019, 716579, 718201, 721259, 725903, 736163, 741169, 741311, 745199, 745921, 748657, 753059, 761039, 776567, 777923, 782101, 785915, 792901, 802655, 809999, 812581, 824879, 825265, 827099, 837865, 837899, 838201, 843695, 848521, 860161, 867359, 872423, 876095, 880319, 884305, 895679, 898703, 903959, 913031, 924373, 925681, 930097, 941545, 953281, 955031, 966779, 973559, 976981, 977185, 991799, 997633

13

1763, 3599, 19043, 22847, 24769, 39203, 46079, 67199, 79523, 85281, 117215, 122617, 146329, 164641, 186623, 191101, 223901, 230159, 241535, 432181, 481151, 495935, 507529, 516559, 558145, 651419, 675683, 685583, 753059, 860161, 895679, 919201

16

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633

17

143, 1045, 1763, 3289, 4355, 4991, 8569, 10153, 12719, 29315, 30745, 47879, 49105, 51983, 72899, 73645, 121103, 122617, 170819, 176399, 186623, 196559, 199199, 207901, 223901, 272483, 321937, 334153, 362881, 364895, 446039, 485459, 495935, 558145, 570505, 679535, 685583, 736163, 776567, 777923, 785915, 798571, 966239

20

323, 6601, 6721, 11663, 17119, 19043, 30889, 34561, 35207, 39203, 51983, 90287, 104663, 121103, 138601, 142883, 150121, 163081, 186961, 199801, 252601, 266071, 268801, 283361, 381923, 399001, 506521, 512461, 655201, 685583, 736163, 798571, 852841, 925681

 

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.