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

Pseudoprimi extra forti di Lucas

Sequenze  Teoria dei numeri 

Se Un è la sequenza di Lucas generalizzata generata da P e 1, con P diverso da 2, Vn è la sequenza associata e D = P2 – 4, dato un numero dispari n che non abbia divisori comuni con D, rappresentiamo n meno il simbolo di Jacobi (D | n), dove Simbolo di Jacobi (D | n) è il simbolo di Jacobi, come k2m, con k dispari: se n è primo, Uk ≡ 0 mod n e Vk ≡ ±2 mod nV2sk ≡ 0 mod n per un intero non negativo s minore di m – 1. Se un numero composto dispari n primo rispetto a D soddisfa una delle due condizioni, n si dice “pseudoprimo extra forte di Lucas” rispetto a P.

 

Tutti gli pseudoprimi extra forti di Lucas rispetto a P sono pseudoprimi forti di Lucas rispetto a P e 1.

 

Tutti i numeri composti non multipli di 3 sono pseudoprimi extra forti di Lucas rispetto a 1, perché in tal caso D = –3 e, dato che se p è primo Simbolo di Legendre (–3 | p) = –1, dove Simbolo di Legendre (–3 | p) = –1 è il simbolo di Legendre, se e solo se p ≡ 5 mod 6:

  • se n è della forma 6t + 1, la sua scomposizione contiene un numero pari di fattori primi (non necessariamente distinti) della forma 6t + 5 e n meno il simbolo di Jacobi (D | n) uguale a n – 1;

  • se n è della forma 6t + 5, la sua scomposizione contiene un numero dispari di fattori primi (non necessariamente distinti) della forma 6t + 5 e n meno il simbolo di Jacobi (D | n) uguale a n + 1.

Nei due casi n meno il simbolo di Jacobi (D | n) è multiplo di 3 e quindi anche k è multiplo di 3, pertanto Uk = 0 e Vk = –2.

 

J. Grantham dimostrò nel 1997 che un intero dispari composto è pseudoprimo extra forte rispetto al massimo a 1 / 8 dei valori di P inferiori, quindi un esame di primalità basato sugli pseudoprimi extra forti di Lucas (con P > 2) è più forte di uno basato sugli pseudoprimi forti di Lucas.

 

La tabella seguente riporta gli pseudoprimi extra forti di Lucas fino a 10000 per P da 3 a 100.

Pseudoprimo

P

25

24

35

34

49

48

55

54

65

64

77

76

85

84

91

90

95

94

121

36, 37, 84, 85

169

6, 29, 34

209

14, 15, 80, 81

289

75, 82

323

7, 10, 20, 35, 41, 47, 54, 64, 69, 75, 86, 88, 98

341

18, 19, 80, 81

361

42, 43, 73, 88

377

7, 36, 47, 55, 84

451

47, 48

529

12, 60, 86

533

45, 68

551

23, 24, 52, 53

559

8, 62, 71

589

80, 81

595

71

629

38, 69, 88

649

25, 26, 84, 85

703

9, 60, 69, 79, 83, 88

781

62, 63

841

80

869

29, 30

899

15, 24, 25, 34, 43, 44, 49, 59, 78, 92

901

14, 18, 54, 67, 71

923

19, 57, 75, 85

961

6, 34

989

4, 14, 52, 57, 79, 82

1007

39, 54, 92

1079

10, 68, 98

1121

33, 34

1189

11, 34, 35

1207

41, 72

1241

48

1247

94

1331

36, 37

1349

16, 41, 96

1369

46, 50, 100

1513

48

1541

32

1639

40, 41

1651

36

1691

12

1711

15, 33, 49, 92, 93

1729

92

1763

8, 10, 19, 20, 53, 55, 62, 63, 74, 81, 98

1769

43, 44, 54, 64, 72, 78

1807

23, 29

1819

47, 67

1829

13, 15, 49, 92

1849

82

1853

18, 86

1855

71

1891

7, 43, 44, 47, 50, 68, 75, 78

2033

47

2047

42, 82, 96

2071

86

2159

13

2171

45

2353

81

2407

26

2449

49, 50

2507

65

2561

57

2581

43, 79

2627

46

2651

51, 52

2701

14

2759

37, 43, 46, 90

2809

67

2849

62, 85, 92

2881

29, 50

2899

81

2911

14

2915

56

3013

56, 98

3053

67

3107

34

3115

36

3403

49, 57, 62, 68, 98

3421

58, 59

3439

58, 77

3485

86

3509

37

3569

15, 62, 73, 76, 91, 98

3599

58, 79

3653

47

3655

71, 99

3683

36

3721

41

3781

61, 62

3809

16

3827

34, 47, 82

3977

30

4031

63, 64

4033

23

4171

67

4181

3, 7, 18, 47, 61, 66, 98

4187

11, 45, 68

4199

33

4321

8, 62

4379

73, 78

4427

56

4531

9, 65, 79

4619

32, 87

4681

28, 50, 78

4687

77

4717

88

4769

56

4823

92

4829

69, 70

5083

33

5111

71, 72

5149

83

5183

25, 87

5191

64

5207

61, 71, 94

5219

86

5251

10, 98

5401

73, 74

5429

43

5461

33, 66, 91

5473

18

5491

75

5543

63

5549

74, 75, 81

5587

8, 43, 62

5611

18

5629

55, 62

5671

47, 67, 100

5699

75, 76

5777

3, 7, 18, 23, 47, 76

5833

26, 60, 86

5963

86

6019

75

6061

14, 15

6119

18

6137

88

6161

78, 79

6319

79, 80

6439

24, 26, 89, 99

6479

15, 80, 81

6497

48

6533

17, 24, 60

6601

6, 34

6641

81, 82

6749

71

6767

14, 87

6821

58, 73

6847

19, 42, 45

6887

67

6895

34

6901

71

6931

9, 79

6943

13, 62, 95

6965

34

6989

14

7055

21, 24

7067

40, 55, 86

7139

84, 85

7181

19, 75

7289

28

7303

19

7409

94

7421

37

7471

38

7801

6, 34, 78

7831

88, 89

7939

20, 69

8119

6, 34

8149

47

8189

90, 91

8203

71

8279

54

8321

15, 42, 66

8339

34, 78

8359

20

8371

91, 92

8399

19, 62

8401

16, 38

8471

79

8473

44, 55, 93

8557

47

8569

12, 98

8639

36, 60, 65, 70

8651

81

8749

85

8777

10, 19, 32, 44, 72, 98

8873

20, 69

8903

40

8909

69

8911

29, 50

9017

87

9073

81, 97

9119

95, 96

9197

21

9211

50, 78

9253

54

9271

87

9287

73

9593

45

9637

12, 50

9659

21

9701

98, 99

9869

14, 64, 75, 77, 89

9899

31, 99, 100

 

Contattami

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