Esercizio numero 7, Foglio 1
(Numeri di Fermat) Per ogni numero naturale n, si definisce l'ennesimo numero di Fermat come F(n)=2^2^n+1;
(a) Dimostrare: se 2^m+1 è primo, allora m è potenza di 2;
(b) Far vedere che F(n) è primo per 1<=n<=4;
(a) Dobbiamo dimostrare che se 2^m+1 è primo allora m è potenza di 2 ovvero m = 2^k per qualche k
Per assurdo ipotizziamo che m non sia potenza di due, dobbiamo considerare due casi diversi
(a.1) m è un primo diverso da 2
(a.2) m non è primo
(a.1) Possiamo dimostrare che per ogni primo m!=2, 2^m+1 è divisibile per 3, o equivalentemente che 2^m+1 è congruo 0 (mod 3) o che equivalentemente 2^m è congruo -1 (mod 3)
Allora un numero s modulo 3 può essere congruo a -1, 0 o +1
è facile dimostrare che 2^m, per un qualsiasi m (primo o non) non sarà mai congruo a 0 modulo 3
infatti 2^m può essere scritto come prodotto di 2
2^m= 2*..-m volte-..*2
facendo modulo 3 questo prodotto può essere scritto come prodotti di -1
2^m (mod 3) = -1*..-m volte-..*-1=(-1)^m
e per ogni m primo (diverso da due, e quindi m dispari) (-1)^m=-1
quindi abbiamo dimostrato che 2^m+1 (mod 3) è congruo a 0, ma noi abbiamo premesso che 2^m+1 sia primo
(nel caso in cui qualcuno ha il dubbio che 2^m+1 possa essere uguale a 3, rendendo vera la definizione che 2^m+1 (primo) (mod 3) sia congruo a 0, questa è vera solo per m=1 che ovviamente non è un numero primo)
quindi abbiamo dimostrato che per (a.1) ci stavamo sbagliando e che m non possa essere un numero primo diverso da 2
(a.2)
Ora ipotizziamo per assurdo che m sia un numero non primo
Possiamo scrivere che esistono p,q numeri primi
tali che m=p*q AND MCD(p,q)=1
Quindi possiamo scrivere:
F(m)=2^m+1=2^(p+q)+1
e, come per l'esercizio precedente
F(m)=(2^q)^p+1 (mod p) è congruo 3
F(m)=(2^p)^q+1 (mod q) è congruo 3
Per il teorema cinese del resto possiamo scrivere che
F(m)=2^m+1 (mod p*q=m) sia congruo 3
o equivalentemente
2^m-2=2(2^(m-1)-1) (mod m) sia congruo 0
ma questa è vera solo per m primo, e quindi contraddiciamo la nostra ipotesi assurda
Ora avendo dimostrato che le nostre due ipotesi (a.1) e (a.2) sono assurde e contraddicono la premessa, abbiamo dimostrato che
2^m+1 primo implica m è una potenza di 2
(b)
Per far vedere che F(n) è primo per 1<=n<=4, basta fare dei semplici calcoli
F(1) = 2^2^1+1=5
F(2) = 2^2^2+1=17
F(3) = 2^2^3+1=257
F(4) = 2^2^4+1=65537
è facile dimostrare con un Trial Divsion che gli ultimi 2 sono primi
