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

Pseudoprimi di Fermat

Teoria dei numeri 

Fermat dimostrò che bp – 1 ≡ 1 mod p, se p è primo e non divide b; l’inverso non è sempre vero: non è detto che se bp – 1 ≡ 1 mod p, con b > 1 e b e p primi tra loro, allora p sia primo.

I numeri composti che soddisfano tale congruenza si dicono “pseudoprimi di Fermat rispetto alla base b” o più semplicemente “pseudoprimi in base b”.

 

Molti Autori occidentali dell’ultimo secolo riferiscono che gli antichi cinesi credevano che se 2n – 1 ≡ 1 mod n, allora n è primo. L’affermazione è però errata, come riferisce Ribenboim: a parte il fatto che un’asserzione del genere è incompatibile con l’avanzamento della matematica cinese ai tempi di Confucio, l’errore risale a tempi recenti. La leggenda sembra essere originata da uno scritto di H.J. Jeans del 1897, che potrebbe essere stato motivato da un’errata traduzione da “I nove capitoli dell’arte matematica”, come supposto da Needham nella sua monumentale opera (Science and Civilisation in China, vol. 3, cap. 19).

Nella sua tesi di laurea Han Qi riferisce che la congettura risale (in Cina) a Li Shan-Lan (1811 – 1882) e venne riportata tra i lavori di Li da un certo Wylie nel 1869. Alcuni matematici occidentali si accorsero dell’errore e informarono Li, che ne rimosse ogni accenno dai suoi lavori sulla teoria dei numeri. Tuttavia nel 1882 Hua Heng-Fang pubblicò un trattato nel quale incluse la congettura di Li come se fosse un fatto noto, inducendo probabilmente alcuni a credere che risalisse a tempi immemorabili.

Dickson riporta l’affermazione di Jeans e riferisce che altri matematici sono caduti nello stesso errore, a cominciare da Leibniz (1680).

 

Il primo esempio di pseudoprimo venne trovato da Pierre Frédéric Sarrus (10/3/1798, Saint-Affrique, Francia – 20/11/1861), che nel 1819 dimostrò che 341 = 31 • 11 è pseudoprimo in base 2; per questo motivo gli pseudoprimi in base 2 sono detti “numeri di Sarrus” o “numeri di Poulet”, in onore del matematico belga Paul Poulet (1887 – 1946) che pubblicò le prime grandi tabelle di questi numeri.

 

Nel 1830 un matematico rimasto anonimo notò che se ap – 1 – 1 è un multiplo di pq e q – 1 e un multiplo di p – 1, con p primo, pq è pseudoprimo in base a.

 

Lucas scoprì nel 1876 un altro pseudoprimo in base 2, vale a dire 2701, e nel 1891 dimostrò una sorta di inverso del teorema di Fermat: se bp – 1 – 1 è divisibile per p e bn – 1 non lo è per alcun n divisore proprio di p – 1, p è primo.

 

Se p, q e r sono primi distinti e pq, pr e qr sono pseudoprimi di Fermat in una base, anche pqr lo è.

 

 

M. Cipolla pubblicò nel 1904 un semplice metodo per trovare pseudoprimi di Fermat: per ogni intero a si prenda un primo p che non divida a(a2 – 1), allora n = (a^p – 1) / (a – 1) * (a^p + 1) / (a + 1) = (a^(2 * p) – 1) / (a^2 – 1) è pseudoprimo in base a, come pure tutti i suoi divisori composti dispari. Dato che ogni n così ottenuto è chiaramente composto e che ne esistono infiniti, per ogni base esistono infiniti pseudoprimi; in particolare (2^(2 * p) – 1) / 3 è pseudoprimo in base 2 se p > 3.

Cipolla dimostrò inoltre che se p e q = 2p – 1 sono primi, pq è pseudoprimo di Fermat rispetto ai residui quadratici di q.

 

