Scomposizione in fattori primi e test di primalità
Un intero rivela se è primo, la sua scomposizione in fattori primi e l'elenco dei suoi divisori. Un numero primo ha solo due divisori : 1 e se stesso — la sua scomposizione comprende quindi un solo fattore, alla potenza 1.
Calcolatrice
Risultati
| — è primo? | — |
| Scomposizione in fattori primi | — |
| Numero di divisori positivi | — |
| Somma dei divisori | — |
| Elenco dei divisori | — |
Come si calcola una scomposizione in fattori primi
Divisione a tentativi per 2, 3, 5, 7… fino a √n: ogni divisore trovato è un fattore primo
Numero di divisori = prodotto degli (esponente + 1) di ogni fattore primo
Basta testare i divisori fino alla radice quadrata di n : se nessun fattore primo minore o uguale a √n divide n, allora n è primo — ogni eventuale divisore oltre quel limite avrebbe un « complemento » più piccolo già testato. Il numero totale di divisori si deduce direttamente dagli esponenti della scomposizione, senza doverli enumerare tutti.
Un asterisco rinvia alla voce corrispondente del glossario, in calce.
Che cosa si intende per numero primo
Un intero maggiore di 1 è primo se ha soltanto due divisori positivi: 1 e se stesso. Non si scrive come prodotto di due interi più piccoli.
2, 3, 5, 7, 11, 13, 17, 19, 23: è l'inizio della lista, quello che in prima media si impara a memoria, spesso fino a 30 o fino a 100. 4 non c'entra (2 × 2), né 9 (3 × 3), né 15 (3 × 5). Quelli sono composti*. Da 2 in su non esiste un terzo cassetto: o è primo, o si scompone.
Su questa pagina la risposta si legge nella scomposizione. Un solo fattore, alla potenza 1? Il numero è primo. Due fattori, oppure un esponente maggiore di 1, ed è composto. 9 = 3² non è primo: un unico primo a schermo non basta se l'esponente racconta già 3 × 3. Il valore di partenza, 360, esce 2³ × 3² × 5: composto, con dodici divisori.
Perché 1 resta fuori dalla lista
La domanda torna ogni anno, alle medie come al liceo. 1 è divisibile solo per 1: perché allora no?
Perché la definizione chiede due divisori distinti. 1 ne ha uno. Non è composto nemmeno: non si spezza in interi più piccoli. Resta un caso a sé. Il motivo vero è il teorema fondamentale dell'aritmetica*: ogni intero > 1 si scrive in un solo modo come prodotto di primi, a meno dell'ordine. Se 1 fosse primo, si potrebbero attaccare quanti 1 si vuole (1 × 1 × 5 = 5) e l'unicità crollerebbe. Quindi resta fuori. Non è un vezzo dei libri.
Il calcolatore rifiuta qualunque valore sotto 2. Il caso 1, semplicemente, non ha nulla da scomporre. A dire il vero, anche 0 e i negativi restano fuori: la primalità si discute sui naturali da 2 in su.
Il crivello di Eratostene, come si riempie una tavola
Per un n solo basta la divisione a tentativi fino a √n. Per avere tutti i primi fino a un limite N si cambia attrezzo: il crivello di Eratostene*, classico della prima media.
- Si scrivono gli interi da 2 a N.
- 2 è primo: si barrano tutti i suoi multipli (4, 6, 8…).
- Il primo non barrato, 3, è primo: si barrano 6, 9, 12…
- Si ripete con 5, 7 e così via, fino a √N. Quel che resta scoperto è primo.
Non è un test isolato, è una passata. Ogni composto viene toccato poche volte. Per riempire una tavola fino a 100 — quella che sta in fondo a tanti quaderni — non c'è niente di più semplice. Fino a qualche milione, lo stesso schema si programma in poche righe. Questa pagina non crivella l'intervallo: risponde a un n. Generare i cinquanta milioni di primi sotto il miliardo solo perché è comparso 360 sarebbe tempo perso.
Una sola scomposizione: il teorema fondamentale
Ogni intero maggiore di 1 si scrive, in un solo modo, come prodotto di primi. L'ordine non conta: 2 × 3 × 5 e 5 × 2 × 3 sono la stessa scrittura di 30. Gli esponenti sì, contano: 12 = 2² × 3, non 2 × 3 × 2 in un altro senso. È il teorema fondamentale, e da lì discende quasi tutta l'aritmetica scolastica.
I criteri di divisibilità diventano, a questo punto, un modo rapido per scovare i primi piccoli senza scomporre fino in fondo. Se un numero è divisibile per 2, 3 e 5, quei tre fattori ci sono. Il resto, se resta, si tratta a parte. 360 = 2³ × 3² × 5 lo mostra: tre primi, esponenti diversi, e nient'altro.
Senza unicità, confrontare due scomposizioni non direbbe nulla. Con l'unicità, l'MCD e il mcm si leggono sugli esponenti: il minimo per l'MCD, il massimo per il mcm. Due gesti, lo stesso materiale.
Primi gemelli, Mersenne, e i record
Alcuni primi arrivano a coppie, distanti 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31)… Sono i primi gemelli. Se ne conoscono di enormi. Non si sa ancora se ne esistano infiniti. È una delle domande aperte più corte della matematica.
I numeri di Mersenne* hanno la forma 2p − 1. Perché quell'espressione sia prima, p stesso deve esserlo — necessario, non sufficiente. 211 − 1 = 2.047 = 23 × 89, e 11 è primo. Perché interessarsene? Perché quasi ogni record di «primo più grande noto» è un Mersenne: la forma ammette un test dedicato (Lucas–Lehmer) assai più efficace della divisione a tentativi. GIMPS, una rete di macchine volontarie, dà la caccia a questi record dagli anni Novanta.
Comunque questa pagina non ci arriva. 219 − 1 = 524.287 sta ancora sotto il miliardo ed è primo; 231 − 1 = 2.147.483.647, primo anch'esso, esce dal tetto. Gemelli e Mersenne si possono toccare col calcolatore, entro il limite. Non sono un modo speciale dell'aritmetica: sono famiglie, nulla di più.
Numeri perfetti e la somma dei divisori
Un numero è perfetto* quando la somma dei suoi divisori propri — tutti tranne sé stesso — lo ricostruisce.
6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. Poi 496, poi 8.128. La lista si dirada in fretta. Ogni perfetto pari si scrive 2p−1(2p − 1) appena 2p − 1 è un primo di Mersenne (teorema di Euclide–Eulero). Un perfetto dispari non lo ha visto nessuno. Non si è nemmeno dimostrato che non esistano. Restano aperte sia l'esistenza dei dispari sia l'infinità dei pari, il che non impedisce a 6 e 28 di girare in tutti i manuali delle medie.
La tabella di questa pagina somma tutti i divisori, n compreso. Un perfetto compare quindi con somma 2n. Per 28 la somma stampata è 56. Da qui si legge anche il numero dei divisori, senza elencarli: se n = p1a × p2b × …, i divisori sono (a+1)(b+1)… 360 ha (3+1)×(2+1)×(1+1) = 24 divisori. La pagina ne mostra l'elenco finché restano al più 300.
Frazioni, MCD e i fattori in comune
Semplificare una frazione vuol dire togliere ciò che numeratore e denominatore hanno in comune. Quei fattori comuni sono l'MCD — alle medie, il M.C.D. con i puntini.
Se a = 2³ × 3² × 5 e b = 2² × 3 × 7, l'MCD prende il min di ogni esponente: 2² × 3 = 12. Il mcm prende il max: 2³ × 3² × 5 × 7 = 2.520. 360/12 su 84/12 dà la frazione irriducibile 30/7. Euclide non serve se le due scomposizioni sono già lì — a patto che i numeri restino abbastanza piccoli da ottenerle. Spezzare un intero e confrontarne diversi è lo stesso materiale, due gesti.
Il calcolatore di MCD e mcm lavora al contrario, con l'algoritmo di Euclide, anche su un elenco. Il calcolatore di frazioni usa proprio quell'MCD per ridurre ogni risultato. Le tre pagine si rispondono.
Quando la divisione a tentativi non basta più
Fino a un miliardo la divisione a tentativi fino a √n è limpida: √1.000.000.000 sta intorno a 31.623 prove. La pagina risponde in un attimo.
A 50 cifre, √n ne ha 25. Nessuno aspetta 1025 divisioni. A quella scala non si prova più a scomporre: si lancia un test di primalità* (Miller–Rabin in pratica; altri se il numero ha una forma comoda) che può concludere «primo» senza mostrare un solo fattore. Fattorizzare è un altro mestiere, assai più duro — ed è la scommessa su cui poggia RSA. Un numero può quindi essere certificato primo anche se nessuno ne ha scritto i divisori, per il semplice fatto che l'elenco ha due righe: 1 e lui stesso.
In fondo il tetto dello strumento è questo: vedere una scomposizione, non attaccare un modulo crittografico. Al liceo scientifico RSA compare come cultura, non come esercizio da svolgere a mano.
I primi di questa pagina non c'entrano con quelli di una chiave. Il tetto è un miliardo: dieci cifre, un esercizio da scuola. Un modulo RSA tipico ha 2.048 bit, oltre 600 cifre. Scomporre 360 non insegna a spezzare una chiave.
Il 2 è l'unico primo pari
Ogni pari diverso da 2 è divisibile per 2, quindi composto. Il 2 resta solo.
Sembra una battuta da cortile, e accorcia molti ragionamenti. Oltre il 2 si cercano solo dispari. Il crivello comincia barrando una casella su due: la parità è il primo filtro, il più grezzo. I gemelli, dal canto loro, sono quasi sempre due dispari a distanza 2. La coppia (2, 3) è consecutiva, non gemella.
Se un intero finisce per 0, 2, 4, 6 o 8 e non è 2, l'idea che sia primo si può mettere via. Tanto per i criteri di divisibilità, è il più a buon mercato: un'occhiata all'ultima cifra.
I numeri primi sono infiniti
Euclide lo mostra senza consegnare una formula per il successivo. Il ragionamento sta in poche righe e, al liceo, è spesso la prima dimostrazione «vera» che si incontra in aritmetica.
Si supponga che ce ne sia solo un numero finito: p1, p2, …, pk. Si formi N = p1 × p2 × … × pk + 1. Nessun pi divide N (resta sempre 1). Dunque o N è primo — e mancava dall'elenco — oppure ha un fattore primo nuovo. In entrambi i casi l'elenco era incompleto. Si può ricominciare all'infinito. Non si dice come trovare il prossimo. Si dice solo che ce n'è sempre un altro.
N = (prodotto dei primi supposti) + 1 → primo nuovo, o fattore nuovo
La densità cala. Tra 1 e 100 ce ne sono 25; tra 1 e 1.000, 168; tra 1 e 1.000.000, 78.498. Più rari non vuol dire ultimi.
La congettura di Goldbach
Ogni intero pari strettamente maggiore di 2 sarebbe somma di due primi. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 3+7 = 5+5, e così via.
È stata verificata al calcolatore fino a soglie enormi. Non è dimostrata. È una congettura, non un teorema: la distinzione conta, anche se l'enunciato sta in una riga e un controesempio non è mai uscito. Una versione più debole (ogni dispari ≥ 7 è somma di tre primi) è stata dimostrata. La forma forte, quella che si racconta al liceo, resta aperta. Insomma, è uno di quei problemi il cui enunciato è più corto di qualunque resoconto onesto del perché si è ancora fermi.
Questa pagina non verifica Goldbach. Scompone un intero. Per gioco, da un pari si può spezzare e cercare a mano due primi che lo ricompongano. Non è una prova. Né un risultato del calcolatore.
Perché il tetto è un miliardo
Perché la divisione a tentativi resta istantanea e l'elenco dei divisori sta ancora a schermo — salvo qualche numero molto composto, di cui si nasconde allora la lista (oltre 300 divisori).
Oltre, il calcolo su una macchina odierna non «si rompe» subito. L'interesse didattico sì. Nessuno verifica a mano un numero a dodici cifre, e i bisogni veri — chiavi, record — vivono a scale in cui questo metodo non c'entra più. Un miliardo è un tetto onesto: abbastanza per le medie, il liceo, un identificativo, un problema da olimpiade; troppo poco per far credere che si scomponga una chiave. √n si ferma intorno a 31.000, un ciclo PHP che la pagina finisce prima di disegnarsi.
Un intero più grosso di 1.000.000.000 esce da questo strumento. Non è più lo stesso problema.
Glossario
- Numero composto
- Un intero maggiore di 1 che non è primo: si scrive come prodotto di due interi più piccoli di lui. 4, 9, 15, 360 sono composti.
- Teorema fondamentale dell'aritmetica
- Ogni intero maggiore di 1 si scrive in un solo modo come prodotto di numeri primi, a meno dell'ordine dei fattori. È il motivo per cui 1 non è primo.
- Crivello di Eratostene
- Metodo per elencare tutti i primi fino a un limite N: si scrivono gli interi da 2 a N e si barrano i multipli di ciascun primo trovato, fino a √N.
- Numero di Mersenne
- Un intero della forma 2p − 1. Perché sia primo, p stesso deve esserlo (necessario, non sufficiente). Quasi tutti i record di «primo più grande noto» sono di questa famiglia.
- Numero perfetto
- Un intero uguale alla somma dei suoi divisori propri (tutti tranne sé stesso). 6 e 28 sono i primi due. Ogni perfetto pari è legato a un primo di Mersenne.
- Test di primalità
- Una procedura che decide se un intero è primo senza necessariamente scomporlo. Miller–Rabin è quello usato in pratica sui numeri grandi; non restituisce i fattori.