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 Paulet (1887 – 1946), che ne fece oggetto di studi e pubblicò la prima tabella 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 potenze 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 che non sia una potenza di 2), 225 mod 25 = 7 (il minimo valore dispari), ma la formula sembra 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 Carmichael;

  • i numeri di Fermat composti;

  • i prodotti di numeri di Fermat;

  • i numeri di Mersenne Mn composti, con n primo o numero di Poulet; se n è un numero di Poulet, Mn è composto, quindi da un numero di Poulet n se ne ricava un altro Mn, e questo dimostra che esistono infiniti numeri di Poulet dispari.

 

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.

 

Malo dimostrò nel 1903 che se n è un numero di Poulet, anche m = 2n – 1 lo è e non è primo perché è divisibile per 2a – 1, dove a è uno dei divisori propri di n maggiori di 1.

 

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.

 

Nel 1950 Erdös dimostrò che se p è un primo maggiore di 3, (4^p – 1) / 3 è un numero di Poulet.

 

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.

 

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.

 

Pomerance dimostrò che per x 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.

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

 

La tabella seguente riporta il numero di numeri di Poulet minori di 10n, per n fino a 19 (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.