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

Pseudoprimi di Eulero – Jacobi

Teoria dei numeri 

Se n è un primo dispari, Congruenza soddisfatta dai numeri primi e dagli pseudoprimi di Eulero – Jacobi, per qualsiasi intero positivo b non multiplo di n, dove Simbolo di Jacobi (b | n) è il simbolo di Jacobi. Si dicono “pseudoprimi di Eulero – Jacobi”, ma anche talvolta semplicemente “pseudoprimi di Eulero”, rispetto alla base b i numeri composti dispari, che soddisfano la stessa congruenza.

 

Tutti gli pseudoprimi di Eulero – Jacobi sono anche pseudoprimi di Eulero (I) nella stessa base, ma non viceversa; per esempio, 341 e 5461 sono pseudoprimi di Eulero (I) in base 2, ma non pseudoprimi di Eulero – Jacobi; quindi verificare la congruenza costituisce un esame di primalità più forte che verificare se Congruenza soddisfatta dai numeri primi e dagli pseudoprimi di Eulero.

 

Tutti gli pseudoprimi forti rispetto a una base sono anche pseudoprimi di Eulero – Jacobi, come dimostrò Selfridge; il viceversa vale sempre se lo pseudoprimo diviso per 4 dà resto 3 (Malm 1977) oppure se la base non è residuo quadratico di p (Pomerance, Selfridge e Wagstaff, 1980).

 

Nel 1986 Kiss, Phong e Lieuwens dimostrarono che per ogni base esistono infiniti pseudoprimi di Eulero – Jacobi, con ogni numero fissato di fattori primi.

 

Tutti i numeri di Mersenne composti Mp con p primo e tutti i numeri di Fermat composti sono pseudoprimi forti in base 2 e quindi pseudoprimi di Eulero – Jacobi nella stessa base.

 

Nel 1976 D.H Lehmer dimostrò che per ogni numero composto vi è almeno una base rispetto alla quale non è pseudoprimo di Eulero – Jacobi e nel 1977 R. Soloway e V. Strassen dimostrarono che un numero composto n può essere pseudoprimo di Eulero – Jacobi rispetto al massimo a φ(n) / 2 basi minori di n e prime rispetto a n, quindi non esiste tra gli pseudoprimi di Eulero – Jacobi un analogo dei numeri di Carmichael o degli pseudoprimi assoluti di Eulero, pseudoprimi in tutte le basi prime rispetto al numero.

 

Nel 1980 Monier dimostrò che il numero di basi rispetto alle quali un intero composto dispari n è pseudoprimo di Eulero – Jacobi è esattamente Formula per il numero di basi rispetto alle quali un intero composto dispari n è pseudoprimo di Eulero – Jacobi, dove δ(n) vale:

  • 2, se e2(n) – 1 = e(n);

  • 1 / 2, se esiste un primo p che divide n, tale che ep(n) sia dispari e e2(p – 1) < e2(n – 1);

  • 1 altrimenti.

In queste formule ep(n) indica l’esponente della massima potenza di p che divide n e Formula per la definizione di e(n).

 

I numeri composti n che sono pseudoprimi di Eulero – Jacobi rispetto a φ(n) / 2 basi, il massimo numero possibile, sono i numeri di Carmichael speciali, ossia i numeri interi n non multipli di quadrati, tali che p – 1 divida (n – 1) / 2 per ogni primo p che divide n (Lorenzo Di Biagio, 2011).

 

Il test di primalità di Solovay – Strassen si basa sul verificare se un numero è pseudoprimo di Eulero – Jacobi rispetto a varie basi: scegliendo k basi a caso, la probabilità che un numero composto superi l’esame è minore di 2n e aumentando il numero delle basi, si riduce a piacere la probabilità di errore.

 

La tabella seguente mostra gli pseudoprimi di Eulero – Jacobi minori di 10000 nelle basi da 2 a 100.

Base

Pseudoprimi di Eulero – Jacobi

2

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481

3

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911

4

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911

5

781, 1541, 1729, 5461, 5611, 6601, 7449, 7813

