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

Pseudoprimi di Eulero (I)

Teoria dei numeri 

Se n è un primo dispari, b^((n – 1) / 2) ≡ ± mod n per qualsiasi intero positivo b non multiplo di n; si dicono “pseudoprimi di Eulero” rispetto alla base b i numeri composti dispari che soddisfano la stessa congruenza.

 

Se un numero è pseudoprimo di Eulero rispetto a una base, è anche pseudoprimo di Eulero rispetto alle potenze di quella base.

 

Tutti gli pseudoprimi di Eulero sono anche pseudoprimi di Fermat nella stessa base, ma non viceversa. Per esempio, 645 è pseudoprimo di Fermat in base 2, ma non pseudoprimo di Eulero in base 2.

Tutti gli pseudoprimi di Eulero – Jacobi sono anche pseudoprimi di Eulero nella stessa base, ma non viceversa.

 

La tabella seguente mostra gli pseudoprimi di Eulero fino a 10000 nelle basi fino a 100.

Base

Pseudoprimi

1

Tutti i numeri composti dispari

2

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

3

121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 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

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

6

185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365

7

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

8

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

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, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401

11

133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113

12

65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073

13

21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637

14

15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073

15

341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073

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, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171

18

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

19

9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997

20

21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999

21

65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061

22

21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453

23

33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805

24

25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361

25

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

26

9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073

27

65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881

28

9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841

29

15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841

30

49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881

31

15, 49, 65, 133, 185, 481, 931, 1729, 2317, 2465, 2553, 4921, 6241, 6289, 6601, 7449, 8911, 9073, 9131

32

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

33

545, 1057, 1105, 1417, 1649, 1729, 2465, 2501, 4033, 4681, 5461, 5713, 5833, 6533, 6601, 7861, 9073, 9265

34

21, 33, 35, 65, 77, 105, 165, 273, 385, 671, 1001, 1045, 1065, 1157, 1281, 1729, 2059, 2071, 2145, 2937, 3201, 3605, 4033, 5161, 5785, 6533, 6945, 7861, 8911, 9073, 9345

35

9, 153, 341, 561, 1261, 1581, 1921, 2701, 2871, 3601, 5083, 5161, 7969

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, 57, 133, 217, 301, 451, 469, 589, 685, 801, 817, 1065, 1233, 1273, 1333, 1729, 1881, 2077, 2413, 2465, 2881, 3781, 3913, 4521, 5073, 6097, 6601, 7657, 7809, 8905, 9271

38

39, 65, 85, 91, 185, 289, 469, 481, 561, 871, 1105, 1221, 1445, 2465, 2553, 2821, 3145, 3585, 4033, 4681, 5461, 6031, 6097, 6931, 7449, 7585, 7613, 8177, 9073

39

133, 341, 1561, 2047, 2101, 2465, 3053, 3439, 4141, 4237, 5921, 6533, 6601, 6697, 8149, 8321, 8911

40

39, 121, 289, 451, 533, 703, 793, 1541, 1561, 1729, 1921, 2821, 3097, 3829, 4961, 5461, 5729, 6601, 7111, 7201, 9073, 9881

41

21, 105, 145, 231, 609, 645, 671, 703, 841, 1065, 1281, 1387, 1417, 1729, 2121, 2465, 2701, 3053, 3829, 4033, 6161, 8321, 8911, 9253

42

451, 529, 1105, 1247, 1441, 1541, 1765, 1807, 1921, 1991, 2465, 2665, 5977, 6001, 7421, 9773

43

21, 25, 33, 77, 105, 185, 385, 481, 561, 777, 825, 925, 973, 1105, 1541, 1729, 1807, 1825, 2465, 2553, 2821, 2849, 3281, 3439, 3781, 4033, 4417, 6105, 6369, 6545, 6601, 6697, 7081, 7825, 8857

44

9, 15, 45, 65, 129, 301, 369, 585, 645, 703, 745, 1035, 1729, 1921, 1937, 1981, 2047, 2465, 3585, 3913, 4005, 4097, 4417, 4633, 6273, 6533, 6705, 7281, 7345, 8385

45

133, 253, 481, 1417, 1541, 1729, 1981, 2059, 2071, 3053, 3289, 3553, 4033, 4921, 5377, 6533, 6601, 6817, 7337, 8321, 9361

46

9, 15, 45, 133, 141, 145, 341, 657, 705, 721, 781, 949, 1305, 1417, 1645, 1729, 1891, 1957, 1991, 2071, 2117, 2201, 2465, 3201, 4033, 4089, 4187, 4465, 4681, 5611, 5833, 6721, 8321, 9211

47

65, 69, 85, 221, 341, 345, 481, 561, 703, 721, 793, 897, 1105, 1649, 1729, 1891, 2257, 2465, 2737, 3145, 3201, 5185, 5461, 5865, 6305, 9361, 9881

48

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

49

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

50

21, 49, 51, 133, 301, 357, 561, 697, 793, 817, 833, 1281, 1649, 1729, 2009, 2041, 2501, 2701, 3201, 3913, 4753, 5461, 6601, 7701, 8041, 8113, 9073, 9577