Steuerwald nel 1948 dimostrò che se n è pseudoprimo di Fermat in base a e primo rispetto ad a – 1, anche (a^n – 1) / (a – 1) è pseudoprimo di Fermat in base a e primo rispetto ad a – 1. In seguito furono scoperti altri modi per produrre sequenze infinite di pseudoprimi di Fermat in una base fissata.

 

Erdös dimostrò nel 1949 che fissato un qualsiasi intero maggiore di uno, esistono infiniti pseudoprimi di Fermatin base 2 con quel numero di fattori primi distinti; Lieuwens dimostrò nel 1971 che vale per qualsiasi base.

 

Erdös dimostrò nel 1956 che gli pseudoprimi di Fermat in base 2 minori di n sono meno di Limite superiore per il numero di pseudoprimi di Fermat in base 2 minori di n per una costante c e n abbastanza grande; la dimostrazione vale con semplici modifiche per qualsiasi base diversa da 1 e –1. Una conseguenza è che la somma dei reciproci degli pseudoprimi di Fermat in una base diversa da 1 e –1 è convergente.

 

A. Schinzel dimostrò nel 1958 che per ogni numero fissato a, esistono due primi p e q arbitrariamente grandi tali che pq sia pseudoprimo di Fermat in base a.

 

A. Rotkiewicz dimostrò nel 1959 che se a e b sono primi tra loro, fissato m esistono infiniti interi n, prodotto di m primi, che dividono an – 1bn – 1. In particolare, se b = 1, esistono infiniti pseudoprimi di Fermat, ciascuno prodotto di un numero prefissato di primi distinti.

 

A. Rotkiewicz dimostrò nel 1963 che fissati a e d primi tra loro, in ogni base esistono infinite progressioni aritmetiche di pseudoprimi di Fermat della forma a + nd per n > 1.

 

A. Rotkiewicz dimostrò nel 1972 che per ogni base esistono infiniti pseudoprimi di Fermat multipli di ogni primo che non divida la base.

 

A. MÄ…kovski dimostrò nel 1974 che, chiamando Qn(b) l’n-esimo pseudoprimo di Fermat in base bSomma dei reciproci dei logaritmi degli pseudoprimi di Fermat in base b diverge per qualsiasi base b > 0.

 

Nel 1981 Carl Pomerance dimostrò che il numero di pseudoprimi di Fermat in base 2 minori di n è almeno 0.171logn, per n maggiore di 340, mentre in qualsiasi base fissata per il numero di pseudoprimi di Fermat maggiori di n P(n) in qualsiasi base fissata vale Limiti inferiore e superiore per il numero di pseudoprimi di Fermat in quasiasi base minori di n. Nel 1989 Pomerance aumentò l’esponente 5 / 14 a 85 / 207.

 

Se p è pseudoprimo di Fermat in base n!, p non divide n!, quindi è maggiore di n; pertanto la sequenza dei minimi pseudoprimi di Fermat è illimitata e non periodica al crescere della base.

 

Per gli pseudoprimi di Fermat in base 2 v. numeri di Poulet.

 

In base 1 tutti i numeri composti sono banalmente pseudoprimi di Fermat.

Dato che kn + 1 ≡ 1 mod n, (kn + 1)n – 1 ≡ 1 mod n, ogni intero composto n è pseudoprimo di Fermat in base kn + 1 per ogni intero positivo k e in particolare in base n + 1.

Dato che kn – 1 ≡ –1 mod n, se n è dispari, (kn – 1)n – 1 ≡ 1 mod n, ogni intero composto dispari n è pseudoprimo di Fermat in base kn – 1 per ogni intero positivo k e in particolare in base n – 1.

 

Se b e n sono primi tra loro, un numero composto dispari n è pseudoprimo di Fermat in base b se e solo se ((n – 1)! – 1)bn – 1 ≡ –1 mod n. Infatti, se b e n non hanno divisori comuni, ((n – 1)! – 1) mod n vale 0 se n è primo, –1 altrimenti (teorema di Wilson), mentre bn – 1 mod n vale 1 se e solo se n è pseudoprimo di Fermat in base b.

 