6

217, 481, 1111, 1261, 1729, 2701, 3589, 3913, 5713, 6533

7

25, 325, 703, 2101, 2353, 2465, 3277, 4525

8

9, 65, 105, 273, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 6305, 6601, 7161, 8321, 8481, 9265

9

91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911

10

9, 91, 481, 1729, 4187, 6533, 6601, 8149, 8401

11

133, 793, 2047, 2465, 4577, 4921, 5041, 5185

12

91, 133, 145, 247, 385, 1649, 1729, 2041, 2233, 2821, 3553, 8911, 9073

13

85, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637

14

15, 65, 793, 841, 2465, 2743, 3277, 5713, 6541, 7171, 7449, 7585, 9073

15

1687, 1729, 1921, 3277, 6541

16

15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919

17

9, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171

18

25, 49, 65, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6601, 7345

19

9, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997

20

21, 671, 889, 1281, 1729, 1891, 2059, 2761, 3201, 5461, 6601, 7999

21

221, 703, 793, 1045, 3781, 7363, 9061

22

21, 91, 169, 345, 485, 1183, 1247, 2047, 2465, 5551, 7665

23

169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805

24

25, 175, 553, 949, 1541, 1729, 1825, 1975, 2701, 4537, 6931, 7501, 9361

25

217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881

26

9, 25, 27, 45, 217, 225, 475, 703, 925, 1065, 3825, 5041, 5425, 8029, 9073

27

121, 133, 259, 365, 481, 703, 1649, 1729, 1891, 2821, 3281, 4033, 4921, 5461, 7381, 7585, 8401, 8911, 9809, 9841, 9881

28

9, 27, 261, 361, 529, 785, 1431, 2041, 2465, 3201, 3277, 4699, 5149, 7065, 8401

29

15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841

30

49, 133, 341, 403, 637, 871, 901, 931, 1729, 2059, 2077, 3277, 4081, 4097, 6031, 6409, 8023, 8401, 9881

31

15, 49, 133, 481, 931, 2465, 6241, 7449, 8911, 9131

32

25, 33, 205, 217, 325, 385, 465, 561, 793, 825, 1025, 1057, 1065, 1105, 1353, 1525, 1705, 1729, 1905, 2047, 2465, 2665, 2761, 3277, 4033, 4141, 4681, 5185, 5425, 6601, 6665, 6697, 7905, 8305, 8321, 8481, 8569, 9017, 9073

33

545, 1057, 1105, 1417, 1649, 2501, 5461, 5713, 5833, 6533, 6601, 9073, 9265

34

33, 35, 165, 273, 671, 1001, 1157, 2059, 2071, 2937, 4033, 6533, 6945, 7861, 8911

35

9, 153, 561, 1261, 2701, 2871, 5083, 5161

36

35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881

37

9, 451, 469, 589, 685, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271

38

39, 85, 91, 289, 469, 481, 871, 1445, 2553, 4033, 4681, 5461, 6031, 6097, 6931, 7449, 7585, 7613, 8177

39

133, 1561, 2047, 2465, 3053, 3439, 4141, 4237, 5921, 6533, 6601, 8149, 8911

40

39, 121, 289, 451, 533, 703, 1561, 1729, 1921, 4961, 5729, 6601, 7111, 7201, 9881

41

21, 105, 231, 671, 703, 841, 1065, 1281, 1387, 1417, 2465, 2701, 3829, 8321, 8911

42

451, 529, 1247, 1541, 1765, 1807, 1991, 6001, 7421, 9773

43

21, 25, 185, 385, 925, 1541, 1729, 1807, 2465, 2553, 2849, 3281, 3439, 3781, 4417, 6545, 7081, 8857

44

9, 15, 45, 301, 703, 1035, 1937, 1981, 2047, 2465, 4005, 4097, 4633, 6273, 8385

45

481, 1541, 1729, 1981, 2059, 2071, 3289, 4921, 6601, 8321, 9361

46

