Un generatore di numeri primi

“Ehi, guarda, ho scoperto un generatore di numeri primi!”.

“Uhm”.

“Come uhm? Guarda:”.

P(n) = n² + n + 41

“Uhm”.

“Ma insomma, cosa c'è che non va? P(0) fa 41, che è un numero primo”.

“Questo è vero”.

“P(1) fa 43, che è ancora primo”.

“Vero anche questo”.

“P(2) fa 47, P(3) fa 53, tutti primi”.

“Certo”.

“E posso andare avanti così, i numeri successivi sono 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033”.

“Molto bene”.

“Quindi sto generando numeri primi”.

“Sì, certo. Hai calcolato P(41)?”.

“Aspetta che faccio i calcoli”.

“Forse non hai bisogno di fare tutti i conti per dire se è primo o no”.

“Perché?”.

“Beh, stai sommando tre numeri: 41² + 41 + 41”.

“Oh”.

“Come vedi, 41 è un fattore comune a tutti e tre”.

“Uffa, risulta un numero composto”.

“Sì, 41 × 43. Prova anche a calcolare P(40)”.

“Questo sarà primo, dai”.

“Prova”.

“Allora: 40² + 40 + 41”.

“Che, volendo, puoi scrivere come 40² + 80 + 1”.

“E perché questa scrittura dovrebbe essere meglio?”.

“Perché è uguale a (40 + 1)², cioè 41²”.

“Oh, è composto anche questo”.

“Già”.

“Ma ci sarà un polinomio che funziona, no?”.

“Cioè un polinomio P(n) a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo?”.

“Uh, mamma mia, che pignoleria. Sì, un polinomio fatto così”.

“Certo, eccotene uno: P(n) = 2”.

“Eh? Ma no, che genera numeri primi diversi!”.

“Allora lo vuoi anche non costante”.

“Sì! Quanto sono noiosi questi Veri Matematici”.

“Capisci che bisogna esser precisi, altrimenti poi non si sa bene quello che si vuole”.

“Va bene, va bene. Esiste un polinomio così?”.

“No”.

“Ma come? Tra tutti gli infiniti polinomi che si possono costruire, non ce n'è nemmeno uno che genera solo numeri primi?”.

“Nemmeno uno”.

“Santo cielo. E perché?”.

“Immagina che ne esista uno, per esempio uno che assuma il valore 43 quando n = 1”.

“Come fa il mio”.

“Esatto: possiamo scrivere che P(1) = 43”.

“Bene”.

“Ora prova a calcolare P(1 + 43k)”.

“Cos'è k?”.

“Un qualunque numero intero”.

“Eh, ma come faccio a calcolare P(1 + 43k) se non so come sia fatto P?”.

“Allora, partiamo dall'inizio. Supponiamo che esista P, che sarà scritto in maniera molto generica in questo modo:”.

P(n) = a_nxⁿ + a_n−1xⁿ⁻¹ + … + a₁x + a₀

“Gulp”.

“Prova a calcolare, adesso, P(1 + 43k)”.

“Vediamo, risulterà una cosa del genere:”.

P(1 + 43k) = a_n(1 + 43k)ⁿ + a_n−1(1 + 43k)ⁿ⁻¹ + … + a₁(1 + 43k) + a₀

“Bene. Comincia a svolgere”.

“Stai scherzando?”.

“No, ma non devi svolgere tutto tutto. Per esempio, da tutte quelle parentesi del tipo (1 + 43k) elevate a una qualche potenza puoi estrarre il primo termine, che è 1”.

“Eh, ma poi c'è un sacco di altra roba”.

“Certo, cominciamo dal facile: ognuna di quelle parentesi genera sicuramente un 1”.

“Va bene. Ognuno di quegli 1 viene moltiplicato per un coefficiente diverso”.

“E quindi puoi cominciare a scrivere una cosa del genere:”.

P(1 + 43k) = a_n + a_n−1 + … + a₁ + a₀ + (altra roba)

“Non mi sembra una scrittura molto matematica, però va bene”.

“Ti ricordi quanto faceva P(1)?”.

“Abbiamo detto 43”.

“E, però, se sostituisci 1 nel tuo generico polinomio cosa ottieni?”.

“Ah, facile, ottengo a_n + a_n−1 + … + a₁ + a₀”.

“Benissimo. Quindi sai che a_n + a_n−1 + … + a₁ + a₀ = 43”.

“Ah. Ma allora posso scrivere così:”.

P(1 + 43k) = 43 + (altra roba)

“Certo. Adesso concentriamoci sull'altra roba”.

“E come facciamo? Dobbiamo svolgere tutte quelle potenze di binomio, non si finisce più”.

“Non facciamolo. Sarai d'accordo con me se ti dico che lo sviluppo di qualunque potenza del tipo (1 + 43k)ⁿ contiene un termine uguale a 1, e tanti altri termini che contengono, almeno una volta, il fattore 43?”.

“Eh, sì, giusto. Tutti i termini dopo il primo 1 contengono le varie potenze di 43k. Non ricordo bene il calcolo dei coefficienti, però”.

“Beh, non importa ai fini dei calcoli che stiamo facendo. Senza conoscere nessuna regola, puoi immaginare di dover calcolare quella potenza in questo modo:”.

(1 + 43k)ⁿ = (1 + 43k)(1 + 43k) … (1 + 43k)

“Ah, certo”.

“Quando ti calcoli tutti i prodotti, vedi che c'è un solo caso in cui fai 1×1×…×1, mentre in tutti gli altri casi almeno un termine del tipo 43k lo devi prendere”.

“Giusto, e quindi un 43 c'è sempre”.

“Ottimo. Ed ecco allora che possiamo semplificare ulteriormente il calcolo che stavamo facendo, mettendo in evidenza il fattore comune 43:”.

P(1 + 43k) = 43 + 43(altra roba ancora)

“Bene, e quindi?”.

“E quindi P(1 + 43k) è divisibile per 43”.

“E allora?”.

“E allora non è primo, dunque P(n) non può assumere valori primi per ogni valore di n”.

“Ah!”.

“Volendo essere più precisi, bisognerebbe distinguere due casi nell'espressione P(1 + 43k) = 43 + 43(altra roba ancora)”.

“Quali?”.

“Se la parentesi (altra roba ancora) fosse uguale a 0, allora il risultato sarebbe 43, che è effettivamente un numero primo”.

“Allora potrebbe succedere?”.

“Eh, questo significherebbe che P(1 + 43k) dovrebbe essere uguale a 43 per infiniti valori di k”.

“E questo non è possibile?”.

“Lo è, ma un polinomio che assume infiniti valori uguali è un polinomio costante”.

“Ah, il caso banale P(n) = 43”.

“Già. Se vuoi un polinomio non costante e in grado di generare solo numeri primi, non ce la fai. Non esiste. Naturalmente 43 è solo un esempio, puoi rifare tutta la dimostrazione sostituendo, al posto di 43, un qualsiasi numero p primo. Quindi, niente da fare: non esiste un polinomio P(n) non costante a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo”.

“Oh. Peccato”.

“Già”.