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

Poulet (numeri di)

Teoria dei numeri 

Si dicono “numeri di Poulet” gli pseudoprimi in base 2, cioè gli interi n composti per i quali 2n – 1 ≡ 1 mod n, in onore del matematico belga Paul Poulet (1887 – 1946), che ne fece oggetto di studi e pubblicò le prime grandi tabelle di questi numeri.

Sono anche detti anche “numeri di Sarrus”, in onore di Pierre Frédéric Sarrus (10/3/1798, Saint-Affrique, Francia – 20/11/1861), che trovò il primo, 341, nel 1819.

 

I numeri di Poulet minori di 106 sono: 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341, 30121, 30889, 31417, 31609, 31621, 33153, 34945, 35333, 39865, 41041, 41665, 42799, 46657, 49141, 49981, 52633, 55245, 57421, 60701, 60787, 62745, 63973, 65077, 65281, 68101, 72885, 74665, 75361, 80581, 83333, 83665, 85489, 87249, 88357, 88561, 90751, 91001, 93961, 101101, 104653, 107185, 113201, 115921, 121465, 123251, 126217, 129889, 129921, 130561, 137149, 149281, 150851, 154101, 157641, 158369, 162193, 162401, 164737, 172081, 176149, 181901, 188057, 188461, 194221, 196021, 196093, 204001, 206601, 208465, 212421, 215265, 215749, 219781, 220729, 223345, 226801, 228241, 233017, 241001, 249841, 252601, 253241, 256999, 258511, 264773, 266305, 271951, 272251, 275887, 276013, 278545, 280601, 282133, 284581, 285541, 289941, 294271, 294409, 314821, 318361, 323713, 332949, 334153, 340561, 341497, 348161, 357761, 367081, 387731, 390937, 396271, 399001, 401401, 410041, 422659, 423793, 427233, 435671, 443719, 448921, 449065, 451905, 452051, 458989, 464185, 476971, 481573, 486737, 488881, 489997, 493697, 493885, 512461, 513629, 514447, 526593, 530881, 534061, 552721, 556169, 563473, 574561, 574861, 580337, 582289, 587861, 588745, 604117, 611701, 617093, 622909, 625921, 635401, 642001, 647089, 653333, 656601, 657901, 658801, 665281, 665333, 665401, 670033, 672487, 679729, 680627, 683761, 688213, 710533, 711361, 721801, 722201, 722261, 729061, 738541, 741751, 742813, 743665, 745889, 748657, 757945, 769567, 769757, 786961, 800605, 818201, 825265, 831405, 838201, 838861, 841681, 847261, 852481, 852841, 873181, 875161, 877099, 898705, 915981, 916327, 934021, 950797, 976873, 983401, 997633.

 