9, 15, 45, 341, 657, 721, 781, 949, 1729, 1891, 1991, 2071, 2117, 2201, 2465, 3201, 4033, 4089, 4187, 4465, 4681, 5611, 8321, 9211

47

65, 85, 221, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465, 5461, 5865, 6305, 9361, 9881

48

49, 259, 427, 481, 637, 703, 793, 1729, 1813, 1891, 1921, 2257, 2305, 2353, 2821, 2989, 4465, 5185, 5951, 6697, 6721, 8869, 8911, 9881

49

25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321

50

49, 51, 561, 697, 793, 817, 833, 1281, 1649, 1729, 2009, 2041, 2501, 2701, 3201, 3913, 4753, 6601, 8041, 8113, 9073, 9577

51

25, 65, 175, 325, 1247, 1681, 2059, 2653, 2821, 3053, 5461, 8365, 9475

52

51, 671, 901, 1891, 2653, 2705, 3201, 4081, 5151, 7201, 8911, 9773

53

9, 27, 91, 117, 1405, 1441, 1541, 2209, 2529, 2863, 3367, 3481, 5317, 6031, 9409

54

55, 265, 341, 361, 385, 1247, 1729, 2701, 2863, 4033, 4069, 4081, 7957, 9073

55

9, 27, 153, 801, 1027, 1387, 1513, 2821, 4033, 6533, 9773

56

55, 57, 247, 285, 1027, 1501, 1705, 1891, 2465, 3193, 3277, 3553, 5665, 6441

57

25, 65, 125, 325, 1001, 1625, 2047, 2465, 2911, 3193, 4187, 7501, 7613

58

57, 133, 671, 1141, 1441, 2065, 3009, 3097, 3365, 3781, 7471, 7991, 8119, 8749, 9073

59

15, 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465, 3097, 4681, 5611, 6191, 7421, 8149, 9637

60

481, 841, 1729, 1891, 3133, 3277, 3601, 3661, 4577, 4777, 6533, 8917

61

15, 217, 341, 1261, 2465, 2701, 2821, 3565, 3661, 6541, 6601, 6697, 7613, 7905

62

9, 21, 63, 91, 231, 361, 549, 679, 793, 1261, 1281, 1541, 2465, 2871, 3367, 3439, 3845, 4141, 4577, 5185, 5917, 6533, 6697, 6921, 8827

63

529, 703, 841, 1147, 1985, 2071, 2465, 2509, 3379, 3683, 4033, 5161, 5461, 6119, 6533, 6943, 7711, 9073

64

9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945

65

33, 289, 703, 1111, 1387, 1891, 1921, 2701, 4291, 6533, 6697, 8321, 9537, 9809

66

65, 469, 1105, 1541, 2071, 2911, 4291, 6097, 6601, 6953, 7969, 9211

67

33, 49, 217, 561, 703, 1105, 1309, 1519, 1729, 2209, 2245, 5797, 6119, 7633, 8029, 8371

68

25, 49, 69, 125, 185, 217, 247, 361, 637, 871, 925, 1225, 1273, 1519, 1771, 2185, 2413, 2725, 2821, 4033, 4625, 4693, 4921, 5425, 5713, 7705, 8241, 9025

69

35, 85, 91, 133, 247, 361, 1105, 1387, 1729, 1921, 2527, 3605, 4693, 5713, 6161, 6643, 7345, 8911

70

69, 169, 341, 377, 561, 671, 949, 1891, 2769, 3053, 3201, 4901, 6001, 6177, 7449, 9301, 9361

71

9, 35, 45, 1387, 1729, 1921, 2071, 2209, 2321, 2701, 4033, 6541, 7957, 8365, 8695, 9809

72

85, 305, 451, 793, 1037, 1105, 1241, 1387, 1729, 2465, 4381, 5185, 5257, 6601, 6697, 8449

73

9, 65, 205, 259, 333, 369, 533, 585, 1441, 1729, 1921, 2553, 2665, 3439, 5257, 6697

74

15, 25, 75, 91, 325, 365, 427, 511, 793, 949, 1387, 1525, 1729, 1825, 4453, 4577, 5551, 6541, 6643, 7421