51

25, 65, 175, 325, 481, 1247, 1681, 1729, 1825, 2059, 2653, 2821, 3053, 5461, 6505, 6601, 7201, 8365, 9475

52

51, 265, 561, 671, 901, 1541, 1891, 2413, 2465, 2653, 2705, 3201, 3421, 4081, 4505, 5151, 6433, 6533, 7201, 8911, 9773

53

9, 27, 65, 91, 117, 561, 585, 1105, 1405, 1441, 1541, 1729, 2209, 2465, 2529, 2821, 2863, 3097, 3367, 3481, 3861, 5317, 5833, 6031, 6433, 9409

54

55, 265, 341, 361, 385, 781, 1045, 1247, 1729, 2201, 2465, 2701, 2863, 4033, 4069, 4081, 5461, 7957, 8321, 9073

55

9, 21, 27, 153, 189, 369, 553, 801, 1027, 1387, 1513, 1729, 2821, 3649, 4033, 6273, 6533, 6541, 7189, 9773, 9937

56

33, 55, 57, 165, 209, 247, 285, 589, 1027, 1045, 1501, 1705, 1891, 1957, 2449, 2465, 3193, 3277, 3553, 3565, 4345, 5665, 6441, 7657, 8137, 8321

57

25, 65, 125, 145, 217, 325, 377, 721, 781, 1001, 1625, 2047, 2465, 2911, 3193, 3625, 4187, 5425, 6533, 6601, 7501, 7613, 8401, 9425

58

57, 133, 177, 341, 671, 1121, 1141, 1441, 1541, 1729, 2065, 3009, 3097, 3365, 3781, 4061, 7471, 7991, 8119, 8321, 8749, 9073

59

15, 145, 451, 561, 645, 1105, 1141, 1247, 1541, 1661, 1729, 1991, 2413, 2465, 3097, 4681, 5611, 5729, 6191, 6533, 6601, 7421, 8149, 8321, 8705, 9637

60

341, 481, 793, 841, 1729, 1891, 2257, 3133, 3277, 3601, 3661, 4577, 4777, 6161, 6533, 8917, 9937

61

15, 93, 217, 341, 465, 1261, 1441, 1729, 2465, 2701, 2821, 3565, 3661, 4061, 4577, 5461, 6541, 6601, 6697, 7613, 7905, 9305, 9937

62

9, 21, 63, 91, 105, 231, 305, 361, 549, 679, 793, 1261, 1281, 1541, 1729, 2121, 2465, 2745, 2871, 3367, 3439, 3845, 4141, 4577, 5185, 5917, 6161, 6533, 6601, 6697, 6849, 6921, 8827

63

341, 481, 529, 703, 841, 1147, 1417, 1985, 2071, 2465, 2509, 3379, 3683, 4033, 4577, 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, 133, 289, 703, 1111, 1387, 1891, 1921, 2701, 3553, 4291, 6533, 6697, 8321, 9537, 9709, 9809

66

65, 469, 481, 1105, 1541, 1729, 2071, 2201, 2465, 2821, 2911, 4033, 4291, 4681, 5461, 6097, 6601, 6953, 7969, 9211

67

33, 49, 217, 385, 561, 703, 1105, 1309, 1519, 1705, 1729, 2209, 2245, 2465, 3201, 5797, 6119, 7633, 7701, 8029, 8321, 8371, 9073

68

25, 49, 69, 125, 133, 185, 201, 217, 247, 345, 361, 469, 481, 589, 637, 871, 925, 1025, 1225, 1273, 1417, 1519, 1541, 1729, 1771, 2077, 2185, 2413, 2553, 2725, 2821, 4033, 4625, 4693, 4921, 5025, 5425, 5713, 6097, 7585, 7657, 7705, 8241, 8625, 9025, 9361

69

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

70

69, 169, 213, 341, 377, 561, 671, 781, 897, 949, 1441, 1541, 1633, 1891, 2001, 2201, 2769, 3053, 3201, 4061, 4901, 6001, 6177, 7449, 9301, 9361

71

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

72

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

73

9, 65, 185, 205, 259, 333, 369, 481, 533, 585, 1221, 1441, 1665, 1729, 1921, 2465, 2553, 2665, 3439, 4329, 5257, 5461, 6273, 6601, 6697, 7585, 9073

74

15, 25, 75, 91, 325, 365, 427, 511, 793, 949, 1387, 1525, 1729, 1825, 2465, 2821, 4453, 4577, 5185, 5551, 6533, 6541, 6601, 6643, 7421, 7613

75

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

76

15, 21, 25, 33, 75, 77, 105, 165, 265, 385, 525, 545, 561, 781, 825, 949, 1105, 1113, 1369, 1417, 1541, 1825, 1891, 1925, 2289, 2465, 2701, 3605, 4033, 4081, 4097, 4681, 5461, 5777, 6533, 6545, 7957, 8365, 8393, 8745, 9211, 9265, 9673

