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

Primi di Sophie Germain

Teoria dei numeri 

Si chiamano “primi di Sophie Germain” i numeri primi p tali che 2p + 1 sia primo, come 3 e 5; la loro importanza è storicamente legata all’ultimo teorema di Fermat, che afferma che non vi sono soluzioni intere dell’equazione xn + yn = zn con n > 2.

 

Il problema si riduce al caso in cui l’esponente sia un primo dispari p, perché se n = km, l’equazione si può riscrivere come xkm + ykm = zkm, quindi può esistere una soluzione per n composto solo se esiste per i suoi fattori primi. Fermat stesso aveva fornito una dimostrazione per il caso n = 4, escludendo quindi le potenze di 2 maggiori di 2.

 

Eulero dimostrò poi la validità per n = 3, ma all’inizio del XIX secolo, dopo 2 secoli di sforzi erano stati dimostrati solo due casi particolari e, quel che era peggio, con dimostrazioni differenti e non applicabili ad altri casi.

 

Marie-Sophie Germain (Parigi, 1/4/1776 – Parigi, 27/6/1831) dimostrò nel 1825 che l’ultimo teorema di Fermat vale per tutti i primi dispari p tali che 2p + 1 sia primo se né x, né yz sono multipli di p. Fu la prima dimostrazione parziale, ma valida per un’intera grande categoria di primi e non per casi singoli. Per di più apparve subito chiaro che tali primi sono probabilmente infiniti.

I primi tali p tali che 2p + 1 sia primo sono chiamati “primi di Sophie Germain” in suo onore.

 

Sophie Germain era un’autodidatta, la cui passione per la matematica era violentemente osteggiata anche dai genitori. A causa dei pregiudizi sulle donne che si occupavano di scienza, non poté frequentare l’università, ma si faceva mandare appunti di lezioni sotto lo pseudonimo di Antoine-Auguste Le Blanc e con lo stesso nome inviava risposte ai problemi e osservazioni. Tali osservazioni erano a volte così acute, che il docente, Lagrange, volle incontrare “il” suo studente, restando naturalmente piuttosto stupito. Lagrange divenne amico e mentore di Sophie Germain, che però dovette continuare a pubblicare i suoi lavori con lo pseudonimo di M. Le Blanc. Con tale nome intrattenne per anni una corrispondenza con Gauss, che scoprì la verità solo quando lei dovette intervenire personalmente per assicurarsi che il matematico tedesco non subisse danni nel corso di un’invasione francese del suo paese. Gauss rimase sorpreso e quasi divertito d’essere stato beffato e non mutò mai il rispettoso atteggiamento col quale trattava “il” collega.

 

Sfortunatamente Sophie Germain non pubblicò buona parte dei suoi lavori, che furono riscoperti in tempi relativamente recenti, quindi alcune delle sue scoperte furono attribuite ad altri, che vi arrivarono indipendentemente. Un caso eclatante sono le dimostrazioni che il teorema vale per p = 5, normalmente attribuita a Adrien-Marie Legendre (1823) o Dirichlet (1923), e per p = 7 normalmente attribuita a G. Lamé (1839), mentre questi casi sono tra quelli coperti dalle dimostrazioni di Sophie Germain, nel caso di x, y e z non multipli di p.

 

I suoi lavori spinsero Sophie Germain a suddividere il problema in due casi: nel primo, x, y e z non sono multipli di p, nel secondo una e una sola delle tre variabili lo è; se due variabili sono multiple di p lo è anche la terza, nel qual caso, dividendole per p ci si riconduce a una soluzione più semplice.

Da allora questa divisione si è dimostrata importante, perché nel cercare dimostrazioni per esponenti di forme particolari, il primo caso si è dimostrato più trattabile del secondo.

 

Sophie Germain dimostrò che il primo caso del teorema di Fermat vale per p, se esiste un primo ausiliario q = 2kp + 1 che soddisfi due condizioni:

  • xp + yp + zp = 0 mod q implica che x, y o z siano multipli di q;

  • p non è residuo di una potenza p-esima modulo q.