75

91, 133, 247, 289, 427, 481, 793, 1159, 1729, 1849, 1891, 2257, 2413, 2701, 2813, 2821, 4033, 4681, 4921, 5551, 7957, 8113, 8911, 9211

76

15, 25, 75, 77, 385, 949, 1113, 1369, 1417, 1825, 1891, 1925, 2289, 2701, 4033, 4681, 5777, 6533, 6545, 7957, 8365, 8745, 9211, 9673

77

39, 1387, 1513, 2465, 2701, 2965, 3705, 4371, 5073, 5461, 5713, 6541

78

77, 341, 451, 703, 1247, 1271, 1849, 1921, 2047, 2465, 3097, 4187, 4345, 6031, 6085, 6601

79

39, 49, 65, 91, 301, 559, 637, 1649, 2107, 2465, 2701, 3913, 6305, 6533, 7051, 8321, 9881

80

9, 27, 49, 81, 169, 301, 481, 1729, 2107, 3321, 3439, 5461, 6253, 6401, 6601, 7107, 7821, 8261, 8281, 8769

81

91, 121, 205, 511, 671, 697, 703, 949, 1105, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8911

82

9, 25, 27, 81, 91, 225, 511, 891, 925, 949, 1345, 1525, 1541, 1825, 2025, 2257, 2465, 2871, 5611, 6533, 6643, 6725, 7957, 8321, 9919

83

21, 65, 231, 265, 561, 689, 703, 861, 1105, 1241, 1729, 2665, 3277, 3445, 4411, 5713, 6601, 6973, 7665, 8421

84

85, 1615, 2501, 2981, 3145, 5713, 6973, 7141, 8401

85

21, 341, 781, 1591, 2201, 3097, 3913, 4859, 7141, 7161, 7613, 8299

86

85, 87, 145, 493, 595, 1729, 2465, 3091, 5365, 7397, 7483, 9673

87

247, 403, 559, 589, 817, 1333, 1661, 1705, 3785, 5461, 6533, 7471, 7483, 7657, 8401, 9881

88

87, 247, 403, 589, 1891, 2047, 2465, 2581, 2611, 4331, 4849, 4921, 6697, 7657, 7745, 9073

89

9, 15, 45, 153, 169, 1035, 1441, 2097, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711

90

91, 1001, 1157, 1729, 2413, 6281, 6601, 8321, 8401

91

9, 15, 45, 369, 1065, 1387, 2651, 3015, 4005, 4141, 4187, 5963, 6969, 9361, 9881

92

91, 93, 105, 301, 451, 559, 1001, 1209, 1393, 1729, 2465, 2587, 2701, 3731, 3781, 3913, 4033, 4371, 4641, 4681, 6697, 7161, 7905, 7957, 8321, 8465, 8557, 8841, 8911

93

25, 325, 793, 865, 1105, 1525, 1771, 2047, 2737, 3913, 4187, 4325, 4465, 4945, 5185, 5713, 5833, 6697, 6721, 8321, 8557, 8743, 8911

94

93, 95, 121, 133, 403, 465, 1105, 1729, 2465, 2977, 3053, 3565, 5685, 7099, 7471, 7905, 8743, 8911, 9073

95

1891, 2821, 2977, 3131, 3421, 4089, 6161, 8249, 9121

96

95, 485, 679, 1273, 1729, 2641, 2701, 4187, 5617, 6097, 9121, 9217, 9313

97

49, 105, 341, 469, 481, 949, 973, 1065, 2701, 3283, 3577, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313

98

9, 33, 85, 99, 153, 561, 565, 873, 1017, 1105, 1649, 1705, 1921, 2465, 2701, 3007, 3201, 3277, 3585, 3729, 6817, 7345, 7471, 8321, 9605, 9703, 9881

99

25, 49, 169, 245, 361, 377, 775, 1225, 2413, 2465, 3277, 3565, 4225, 4901, 5611, 6889, 6943, 7825, 8281, 8321, 8695, 9425, 9703

100

9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911

 

Contattami

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