77

39, 57, 65, 741, 1105, 1387, 1513, 2465, 2701, 2965, 3705, 4033, 4371, 5073, 5461, 5713, 6533, 6541

78

77, 341, 385, 451, 553, 703, 869, 1247, 1271, 1441, 1849, 1921, 2047, 2465, 3097, 4061, 4187, 4345, 4577, 6031, 6085, 6601, 8321

79

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

80

9, 27, 49, 81, 169, 237, 301, 481, 553, 1377, 1729, 2107, 2133, 2553, 3321, 3397, 3439, 3537, 3913, 5461, 6253, 6401, 6533, 6601, 6697, 7107, 7613, 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, 249, 481, 511, 793, 891, 925, 949, 1345, 1377, 1525, 1541, 1729, 1825, 2025, 2101, 2241, 2257, 2465, 2821, 2871, 2905, 4033, 5185, 5611, 6225, 6533, 6643, 6725, 7957, 8321, 9919

83

21, 65, 105, 133, 231, 265, 273, 561, 689, 703, 861, 1001, 1105, 1113, 1241, 1729, 2465, 2569, 2665, 2993, 3277, 3445, 4081, 4305, 4411, 4641, 5713, 6541, 6601, 6973, 7665, 8421

84

85, 481, 1105, 1615, 2465, 2501, 2981, 3145, 5713, 6161, 6533, 6973, 7141, 7201, 7885, 8401

85

21, 129, 301, 341, 481, 781, 1281, 1591, 1729, 2201, 3097, 3201, 3913, 4577, 4681, 4859, 7141, 7161, 7613, 8299, 9637

86

65, 85, 87, 145, 377, 493, 561, 595, 1105, 1729, 2465, 3091, 4033, 5365, 5685, 6409, 6601, 7397, 7483, 7701, 9673

87

133, 217, 247, 301, 385, 403, 473, 559, 589, 817, 1105, 1333, 1661, 1705, 1729, 2821, 3553, 3785, 3913, 4681, 5461, 6533, 6601, 7471, 7483, 7657, 8401, 9841, 9881

88

87, 133, 145, 217, 247, 403, 481, 589, 1729, 1891, 2047, 2465, 2581, 2611, 2821, 4331, 4849, 4921, 5785, 6697, 7657, 7745, 9073

89

9, 15, 33, 45, 153, 165, 169, 341, 385, 561, 1035, 1045, 1105, 1441, 1541, 1729, 2097, 2465, 2529, 2611, 2977, 3201, 3961, 4061, 4187, 4849, 5461, 6681, 6697, 7107, 7601, 7689, 7711

90

91, 793, 1001, 1157, 1729, 2413, 2821, 4033, 6281, 6601, 8321, 8401

91

9, 15, 45, 69, 341, 345, 369, 505, 1065, 1387, 1541, 2465, 2651, 3015, 4005, 4141, 4187, 4545, 5963, 6273, 6533, 6969, 9361, 9881

92

21, 65, 91, 93, 105, 217, 273, 301, 341, 451, 465, 559, 861, 1001, 1209, 1333, 1393, 1661, 1729, 2465, 2587, 2701, 2821, 3731, 3781, 3913, 4033, 4371, 4641, 4681, 6169, 6697, 7161, 7905, 7957, 8321, 8465, 8557, 8841, 8911

93

25, 301, 325, 793, 865, 1081, 1105, 1393, 1525, 1729, 1771, 2047, 2465, 2737, 3781, 3913, 4033, 4187, 4325, 4465, 4945, 5149, 5185, 5713, 5833, 6697, 6721, 8321, 8557, 8743, 8911, 9361

94

57, 93, 95, 121, 133, 217, 285, 341, 403, 465, 561, 589, 645, 1065, 1105, 1541, 1653, 1729, 2465, 2821, 2945, 2977, 3053, 3565, 4961, 5461, 5685, 6665, 7099, 7471, 7657, 7905, 8743, 8911, 9073, 9937

95

141, 341, 1891, 1921, 2821, 2977, 3131, 3421, 3601, 4089, 4741, 5461, 6161, 6533, 6721, 8249, 8601, 9121, 9641

96

65, 95, 133, 469, 485, 679, 781, 973, 1273, 1729, 2465, 2641, 2701, 3545, 4187, 4577, 5617, 6097, 6305, 9121, 9217, 9313

97

21, 49, 105, 341, 469, 481, 833, 949, 973, 1065, 1729, 2465, 2701, 3053, 3283, 3577, 4187, 4371, 4705, 6097, 6811, 7161, 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, 65, 145, 169, 217, 245, 361, 377, 775, 833, 1225, 1729, 2413, 2465, 3185, 3277, 3565, 4225, 4901, 5425, 5611, 6889, 6943, 7105, 7825, 8029, 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

 

Esistono pseudoprimi di Eulero assoluti, che sono pseudoprimi di Eulero rispetto a qualsiasi base inferiore al numero stesso, esclusi naturalmente i divisori del numero.

Contattami

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