Se un intero è pseudoprimo di Fermat rispetto a una base, lo è anche rispetto alle potenze della base. L’inverso non è sempre vero, uno pseudoprimo di Fermat rispetto a una potenza non è detto che sia tale rispetto alla base; per esempio, 39 è pseudoprimo di Fermat in base 25 = 52, ma non in base 5.

Se un intero n è pseudoprimi di Fermat rispetto a due basi a e b, prime rispetto a n, lo è anche rispetto alle basi ab e ab–1, dove b–1 è l’inverso di b modulo n. L’inverso non è sempre vero, ossia uno pseudoprimo di Fermat rispetto a un numero composto non è detto che lo sia rispetto ai fattori; per esempio, 55 è pseudoprimo di Fermat in base 21 = 3 • 7, ma non lo è in base 3 o 7.

 

Se un intero n non è pseudoprimo di Fermat rispetto a una base b minore di n, con n e b primi tra loro, allora non è pseudoprimo di Fermat rispetto ad almeno la metà delle basi maggiori di 1, minori di n e prime rispetto a n.

 

Se p è un primo maggiore di 3 e 2p – 1 è primo, p(2p – 1) è pseudoprimo di Fermat in base 3. Per esempio, p = 7 è primo, 2p – 1 = 13 è primo e p(2p – 1) = 91 è pseudoprimo in base 3.

Se p è un primo maggiore di 3 e 2p – 1 è primo, p(2p – 1) è pseudoprimo di Fermat in base 5 se e solo se p è della forma 10k + 1. Per esempio, p = 31 è primo, 2p – 1 = 61 è primo e p(2p – 1) = 1891 è pseudoprimo in base 5.

 

Se p è un primo maggiore di 5, (2^(2 * p) + 1) / 5 è primo o pseudoprimo di Fermat in base 5 (A. Rotkiewicz).

 

Schinzel dimostrò che il minimo pseudoprimo di Fermat in base 4k e 4k + 1, per ogni valore di k, è 4; il minimo in base 12k + 3, 12k + 6, 12k + 7 e 12k + 10 è 6.

 

Un numero può essere pseudoprimo di Fermat in più basi:

  • il minimo in base 2 e 3 è 1105;

  • il minimo in base 2, 3 e 5 è 1729;

  • il minimo in base 2, 3, 5 e 7 è 29341.

 

Nel 1980 Robert Baillie e Samuel S. Wagstaff Jr. dimostrarono che il numero di basi minori di n nelle quali n è pseudoprimo di Fermat (includendo le basi banali 1 e n – 1) è dato da Formula per il numero di basi minori di n nelle quali n è pseudoprimo di Fermat, dove il prodotto va calcolato su tutti i divisori primi di n; solitamente tale numero è piccolo rispetto a n. In particolare il numero di basi rispetto alle quali n è pseudoprimo di Fermat divide φ(n): per esempio, φ(91) = 72 e 91 è pseudoprimo di Fermat in 36 basi minori di 91. Di conseguenza un numero composto dispari è pseudoprimo di Fermat rispetto ad almeno due basi non banali, e almeno tre se non è una potenza di 3.

 

I numeri che sono pseudoprimi di Fermat in qualsiasi base prima rispetto a essi sono detti “pseudoprimi assoluti” o “numeri di Carmichael”.

 

Un numero composto n che non sia un numero di Carmichael è pseudoprimo di Fermat rispetto al massimo a φ(n) / 2 basi minori di n. Esistono numeri che sono effettivamente pseudoprimi di Fermat rispetto a φ(n) / 2 basi; per esempio, nel caso di 91 = 7 • 13, φ(91) / 2 = 36 e 91 è pseudoprimo di Fermat rispetto a 36 basi: 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90. I numeri composti n che non sono numeri di Carmichael tuttavia sono per lo più pseudoprimi rispetto a poche basi minori di n.

 