In particolare le due condizioni sono soddisfatte per k = 1, quindi basta  che q = 2p + 1 sia primo, perché non esistano soluzioni nel primo caso. Infatti, per ogni intero m non multiplo di p, m2p = mq – 1 ≡ 1 mod q per il piccolo teorema di Fermat, quindi m2p – 1 = (mp + 1)(mp – 1) ≡ 0 mod q, ossia mp ≡ ±1 mod q e modulo q l’equazione diverrebbe ±1 + ±1 = ±1, che è impossibile, mentre per lo stesso motivo p non può residuo di una potenza p-esima modulo q.

La verifica della seconda condizione è semplificata dal teorema di Eulero, che afferma che n è residuo di una potenza p-esima modulo q se e solo se Formula per il teorema di Eulero.

Lo stesso teorema implica che i primi ausiliari devono essere della forma 2kp + 1, perché se MCD(p, q – 1) = 1, avremmo pp – 1 ≡ 1 mod q e quindi p sarebbe residuo di una potenza p-esima modulo q per il piccolo teorema di Fermat.

 

La matematica francese dimostrò anche che:

  • la prima condizione equivale all’affermazione che non esistono due residui di potenze p-esime consecutivi modulo q;

  • se p non è residuo di una potenza p-esima modulo q, una delle incognite x, y o z è divisibile per p2.

Il secondo risultato è comunemente attribuito a Legendre, che lo pubblicò, ma attribuendolo esplicitamente a Sophie Germain.

 

Sophie Germain dimostrò che la prima condizione vale se almeno uno dei numeri 4p + 1, 6p + 1, 8p + 1, 10p + 1, 14p + 1 o 16p è 1 è primo e verificando vari casi nei quali un primo ausiliario di questo genere permette di soddisfare anche la seconda condizione, dimostrò che il teorema vale nel primo caso per numerosi primi.

Per nessun primo p esiste un primo ausiliario della forma 6p + 1 che soddisfi le due condizioni, ma le altre forme permettono in genere di trovare vari primi ausliari per ogni primo p; Legendre e Sophie Germain si fermarono a 197, perché per p = 197 il minimo primo ausiliario possibile è 7487 e i calcoli necessari per verificarne l’idoneità erano pressoché impossibili da svolgere a mano.

 

Il piano d’attacco per il primo caso, che la matematica francese suggerì in una lettera a Gauss del 12/5/1819, era di trovare per ogni primo p un primo ausiliario q = 2kp + 1 che soddisfi la condizione del suo teorema. Per esempio, per n = 5, un primo ausiliario valido è 11, perché i resti dei numeri 15, 25, 35, … 105 modulo 11 sono solo 1 e 10, che non sono consecutivi.

Il passo successivo sarebbe stato dimostrare che per ogni primo esistono infiniti primi ausiliari e che quindi in ogni soluzione il prodotto delle tre variabili sarebbe stato multiplo di infiniti primi, cosa ovviamente impossibile.

Guglielmo Libri suggerì però nel 1829 che che per ogni primo il numero di primi ausiliari è finito, affermazione dimostrata da A.E. Pellet nel 1886. Nel 1909 L.E. Dickson dimostrò che se q > (p – 1)2(p – 2)2 + 6p – 2 , la prima condizione di Sophie Germain è violata e q non può essere un primo ausiliario.

Il piano era perciò condannato all’insuccesso in generale, a causa del numero limitato di primi ausiliari disponibili: era infatti possibile che per nessuno di essi la seconda condizione fosse soddisfatta. La stessa matematica francese era consapevole che il metodo non poteva funzionare sempre, perché aveva dimostrato che per p = 3 gli unici primi ausiliari sono 7 e 13, perché per k > 2 tutti i primi della forma 6k + 1 hanno almeno due residui cubici consecutivi; tuttavia questo caso era stato risolto da Eulero e, avendo esaminato tutti i primi minori di 100 con k da 1 a 10, sperava che potesse funzionare almeno per un insieme ampio, se non infinito, di primi.

 

