Numero di Fermat (original) (raw)

Da Wikipedia, l'enciclopedia libera.

Un numero di Fermat, chiamato così dal matematico francese Pierre de Fermat, è un numero intero esprimibile come:

F n = 2 2 n + 1 , {\displaystyle F_{n}=2^{2^{n}}+1,} $F_{n}=2^{2^{n}}+1,$

con n {\displaystyle n} $n$ intero non negativo.

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

F 0 = 2 2 0 + 1 = 3 {\displaystyle F_{0}=2^{2^{0}}+1=3} $F_{0}=2^{2^{0}}+1=3$

F 1 = 2 2 1 + 1 = 5 {\displaystyle F_{1}=2^{2^{1}}+1=5} $F_{1}=2^{2^{1}}+1=5$

F 2 = 2 2 2 + 1 = 17 {\displaystyle F_{2}=2^{2^{2}}+1=17} $F_{2}=2^{2^{2}}+1=17$

F 3 = 2 2 3 + 1 = 257 {\displaystyle F_{3}=2^{2^{3}}+1=257} $F_{3}=2^{2^{3}}+1=257$

F 4 = 2 2 4 + 1 = 65 537 {\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:

F 5 = 2 2 5 + 1 = 2 32 + 1 = 4 294 967 297 = 641 ⋅ 6 700 417. {\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 2 n + 1 + 1 {\displaystyle K2^{n+1}+1} $K2^{n+1}+1$ , risultato che venne migliorato da Lucas nel 1878 con la considerazione che tali divisori devono anche essere del tipo L 2 n + 2 + 1 {\displaystyle L2^{n+2}+1} $L2^{n+2}+1$ , per gli F n {\displaystyle F_{n}} $F_{n}$ con n > 1 {\displaystyle n>1} $n>1$ , dove K {\displaystyle K} $K$ e L {\displaystyle L} $L$ sono interi positivi.

Nel caso di F 5 {\displaystyle F_{5}} $F_{5}$ , per L = 1 , 2 , 3 , 4 , 5 {\displaystyle L=1,2,3,4,5} $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 F 5 {\displaystyle F_{5}} $F_{5}$ .

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:

F 6 = 274177 ⋅ 67280421310721 {\displaystyle F_{6}=274177\cdot 67280421310721} $F_{6}=274177\cdot 67280421310721$ (Clausen, Landry e Le Lasseur, 1880)
F 7 = 59649589127497217 ⋅ 5704689200685129054721 {\displaystyle F_{7}=59649589127497217\cdot 5704689200685129054721} $F_{7}=59649589127497217\cdot 5704689200685129054721$ (Morrison e Brillhart, 1970)
F 8 = 1238926361552897 ⋅ P 62 {\displaystyle F_{8}=1238926361552897\cdot P62} $F_{8}=1238926361552897\cdot P62$ (Brent e Pollard, 1980)
F 9 = 2424833 ⋅ 7455602825647884208337395736200454918783366342657 ⋅ P 99 {\displaystyle F_{9}=2424833\cdot 7455602825647884208337395736200454918783366342657\cdot P99} $F_{9}=2424833\cdot 7455602825647884208337395736200454918783366342657\cdot P99$ (Western, 1903 / Lenstra, Manasse e altri, 1990)
F 10 = 45592577 ⋅ 6487031809 ⋅ 4659775785220018543264560743076778192897 ⋅ P 252 {\displaystyle F_{10}=45592577\cdot 6487031809\cdot 4659775785220018543264560743076778192897\cdot P252} $F_{10}=45592577\cdot 6487031809\cdot 4659775785220018543264560743076778192897\cdot P252$ (Selfridge, 1953 / Brillhart, 1962 / Brent, 1995)
F 11 = 319489 ⋅ 974849 ⋅ 167988556341760475137 ⋅ 3560841906445833920513 ⋅ P 564 {\displaystyle F_{11}=319489\cdot 974849\cdot 167988556341760475137\cdot 3560841906445833920513\cdot P564} $F_{11}=319489\cdot 974849\cdot 167988556341760475137\cdot 3560841906445833920513\cdot P564$ (Cunningham, 1899 / Brent e Morain, 1988)

dove P x {\displaystyle Px} $Px$ indica un fattore primo di x {\displaystyle x} $x$ cifre.[1]

Si può comunque dimostrare (in base al test di primalità noto come test di Pépin) che F n {\displaystyle F_{n}} $F_{n}$ è primo se e solo se 3 ( F n − 1 ) / 2 ≡ − 1 ( mod F n ) . {\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 non correlati. Ad esempio, Gauss dimostrò che si possono fare le costruzioni con riga e compasso dei poligoni regolari con n {\displaystyle n} $n$ lati se e solo se n {\displaystyle n} $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 F 3329780 {\displaystyle F_{3329780}} $F_{3329780}$ . Questo numero primo possiede ben 1002367 cifre, ed è

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

Al momento della dimostrazione, F 3329780 {\displaystyle F_{3329780}} $F_{3329780}$ diventava quindi il più grande numero di Fermat di cui fosse conosciuto almeno un fattore primo e di conseguenza la non primalità.[2]

Il 18 luglio 2009 il GIMPS ha annunciato la scoperta di un divisore di F 19 {\displaystyle F_{19}} $F_{19}$ :

8962167624028624126082526703 ⋅ 2 22 + 1 {\displaystyle 8962167624028624126082526703\cdot {2^{22}+1}} $8962167624028624126082526703\cdot {2^{22}+1}$ divide F 19 {\displaystyle F_{19}} $F_{19}$ .[1]

Il 13 febbraio 2015 PrimeGrid ha annunciato di aver scoperto un divisore primo di F 2662088 {\displaystyle F_{2662088}} $F_{2662088}$ :

267 ⋅ 2 2662090 + 1. {\displaystyle 267\cdot {2^{2662090}}+1.} $267\cdot {2^{2662090}}+1.$ [3]

In un sistema numerico binario, tutti i numeri di Fermat sono palindromi (3=11; 5=101; 17=10001; 65537=10000000000000001), e tutti i primi di Fermat sono quindi palindromi primi.

I numeri di Fermat soddisfano le seguenti relazioni di ricorrenza valide per _n_≥2, che possono essere provate tramite induzione:

F n = ( F n − 1 − 1 ) 2 + 1 {\displaystyle F_{n}=(F_{n-1}-1)^{2}+1} $F_{n}=(F_{n-1}-1)^{2}+1$

F n = F n − 1 + 2 2 n − 1 F 0 ⋯ F n − 2 {\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}} $F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}$

F n = F n − 1 2 − 2 ( F n − 2 − 1 ) 2 {\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}} $F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}$