La tabella seguente mostra gli pseudoprimi di Fermat minori di 10000 nelle basi b fino a 20.

b

Pseudoprimi di Fermat

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911

10

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

11

10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730

12

65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073

13

4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637

14

15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073

15

14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073

16

15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919

17

4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911

18

25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061

19

6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997

20

21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911

 

La tabella seguente mostra per i numeri composti n minori di 20 le basi minori di 1000 nelle quali sono pseudoprimi di Fermat.

n

Basi

4

5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, 101, 105, 109, 113, 117, 121, 125, 129, 133, 137, 141, 145, 149, 153, 157, 161, 165, 169, 173, 177, 181, 185, 189, 193, 197, 201, 205, 209, 213, 217, 221, 225, 229, 233, 237, 241, 245, 249, 253, 257, 261, 265, 269, 273, 277, 281, 285, 289, 293, 297, 301, 305, 309, 313, 317, 321, 325, 329, 333, 337, 341, 345, 349, 353, 357, 361, 365, 369, 373, 377, 381, 385, 389, 393, 397, 401, 405, 409, 413, 417, 421, 425, 429, 433, 437, 441, 445, 449, 453, 457, 461, 465, 469, 473, 477, 481, 485, 489, 493, 497, 501, 505, 509, 513, 517, 521, 525, 529, 533, 537, 541, 545, 549, 553, 557, 561, 565, 569, 573, 577, 581, 585, 589, 593, 597, 601, 605, 609, 613, 617, 621, 625, 629, 633, 637, 641, 645, 649, 653, 657, 661, 665, 669, 673, 677, 681, 685, 689, 693, 697, 701, 705, 709, 713, 717, 721, 725, 729, 733, 737, 741, 745, 749, 753, 757, 761, 765, 769, 773, 777, 781, 785, 789, 793, 797, 801, 805, 809, 813, 817, 821, 825, 829, 833, 837, 841, 845, 849, 853, 857, 861, 865, 869, 873, 877, 881, 885, 889, 893, 897, 901, 905, 909, 913, 917, 921, 925, 929, 933, 937, 941, 945, 949, 953, 957, 961, 965, 969, 973, 977, 981, 985, 989, 993, 997

6

7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, 73, 79, 85, 91, 97, 103, 109, 115, 121, 127, 133, 139, 145, 151, 157, 163, 169, 175, 181, 187, 193, 199, 205, 211, 217, 223, 229, 235, 241, 247, 253, 259, 265, 271, 277, 283, 289, 295, 301, 307, 313, 319, 325, 331, 337, 343, 349, 355, 361, 367, 373, 379, 385, 391, 397, 403, 409, 415, 421, 427, 433, 439, 445, 451, 457, 463, 469, 475, 481, 487, 493, 499, 505, 511, 517, 523, 529, 535, 541, 547, 553, 559, 565, 571, 577, 583, 589, 595, 601, 607, 613, 619, 625, 631, 637, 643, 649, 655, 661, 667, 673, 679, 685, 691, 697, 703, 709, 715, 721, 727, 733, 739, 745, 751, 757, 763, 769, 775, 781, 787, 793, 799, 805, 811, 817, 823, 829, 835, 841, 847, 853, 859, 865, 871, 877, 883, 889, 895, 901, 907, 913, 919, 925, 931, 937, 943, 949, 955, 961, 967, 973, 979, 985, 991, 997

8

9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97, 105, 113, 121, 129, 137, 145, 153, 161, 169, 177, 185, 193, 201, 209, 217, 225, 233, 241, 249, 257, 265, 273, 281, 289, 297, 305, 313, 321, 329, 337, 345, 353, 361, 369, 377, 385, 393, 401, 409, 417, 425, 433, 441, 449, 457, 465, 473, 481, 489, 497, 505, 513, 521, 529, 537, 545, 553, 561, 569, 577, 585, 593, 601, 609, 617, 625, 633, 641, 649, 657, 665, 673, 681, 689, 697, 705, 713, 721, 729, 737, 745, 753, 761, 769, 777, 785, 793, 801, 809, 817, 825, 833, 841, 849, 857, 865, 873, 881, 889, 897, 905, 913, 921, 929, 937, 945, 953, 961, 969, 977, 985, 993