Qui trovate i numeri di Poulet inferiori a 1012 (N.J.A. Sloane, David W. Wilson, The Online Encyclopedia of Integer Sequences http://oeis.org) (1.2 Mbyte).

 

Da notare che 2n mod n è molto spesso 0 (se n è una potenza di 2) o una potenza di 2, ma può assumere vari altri valori; per esempio, 23 mod 3 = 2, 29 mod 9 = 8, 218 mod 18 = 10 (il minimo valore di n, tale che il modulo sia un numero pari, ma non una potenza di 2), 225 mod 25 = 7 (il minimo valore di n, tale che il modulo sia un numero dispari), 210669 mod 10669 = 6 (il minimo modulo possibile che sia pari, ma non una potenza di 2), ma la formula sembrava snobbare il valore 3. D.H. e Emma Lehmer risolsero la questione trovando il minimo valore di n tale che 2n mod n = 3, ossia 4700063497.

 

Un intero composto dispari n è un numero di Poulet se e solo se ((n – 1)! – 1)2n – 1 ≡ –1 mod n.

 

Sono numeri di Poulet tra gli altri:

 

I numeri di Poulet sono pseudoprimi di Fermat rispetto a tutte le potenze di 2.

 

Se p e q sono primi, 2p – 2 è multiplo di q e 2q – 2 è multiplo di p, pq è un numero di Poulet. Esempi di coppie di primi del genere sono 11 e 31, che producono 341, il minimo numero di Poulet, 19 e 73, che producono 1387.

Se p e 2p – 1 sono primi, n = p(2p – 1) è un numero di Poulet se e solo se p è della forma 12k + 1; in tal caso n è anche pseudoprimo in base 6.

 

Negli anni sono state compilate tabelle dei numeri di Poulet fino a limiti sempre maggiori:

  • Banachiewicz arrivò fino a 2000;

  • Poulet nel 1926 arrivò a 5 • 107;

  • lo stesso Poulet nel 1938 arrivò a 108;

  • C. Pomerance, J. L. Selfridge e S.S. Wagstaff nel 1980 arrivarono sino a 25 • 109;

  • R. Pinch nel 2000 arrivò a 1013;

  • W. Galway arrivò a 264.

L’importanza di queste tabelle sta nel fatto che è relativamente facile verificare se pn – 1 ≡ 1 mod n, per alcuni valori di n; in questo modo si stabilisce se p è primo o pseudoprimo ed escludendo tramite le tabelle che appartenga a quest’ultima categoria, si ottiene un esame di primalità molto efficiente, per numeri non troppo grandi.

 

Nel 1897 J.H. Jeans notò che se 2p ≡ 2 mod q e 2q ≡ 2 mod p, con p e q primi differenti, pq è un numero di Poulet; ciò avviene se 2r ≡ 1 mod pq, dove r è un fattore comune di p – 1 e q – 1. Questa scoperta gli permise di scoprire i numeri di Poulet 1387, 4369, 4681 e 10261.

 

E. Malo dimostrò nel 1903 che tutti i numeri di Mersenne Mp composti con p primo sono numeri di Poulet e che se n è un numero di Poulet, anche Mn = 2n – 1 lo è e non è primo perché è divisibile per 2a – 1, dove a è uno dei divisori propri di n maggiori di 1. Quindi da un numero di Poulet n se ne ricava un altro Mn, e questo dimostra che esistono infiniti numeri di Poulet dispari.

 

Nel 1936 Lehmer dimostrò che se si prende un fattore primo primitivo (v. potenze) di 2k – 1 e uno di 2k + 1, il loro prodotto è un numero di Poulet; esistono quindi sempre almeno n numeri di Poulet, ciascuno prodotto di due fattori primi, non superiori a 4k + 3 – 1.

 

Erdös dimostrò nel 1949 che fissato un qualsiasi intero maggiore di uno, esistono infiniti numeri di Poulet con quel numero di fattori primi distinti.

 

Se p è un primo maggiore di 3, (4^p – 1) / 3 è un numero di Poulet (M. Cipolla, 1904).

 

Nel 1956 Erdös dimostrò che, indicando con P2(n) il numero di numeri di Poulet minori di n, vale Limiti inferiore e superiore per il numero di numeri di Poulet minori di n per due costanti c1 e c2 e n abbastanza grande.

 

Nel 1964 A. Rotkiewicz dimostrò che se p è un primo maggiore di 5, (4^p + 1) / 5 è un numero di Poulet.

 

Nel 1965 A. Rotkiewicz dimostrò che:

  • se p e q sono primi, pq è un numero di Poulet se e solo se lo è (2p – 1)(2q – 1);

  • se e solo se p è 11 o un primo maggiore di 13, esiste un altro primo q tale che pq sia un numero di Poulet;

  • i soli numeri di Poulet quadrati minori di 1012 sono i quadrati dei primi di Wieferich (10932 e 35112);

  • per n > 18 c’è sempre un numero di Poulet tra n e n2;

  • se a e b sono primi tra loro, esistono infiniti numeri di Poulet della forma an + b (una sorta di analogo del teorema di Dirichlet).

 

Nel 1965 K. Szymiczek dimostrò che la somma dei reciproci dei numeri di Poulet è divergente.

 

Nel 1981 Carl Pomerance dimostrò che per n abbastanza grande, il numero P2(x) di numeri di Poulet minori di x soddisfa Limite inferiore per il numero di numeri di Poulet minori di x e che i numeri di Poulet minori di n sono almeno 0.171logn, per n maggiore di 340.

Per avere un’idea dell’effettiva distribuzione, basta considerare che vi sono 455052512 primi minori di 1010, ma solo 14884 numeri di Poulet.

 

C’è sempre almeno un numero di Poulet tra n e n2, per n maggiore di 18 (Rotkiewicz 1965).

 

La tabella seguente riporta il numero di numeri di Poulet minori di 10n, per n fino a 19 (Jan Feitsma, William F. Galway, Charles R Greathouse IV e Eric W. Weisstein, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numeri di Poulet minori di 10n

1

0

2

0

3

3

4

22

5

78

6

245

7

750

8

2057

9

5597

10

14884

11

38975

12

101629

13

264239

14

687007

15

1801533

16

4744920

17

12604009

18

33763684

19

91210364

 

 

Gli unici due numeri di Poulet con differenza 2, che potremmo chiamare “gemelli”, inferiori a 1013 sono 4369 e 4371.

 

Esistono numeri di Poulet che hanno un numero di Poulet come massimo divisore proprio; il minimo è 158369, multiplo di 5641 = 43 • 127.

 

Il minimo numero di Poulet che sia prodotto di due numeri di Poulet è 2113665 = 645 • 3277.

 

La condizione soddisfatta dai numeri di Poulet dispari può essere scritta come 2n ≡ 2 mod n, e in questa forma può essere soddisfatta anche da numeri pari, ossia dai primi finti in base 2.

La questione dell’esistenza di numeri di Poulet pari venne risolta da D.H. Lehmer, che nel 1950 dimostrò che il minimo pari è 161038 = 2 • 73 • 1103.

 

N.G.W.H. Beeger dimostrò nel 1951 che i numeri di Poulet pari sono infiniti, hanno almeno due fattori primi dispari e ne trovò altri tre: 215326 = 2 • 23 • 31 • 151, 2568226 = 2 • 23 • 31 • 1801 e 143742226 = 2 • 23 • 31 • 100801.

W.L. McDaniel trovò nel 1989 che 2n – 2 è un numero di Poulet per n = 465794 e suppose che sia il minimo numero di Poulet pari di questa forma. McDaniel dimostrò anche che se p e q sono primi distinti, 2p + 1 ≡ 3 mod q, 2q + 1 ≡ 3 mod p e 2pq + 1 ≡ 3 mod pq, allora 2(2pq – 1) è un numero di Poulet pari.

Nel 1995 A. Rotkiewicz e K. Ziemak trovarono 24 pseudoprimi pari con da 3 a 8 fattori primi.

 

Se p e q sono primi distinti, d è un divisore di (2p – 1)(2q – 1), non multiplo di p, q, (2p – 1) o (2q – 1), 2 * (2^p – 1) * (2^q – 1) / d è un numero di Poulet pari se e solo se lo è 2 * (2^(p * q) – 1) / d (A. Rotkiewicz e K. Ziemak, 1995).

 

I numeri di Poulet pari inferiori a 109 sono: 161038, 215326, 2568226, 3020626, 7866046, 9115426, 49699666, 143742226, 161292286, 196116194, 209665666, 213388066, 293974066, 336408382, 377994926, 410857426, 665387746, 667363522, 672655726, 760569694.

Qui trovate i numeri di Poulet pari inferiori a 2 • 1015 (Max Alekseyev, Rich Schroeppel, N.J.A. Sloane, Robert G. Wilson V, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Il minimo numero di Poulet pari e multiplo di quadrati è 190213279479817426 = 2 • 7 • 79 • 1951 • 35112 • 7151 (Max Alekseyev, 2017).

 

Marius Coman avanzò una congettura sui numeri di Poulet con due soli divisori, che sono anche numeri super – Poulet: se un numero super – Poulet ha due soli fattori primi p e q, allora o q = n(p – 1) + 1, per un qualche intero positivo n, oppure q = m(r – 1) + 1 e p = n(r – 1) + 1, per due interi positivi m e n e r primo e maggiore di 7.

 

Marius Coman avanzò un’originalissima congettura sui numeri di Poulet, secondo la quale esisterebbero infiniti numeri di Poulet che si scrivono concatenando due o più numeri primi in notazione decimale.

I primi esempi sono:

  • 341 (3 e 41);

  • 561 (5 e 61);

  • 1729 (17 e 29);

  • 2701 (2 e 701);

  • 2821 (2 e 821);

  • 3277 (3 e 277; 3, 2, 7 e 7);

  • 4371 (43 e 71);

  • 8911 (89 e 11);

  • 13741 (137 e 41; 13, 7 e 41);

  • 13747 (137 e 47; 13, 7 e 47);

  • 23001 (2 e 3001);

  • 25761 (257 e 61; 2, 5 e 761; 2, 5, 7 e 61);

  • 29341 (293 e 41; 2 e 9341);

  • 33153 (331 e 53);

  • 35333 (3533 e 3; 353, 3 e 3; 3, 53, 3 e 3; 3, 5, 3, 3 e 3);

  • 49141 (491 e 41);

  • 63973 (6397 e 3);

  • 83333 (83, 3, 3 e 3);

  • 88357 (883, 5 e 7).

La congettura è con ogni probabilità vera, perché include, tra gli altri, tutti gli interi che si possono scrivere utilizzando solo le cifre 2, 3, 5 e 7 e tra questi è estremamente probabile che vi siano infiniti numeri di Poulet, come pure infiniti primi e infiniti numeri di svariate altre categorie.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • 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.