Numeri di Fermat: primalità, fattorizzazione e divisori noti

MatematicaAggiornato il 5,07 KB

Riassunto

Il testo illustra i numeri di Fermat, della forma 2^(2^n)+1, e la congettura errata di Fermat sulla loro primalità. Descrive la fattorizzazione di F5 data da Eulero e i risultati di Lucas sui divisori possibili, elencando le fattorizzazioni complete note fino al 2015. Presenta infine il test di Pépin e alcune applicazioni, come la costruzione di poligoni regolari con riga e compasso.

Punti chiave

  • F0–F4 sono primi: 3, 5, 17, 257 e 65537.
  • Eulero nel 1732 dimostrò che F5 = 641 · 6700417, smentendo la congettura di Fermat.
  • Ogni divisore di Fn è della forma K·2^(n+1)+1, risultato migliorato da Lucas nel 1878.
  • Il test di Pépin afferma che Fn è primo se e solo se 3^((Fn−1)/2) ≡ −1 (mod Fn).
  • Gauss dimostrò che un poligono regolare con n lati è costruibile con riga e compasso se n è prodotto di una potenza di 2 per numeri di Fermat primi distinti.

Mettiti alla prova

ermat credeva, erroneamente, che tutti i numeri della forma indicata sopra fossero numeri primi. In effetti, questo è vero per i primi cinque:

F0=220+1=3{\displaystyle F_{0}=2^{2^{0}}+1=3}F_{0}=2^{{2^{0}}}+1=3
F1=221+1=5{\displaystyle F_{1}=2^{2^{1}}+1=5}F_{1}=2^{{2^{1}}}+1=5
F2=222+1=17{\displaystyle F_{2}=2^{2^{2}}+1=17}F_{2}=2^{{2^{2}}}+1=17
F3=223+1=257{\displaystyle F_{3}=2^{2^{3}}+1=257}F_{3}=2^{{2^{3}}}+1=257
F4=224+1=65537{\displaystyle F_{4}=2^{2^{4}}+1=65\,537}F_{4}=2^{{2^{4}}}+1=65\,537

Ma nel 1732 Eulero dimostrò che Fermat si sbagliava, dando la fattorizzazione di F5:

F5=225+1=232+1=4294967297=641⋅6700417.{\displaystyle F_{5}=2^{2^{5}}+1=2^{32}+1=4\,294\,967\,297=641\cdot 6\,700\,417.\;}F_{{5}}=2^{{2^{5}}}+1=2^{{32}}+1=4\,294\,967\,297=641\cdot 6\,700\,417.\;

Nel 1770 dimostrò anche che ogni eventuale divisore di Fn è della forma K 2n+1 + 1, risultato che venne migliorato da Lucas nel 1878 con la considerazione che tali divisori devono anche essere del tipo L 2n+2 + 1 dove K ed L sono interi positivi.

Nel caso di F5, per L = 1, 2, 3, 4, 5 troviamo rispettivamente 129, 257, 385, 513, 641; Di questi, solo 257 e 641 sono primi, e 641 effettivamente divide F5.

Non è stato trovato nessun altro numero di Fermat primo, e anzi Si ritiene molto probabile che i numeri di Fermat primi siano in numero Finito.

A febbraio 2015, le uniche altre fattorizzazioni complete di numeri di Fermat sono le seguenti:

  • F6 = 274177 · 67280421310721 (Clausen, Landry e Le Lasseur, 1880)
  • F7 = 59649589127497217 · 5704689200685129054721 (Morrison e Brillhart, 1970)
  • F8 = 1238926361552897 · P62 (Brent e Pollard, 1980)
  • F9 = 2424833 · 7455602825647884208337395736200454918783366342657 · P99 (Western, 1903 / Lenstra, Manasse e altri, 1990)
  • F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252 (Selfridge, 1953 / Brillhart, 1962 / Brent, 1995)
  • F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513 · P564 (Cunningham, 1899 / Brent e Morain, 1988)

dove Px indica un fattore primo di x cifre.[1]

Si può comunque dimostrare (in base al test di primalità noto come test di Pépin) che Fn è primo sé e solo sé 3(Fn−1)/2≡−1(modFn).{\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}3^{{(F_{n}-1)/2}}\equiv -1{\pmod  {F_{n}}}.

I numeri di Fermat appaiono in contesti a prima vista completamente non correlati. Ad esempio, Gauss Dimostrò che si può costruire con riga e compasso un poligono regolare Con n lati sé e solo sé n è il prodotto di una potenza di 2 per un Prodotto finito di numeri di Fermat primi e distinti.

Nel luglio 2014 Raymond Ottusch ha trovato un divisore primo di F3329780. Questo numero primo possiede ben 1002367 cifre, ed è

193⋅23329782+1.{\displaystyle 193\cdot {2^{3329782}}+1.}193\cdot {2^{{3329782}}}+1.

Al momento della dimostrazione, F3329780 diventava quindi Il più grande numero di Fermat di cui fosse conosciuto almeno un fattore Primo e di conseguenza la non primalità.[2]

Scarica

PDF Word HTML

Domande frequenti

Perché Fermat credeva che tutti i numeri della forma 2^(2^n)+1 fossero primi?

Fermat riteneva erroneamente che tutti i numeri di questa forma fossero primi. Il testo osserva che questo è vero solo per i primi cinque, da F0 a F4.

Chi dimostrò che la congettura di Fermat era falsa?

Nel 1732 Eulero dimostrò che Fermat si sbagliava fornendo la fattorizzazione di F5 = 641 · 6700417.

Cos'è il test di Pépin?

È un test di primalità che permette di verificare se Fn è primo: Fn è primo se e solo se 3^((Fn−1)/2) ≡ −1 (mod Fn).

Mettiti alla prova

Schede di ripasso

Clicca una scheda per vedere la risposta.

Test

1. Quali sono i primi cinque numeri di Fermat, tutti primi?
2. Quale matematico dimostrò che F5 non è primo?
3. Quale poligono regolare è costruibile con riga e compasso secondo il risultato di Gauss?
4. Nel 1878 Lucas migliorò il risultato di Eulero sui divisori: cosa aggiunse?
5. Cosa indica il testo sulla possibilità che esistano altri numeri di Fermat primi?
6. Quale fattore primo di F3329780 fu trovato da Raymond Ottusch nel luglio 2014?

Domande generate con l'IA a partire dal documento: verifica le risposte con il testo.