9

8, 10, 17, 19, 26, 28, 35, 37, 44, 46, 53, 55, 62, 64, 71, 73, 80, 82, 89, 91, 98, 100, 107, 109, 116, 118, 125, 127, 134, 136, 143, 145, 152, 154, 161, 163, 170, 172, 179, 181, 188, 190, 197, 199, 206, 208, 215, 217, 224, 226, 233, 235, 242, 244, 251, 253, 260, 262, 269, 271, 278, 280, 287, 289, 296, 298, 305, 307, 314, 316, 323, 325, 332, 334, 341, 343, 350, 352, 359, 361, 368, 370, 377, 379, 386, 388, 395, 397, 404, 406, 413, 415, 422, 424, 431, 433, 440, 442, 449, 451, 458, 460, 467, 469, 476, 478, 485, 487, 494, 496, 503, 505, 512, 514, 521, 523, 530, 532, 539, 541, 548, 550, 557, 559, 566, 568, 575, 577, 584, 586, 593, 595, 602, 604, 611, 613, 620, 622, 629, 631, 638, 640, 647, 649, 656, 658, 665, 667, 674, 676, 683, 685, 692, 694, 701, 703, 710, 712, 719, 721, 728, 730, 737, 739, 746, 748, 755, 757, 764, 766, 773, 775, 782, 784, 791, 793, 800, 802, 809, 811, 818, 820, 827, 829, 836, 838, 845, 847, 854, 856, 863, 865, 872, 874, 881, 883, 890, 892, 899, 901, 908, 910, 917, 919, 926, 928, 935, 937, 944, 946, 953, 955, 962, 964, 971, 973, 980, 982, 989, 991, 998, 1000

10

11, 21, 31, 41, 51, 61, 71, 81, 91, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 201, 211, 221, 231, 241, 251, 261, 271, 281, 291, 301, 311, 321, 331, 341, 351, 361, 371, 381, 391, 401, 411, 421, 431, 441, 451, 461, 471, 481, 491, 501, 511, 521, 531, 541, 551, 561, 571, 581, 591, 601, 611, 621, 631, 641, 651, 661, 671, 681, 691, 701, 711, 721, 731, 741, 751, 761, 771, 781, 791, 801, 811, 821, 831, 841, 851, 861, 871, 881, 891, 901, 911, 921, 931, 941, 951, 961, 971, 981, 991

12

13, 25, 37, 49, 61, 73, 85, 97, 109, 121, 133, 145, 157, 169, 181, 193, 205, 217, 229, 241, 253, 265, 277, 289, 301, 313, 325, 337, 349, 361, 373, 385, 397, 409, 421, 433, 445, 457, 469, 481, 493, 505, 517, 529, 541, 553, 565, 577, 589, 601, 613, 625, 637, 649, 661, 673, 685, 697, 709, 721, 733, 745, 757, 769, 781, 793, 805, 817, 829, 841, 853, 865, 877, 889, 901, 913, 925, 937, 949, 961, 973, 985, 997

14

15, 29, 43, 57, 71, 85, 99, 113, 127, 141, 155, 169, 183, 197, 211, 225, 239, 253, 267, 281, 295, 309, 323, 337, 351, 365, 379, 393, 407, 421, 435, 449, 463, 477, 491, 505, 519, 533, 547, 561, 575, 589, 603, 617, 631, 645, 659, 673, 687, 701, 715, 729, 743, 757, 771, 785, 799, 813, 827, 841, 855, 869, 883, 897, 911, 925, 939, 953, 967, 981, 995

15

