776 – algebra
I numeri di Fermat sono quelli della forma Fn = 2^(2^n)) + 1. Una congettura di Fermat affermava che se n è primo, allora Fn è primo (“numero primo di Fermat”). I primi numeri in effetti lo sono: F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537. Peccato che non si conosca nessun altro primo di Fermat. Ma non è questo il problema di oggi. Dimostrate che vale sempre l’uguaglianza F0F1F2…Fk−1 = Fk − 2.
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p776.html; la risposta verrà postata lì il prossimo mercoledì. Problema 28 da Stephen Siklos, Advanced Problems in Mathematics.)
Non è che mi entusiasmi dover dare una dimostrazione e nemmeno dover fare molti calcoli, però…
Se vediamo i Numeri di Fermat in base binaria, troviamo un formato molto semplice:
F(0) = 3 = 2^1 + 1 = 11_bin
F(1) = 5 = 2^2 + 1 = 101_bin
F(2) = 17 = 2^4 + 1 = 1’0001_bin
F(3) = 257 = 2^8 + 1 = 1’0000’0001_bin
F(4) = 65’537 = 2^16 + 1 = 1’0000’0000’0000’0001_bin
F(5) = 4’294’967’297 = 2^32 + 1 = 1’0000’0000’0000’0000’0000’0000’0000’0001_bin
…tuttavia quest’ultimo non è un numero primo (è divisibile per 641), ma resta sempre un Numero di Fermat.
Al volo si può notare che F(0) = F(1) -2 (questo non era stato richiesto, ma è un buon inizio); moltiplicare tra loro due numeri binari non è velocissimo ma è semplice, e farlo con numeri così composti è molto semplice:
11 x 101 = 1111 = 1’0001 – 10
che equivale a F(0) x F(1) = F(2) – 2
1111 x 1’0001 = 1111’1111 = 1’0000’0001 – 10
che equivale a [ F(0) x F(1) ] x F(2) = F(3) – 2
1111’1111 x 1’0000’0001 = 1111’1111’1111’1111 = 1’0000’0000’0000’0001 – 10
che equivale a [ F(0) x F(1) x F(2) ] x F(3) = F(4) – 2
Non credo serva continuare :-)
“Non credo serva continuare” = “La facile dimostrazione per induzione è lasciata al lettore”? :-D
Carina l’idea di pensare in base 2, in effetti è anche abbastanza naturale. Non so però se questo aiuti a dimostrare formalmente l’uguaglianza. Ovviamente la dimostrazione per induzione è abbastanza diretta e richiede pochissimi calcoli.
Curiosità: questa formula compare in diversi testi (fra cui ovviamente la pagina Wikipedia sui numeri di Fermat, ma anche “Proofs from THE BOOK” di Aigner e Ziegler, peraltro già recensito su queste pagine) come parte di una delle molte dimostrazioni dell’infinità dei numeri primi.
Ovviamente quanto sopra è tutto scritto nella nota 20 del libro di Siklos e nell’appendice alla soluzione di .mau. :-)
Nella stessa nota, Siklos, oltre a scrivere “Aigler” per “Aigner”, mi pare che confonda la congettura di Goldbach con quella dei primi gemelli. Sbaglio?
confermo entrambi gli errori (stavolta non miei :-) )