F n = F 0 ⋯ F n − 1 + 2. {\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2.} $F_{n}=F_{0}\cdots F_{n-1}+2.$

Dall'ultima relazione si deduce il cosiddetto teorema di Goldbach: ogni coppia di numeri di Fermat è coprima, ovvero nessun numero primo divide due numeri di Fermat diversi. Infatti, se F i {\displaystyle F_{i}} $F_{i}$ e F j {\displaystyle F_{j}} $F_{j}$ (con i < j {\displaystyle i<j} $i<j$ ) avessero un fattore comune a > 1 {\displaystyle a>1} $a>1$ , questo dividerebbe sia

F 0 ⋯ F j − 1 {\displaystyle F_{0}\cdots F_{j-1}} $F_{0}\cdots F_{j-1}$

che

F j = F 0 ⋯ F j − 1 + 2 {\displaystyle F_{j}=F_{0}\cdots F_{j-1}+2} $F_{j}=F_{0}\cdots F_{j-1}+2$

e quindi a {\displaystyle a} $a$ dividerebbe 2, ossia a = 2 {\displaystyle a=2} $a=2$ , il che è impossibile perché tutti i numeri di Fermat sono dispari. Quindi due numeri di Fermat sono sempre coprimi.

Da questo si può dimostrare il teorema dell'infinità dei numeri primi: poiché esistono infiniti numeri di Fermat, e ogni numero primo ne divide al più 1, devono esistere infiniti primi.

4.^ Per la 4° relazione di ricorrenza riportata sopra, F n − 2 {\displaystyle F_{n}-2} $F_{n}-2$ è sempre divisibile non soltanto per 3 ma per F n − 1 ! {\displaystyle F_{n-1}!} $F_{n-1}!$ e quindi per ogni F x {\displaystyle F_{x}} $F_{x}$ con x < n {\displaystyle x<n} $x<n$ .

Fermat Search - Progetto di ricerca dei divisori dei Numeri di Fermat per trovare un numero primo più grande.
Numero primo di Mersenne
Costruzione di poligoni regolari
The Prime Pages
La pagina di John Cosgrave, su spd.dcu.ie. URL consultato il 3 ottobre 2005 (archiviato dall'url originale il 2 dicembre 2005).

Controllo di autorità	GND (DE) 4672709-7 · J9U (EN, HE) 987007532614505171