4, 11, 14, 16, 19, 26, 29, 31, 34, 41, 44, 46, 49, 56, 59, 61, 64, 71, 74, 76, 79, 86, 89, 91, 94, 101, 104, 106, 109, 116, 119, 121, 124, 131, 134, 136, 139, 146, 149, 151, 154, 161, 164, 166, 169, 176, 179, 181, 184, 191, 194, 196, 199, 206, 209, 211, 214, 221, 224, 226, 229, 236, 239, 241, 244, 251, 254, 256, 259, 266, 269, 271, 274, 281, 284, 286, 289, 296, 299, 301, 304, 311, 314, 316, 319, 326, 329, 331, 334, 341, 344, 346, 349, 356, 359, 361, 364, 371, 374, 376, 379, 386, 389, 391, 394, 401, 404, 406, 409, 416, 419, 421, 424, 431, 434, 436, 439, 446, 449, 451, 454, 461, 464, 466, 469, 476, 479, 481, 484, 491, 494, 496, 499, 506, 509, 511, 514, 521, 524, 526, 529, 536, 539, 541, 544, 551, 554, 556, 559, 566, 569, 571, 574, 581, 584, 586, 589, 596, 599, 601, 604, 611, 614, 616, 619, 626, 629, 631, 634, 641, 644, 646, 649, 656, 659, 661, 664, 671, 674, 676, 679, 686, 689, 691, 694, 701, 704, 706, 709, 716, 719, 721, 724, 731, 734, 736, 739, 746, 749, 751, 754, 761, 764, 766, 769, 776, 779, 781, 784, 791, 794, 796, 799, 806, 809, 811, 814, 821, 824, 826, 829, 836, 839, 841, 844, 851, 854, 856, 859, 866, 869, 871, 874, 881, 884, 886, 889, 896, 899, 901, 904, 911, 914, 916, 919, 926, 929, 931, 934, 941, 944, 946, 949, 956, 959, 961, 964, 971, 974, 976, 979, 986, 989, 991, 994

16

17, 33, 49, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 273, 289, 305, 321, 337, 353, 369, 385, 401, 417, 433, 449, 465, 481, 497, 513, 529, 545, 561, 577, 593, 609, 625, 641, 657, 673, 689, 705, 721, 737, 753, 769, 785, 801, 817, 833, 849, 865, 881, 897, 913, 929, 945, 961, 977, 993

18

19, 37, 55, 73, 91, 109, 127, 145, 163, 181, 199, 217, 235, 253, 271, 289, 307, 325, 343, 361, 379, 397, 415, 433, 451, 469, 487, 505, 523, 541, 559, 577, 595, 613, 631, 649, 667, 685, 703, 721, 739, 757, 775, 793, 811, 829, 847, 865, 883, 901, 919, 937, 955, 973, 991

20

21, 41, 61, 81, 101, 121, 141, 161, 181, 201, 221, 241, 261, 281, 301, 321, 341, 361, 381, 401, 421, 441, 461, 481, 501, 521, 541, 561, 581, 601, 621, 641, 661, 681, 701, 721, 741, 761, 781, 801, 821, 841, 861, 881, 901, 921, 941, 961, 981

 

La tabella seguente mostra il minimo pseudoprimo di Fermat nelle basi fino a 20.

Base

Minimo pseudoprimo

1

4

2

341

3

91

4

15

5

4

6

35

7

6

8

9

9

4

10

9

11

10

12

65

13

4

14

15

15

14

16

15

17

4

18

25

19

6

20

21

 

Qui trovate il minimo pseudoprimo di Fermat nelle basi fino a 10000 (Robert G. Wilson V, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Secondo alcuni Autori, come Crandall e Pomerance, la definizione va limitata ai numeri dispari eliminando i pari dall’elenco.

 

Se il numero p e la base hanno divisori comuni, e in particolare se sono entrambi pari, bp – 1 diviso per p non può dare resto 1, tuttavia se modifichiamo la definizione, in modo da includere i numeri tali che bpb mod p, possiamo avere pseudoprimi con divisori comuni alla base e in particolare pari in base 2 (v. primi finti).

Bibliografia

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

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