In seguito il teorema fu esteso, dimostrando che non vi sono soluzioni se esiste un primo della forma 2kp + 1, per vari valori di k (v. ultimo teorema di Fermat).

 

I primi di Sophie Germain inferiori a 1000 sono: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953.

Qui trovate i primi di Sophie Germain fino a 108 (4 Mbyte).

 

I massimi primi di Sophie Germain noti sono riportati nella tabella seguente.

Numero

Numero di cifre

Scopritore e anno

137211941292195 • 2171960 − 1

51780

Tímea Csajbok, Gábor Farkas, Antal Járai, Zoltán Járai, János Kasza, 2006

48047305725 • 2172403 − 1

51910

David Underbakke, 2007

607095 • 2176311 − 1

53081

Tom Wu, 2009

620366307356565 • 2253824 − 1

76424

Tímea Csajbok, Gábor Farkas, Antal Járai, Zoltán Járai, János Kasza, 2009

648621027630345 • 2253824 − 1

76424

Tímea Csajbok, Gábor Farkas, Antal Járai, Zoltán Járai, János Kasza, 2009

183027 • 2265440 − 1

79911

Tom Wu, 2010

18543637900515 • 2666667 − 1

200701

Philipp Bliedung, nella ricerca distribuita PrimeGrid, 2012

2618163402417 • 21290000 − 1

388342

PrimeGrid, 2016

 

Il massimo primo di Sophie Germain palindromo noto è 101046 + 532181235 • 10519 + 1 (Dubner, 1994).

Il massimo palindromo noto con anche 2p + 1 palindromo è 3636363616161636161616361636163636163616363636163616161636361616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161636361616163616363636163616363616361636161616361616163636363 (Dubner, 1999), che fa parte di una catena di Cunningham di prima specie di 3 primi, tutti palindromi.

 

Se p è un primo di Sophie Germain e q = 2p + 1:

  • q ha come radici primitive tutti e soli i suoi nonresidui quadratici, tranne –1.

  • se p è della forma 4k + 1, 2 è radice primitiva di q;

  • se p è della forma 4k + 3, –2 è radice primitiva di q.

 

Un primo p è un primo di Sophie Germain se e solo se 22p ≡ 1 mod 2p + 1.

 

A parte 2 e 3, tutti i primi di Sophie Germain sono della forma 3k + 1.

 

Se p è un primo della forma 4k + 3, 2p + 1 è primo se e solo se divide Mp, dove Mp è un numero di Mersenne (Eulero).

 

I primi di Sophie Germain sono soluzioni dell’equazione n’ + (2n + 1)’ = 2, dove n’ è la derivata aritmetica di n.

 

Oltre che in relazione alla storia dell’ultimo teorema di Fermat, i primi di Sophie Germain sono importanti sia perché se p è un primo di Sophie Germain, q = 2p + 1 è un primo sicuro, sia perché se fossero infiniti, si potrebbe ridurre il numero di operazioni della versione originale dell’algoritmo AKS (v. numeri primi).

Un altro utilizzo recente è che se p è un primo di Sophie Germani della forma 20k + 3, 20k + 9 o 20k + 11, q = 2p + 1 può essere usato come generatore di numeri pseudo-casuali: le cifre dello sviluppo decimale di 1 / q si ripetono con periodo q – 1 e ogni cifra non ha un legame ovvio con le precedenti. Per esempio, prendendo p = 11 e quindi q = 23, si ottiene la sequenza di cifre 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3. Un grave difetto di questi generatori è che non tutte le cifre compaiono esattamente lo stesso numero di volte: nell’esempio infatti si vede che le cifre 3 e 6 compaiono 3 volte e le altre 2.

 

Nel 2012 Zhi-Wei Sun propose due congetture sui primi di Sophie Germain, conseguenze della sua versione dell’ipotesi di Schinzel:

  • se gn è il minimo primo della n-esima coppia, Formula che coinvolge i primi di Sophie Germain, tranne che per n uguale a 3 e 4;

  • se Formula per la definizione di S(n)Formula che coinvolge i primi di Sophie Germain è strettamente crescente per n > 12 e tende a 1.

Sun verificò le congetture per n fino a 200000 (g200000 = 42721961).

 

Il grande problema insoluto sui primi di Sophie Germain è se siano infiniti o meno. Dalla congettura di Dickson seguirebbe che siano infiniti, come tutti gli esperti ritengono.

Secondo una congettura di Hardy e Littlewood, il numero di primi di Sophie Germain minori di n tende a 2 * C * n / log(n)^2, dove C2 è la costante dei primi gemelli.

Un’approssimazione migliore per il numero di primi di Sophie Germain minori di n è Formula approssimata per il numero di primi di Sohie Germain minori di n.

La tabella seguente mostra l’accordo tra queste previsioni e il numero effettivo di primi di Sophie Germain  (Donovan Johnson, Eric W. Weisstein, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Primi di Sophie Germain minori di n

2 * C * n / log(n)^2

Formula approssimata per il numero di primi di Sohie Germain minori di n

10

3

2.4902848078

2.9579174588

102

10

6.2257120195

10.1986865854

103

37

27.6698311976

39.0975563907

104

190

155.6428004864

194.5765938558

105

1171

996.1139231132

1165.9457761623

106

7746

6917.4577993970

7810.6384341282

107

56032

50822.1389343456

56127.9446571583

108

423140

389107.0012160832

423294.3865586159

109

3308859

3074425.6886209046

3307887.8910953272

1010

26569515

24902848.0778293270

26568824.0341491632

1011

218116524

205808661.8002423720

218116101.7833225842

1012

1822848478

1729364449.8492588205

1822875219.2866128852

 

Nel frattempo è stato dimostrato che esistono infiniti primi p tali che 2p + 1 è primo o ha solo due fattori e un teorema analogo vale per 8p + 1.

Nel 1969 M. Goldfeld dimostrò che per una frazione non nulla dei primi p il massimo primo che divide p – 1 è maggiore di p^(1 / 2 + c), con c costante vicina a 1 / 12.

Nel 1985 E. Fouvry dimostrò per n abbastanza grande i primi p inferiori a n tali che il massimo primo che divide p – 1 sia maggiore di p^(2 / 3) sono almeno c * n / log(n), per una costante c.

 

Nel 1980 B.J. Powell dimostrò che fissati a e b, i primi p tali che ap + b sia primo hanno densità nulla, quindi esistono infiniti primi non di Sophie Germain.

 

Il minimo quadrato magico di primi di Sophie Germain noto è il seguente (Felice Russo).

1481

1889

2063

2393

1811

1229

1559

1733

2141

 

Il minimo quadrato magico di primi di Sophie Germain di ordine 4 noto è il seguente (John E. Everett, 2000).

23

719

1229

1031

1049

1019

281

653

491

251

1451

809

1439

1013

41

509

 

Naturalmente in questi casi sostituendo ogni primo p con 2p + 1 si ottiene un altro quadrato magico di numeri primi.

 

Sono stati anche considerati i primi p tali che 2p – 1 sia primo; tali primi però non hanno alcuna importanza particolare né in relazione all’ultimo teorema di Fermat, né per la crittografia.

 

Questi primi sono soluzioni dell’equazione n’ + (2n – 1)’ = 2, dove n’ è la derivata aritmetica di n.

 

R.D. Carmichael dimostrò nel 1904 che (p – 1)!4 – 1 è divisibile per p e 2p – 1 se e solo se p e 2p – 1 sono entrambi primi.

 

I primi di questo genere minori di 1000 sono: 2, 3, 7, 19, 31, 37, 79, 97, 139, 157, 199, 211, 229, 271, 307, 331, 337, 367, 379, 439, 499, 547, 577, 601, 607, 619, 661, 691, 727, 811, 829, 877, 937, 967, 997.

Qui trovate i primi di questo genere fino a 108 (4 Mbyte).

log(log(n)) / log(log(log(n)))

Bibliografia

  • Aczel, Amir D.;  L’enigma di Fermat, Milano, Il saggiatore, 1998.
  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • 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.