DIVISORI, FATTORI PRIMI E FATTORIZZAZIONE DI UN NUMERO INTERO

Il Teorema Fondamentale dell’Aritmetica afferma che: “Ogni numero intero maggiore di 1 o è un numero primo o si può esprimere come prodotto di numeri primi. Tale rappresentazione è unica, se si prescinde dall’ordine in cui compaiono i fattori”.
Ad esempio:

1105 = 5 x 13 x 17

E non vi è nessun’altra rappresentazione di questo numero come prodotto di numeri primi.
A questo punto occorre ricordare che un numero primo è un numero intero maggiore di uno divisibile solo per se stesso e per l’unità.
Non bisogna confondere i fattori primi di un numero con i suoi divisori. Ad esempio, nell’esempio precedente, i fattori primi di 1105 sono 5, 13 e 17, mentre i suoi divisori sono 1, 5, 13, 17, 65, 85, 221 e 1105 e, tra questi, 1, 65, 85, 221 e 1105 non sono numeri primi.
Nella scomposizione in fattori primi di un numero, uno o più fattori primi possono anche apparire più volte, ad esempio:

360 = 2³ x 3² x 5

Dove il fattore primo 2 appare 3 volte, il fattore primo 3 appare 2 volte ed il fattore primo 5 appare una volta.
Esistono due relazioni tra i fattori primi ed i divisori di un numero.
Nelle formule seguenti useremo il simbolo ^ per indicare “elevato a”.
Se la scomposizione in fattori primi di N è:

N = p^a  x  q^b  x …… x  r^c

Allora il numero dei divisori di N sarà dato da:

(a + 1) x (b + 1) x …… x (c + 1)

Verifichiamo quanto detto sul numero 360, i cui divisori sono 24 (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 e 360):

360 = 2³x3²x5

(3 + 1) x (2 + 1) x (1 + 1) = 4 x 3 x 2 = 24

La somma dei divisori sarà invece data da:

Verifichiamo sempre sul numero 360:
La somma dei divisori di 360 è:

1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360 = 1170

Applichiamo ora la formula, ricordando sempre che 360 = 2³x3²x5:

[(2^4 -1) / 1] x [(3^3 – 1) / 2] x [(5^2 – 1) / 4 =

= 15 x 13 x 6 = 1170

Si definiscono divisori propri di un numero tutti i suoi divisori tranne il numero stesso.
In particolare, si definisce “numero abbondante” un numero che sia inferiore alla somma dei suoi divisori propri e “numero deficiente” un numero che sia superiore alla somma dei suoi divisori propri.
Il nostro esempio 360 è un “numero abbondante” in quanto la somma dei suoi divisori propri è 810.
Quei rarissimi numeri che sono eguali alla somma dei loro divisori propri, vengono definiti “numeri perfetti” e sono stati trattati in questo articolo:
https://giuseppemerlino.wordpress.com/2010/10/25/numeri-amici-perfetti-e-n-di-mersenne/

Uno dei problemi più ardui della Teoria dei Numeri è la scomposizione di un numero intero nei suoi fattori primi.
“Ma è un argomento che si insegna alla scuola media !”, direte voi. Verissimo, ma quei metodi, dai quali peraltro partiremo, sono utilizzabili per numeri di grandezza “ragionevole”, ma già con un numero considerato “piccolo” in Teoria dei Numeri come 71.445.617 (= 503 x 142.039) ci troveremmo in grandi difficoltà a trovarne i fattori primi.
Il problema è talmente arduo che numeri primi di oltre 60 cifre decimali vengono usati in crittografia, per esempio per nascondere i dati della vostra carta di credito quando comprate qualcosa su internet o quando accedete dal web al vostro conto bancario.
Il punto di partenza per fattorizzare un numero intero sono i criteri di divisibilità. Essi sono veramente tanti, ma quelli veramente utili nella fase iniziale dell’analisi dell’intero da fattorizzare sono, a mio giudizio, solamente tre:
1) tutti i numeri pari (cioè con ultima cifra 0, 2, 4, 6, 8) sono divisibili per 2
2) tutti i numeri che hanno come somma delle cifre un numero divisibile per 3, sono divisibili per 3.
3) tutti i numeri con ultima cifra 5 o 0, sono divisibili per 5
Procediamo allora, col metodo che abbiamo imparato alla scuola media, alla fattorizzazione nel nostro solito esempio (360).
Scriviamo il numero tracciando a destra dello stesso una riga verticale.
Cerchiamo il più piccolo numero primo per cui è divisibile il numero di partenza; nel nostro caso 2 e scriviamo perciò 2 a destra di 360.
Scriviamo il quoziente 180 sotto a 360 e procediamo sempre così, fino a giungere ad un numero primo, quando la scomposizione sarà terminata.

Questo procedimento viene estremamente velocizzato al computer facendo alcune semplici considerazioni:
Innanzitutto, se il numero da esaminare è pari, lo si divide per 2 e, se il risultato fosse ancora pari lo si divide di nuovo per 2, fino a che si ottenga un numero dispari.
Ora si comincia l’analisi sul numero dispari, provando per ciascun numero primo, a partire da 3, 5, 7, 11 ….., se il numero da esaminare sia divisibile per esso.
La velocità del procedimento è estremamente accelerata da una semplice considerazione:
Se il nostro numero da esaminare è N, non è necessario provare la sua divisibilità per tutti i numeri primi fino ad N, ma ci si può tranquillamente limitare solo ai numeri primi inferiori alla radice quadrata di N, infatti, se N non è un numero primo, sicuramente un suo fattore primo sarà inferiore a questo limite.
Se, per esempio, vogliamo fattorizzare il numero 4181, dobbiamo provare tutti i numeri primi fino al limite 65 (√4181 = 64,66065264 …..) e cioè: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61. Dobbiamo dunque eseguire solo 17 divisioni, cosa che il computer esegue pressocchè istantaneamente. Ma di solito il fattore primo viene trovato ancora prima. Nel nostro esempio è 37, ottenuto dopo 11 divisioni:

4181 = 37 x 113

Per fattorizzare grandi numeri è dunque assolutamente necessario disporre di una tabella di numeri primi, il più estesa possibile. Qui ne diamo una con i numeri primi da 1 a 1013:

Un altro metodo di fattorizzazione di un numero intero N, che talvolta può essere più veloce da quello esposto, è stato ideato dal grande matematico Pierre de Fermat.
Questo metodo consiste nel cercare un quadrato esatto tale che, sommato ad N, dia un altro quadrato esatto:

N + A² = B²

Risulterà allora:

N = B² – A²

N = (B – A) x (B + A)

Ed il numero è fattorizzato !

Si procede sommando uno alla volta al numero N da fattorizzare i quadrati esatti 1, 4, 9, 16, 25, 36 etc … finchè questa somma non dia per risultato un quadrato esatto.
Questo metodo è più veloce del precedente quando esistano due divisori di N vicini fra loro.
Facciamo un esempio:
Si voglia fattorizzare il numero 391.

391 + 1 = 392 (non è un quadrato esatto)
391 + 4 = 395 (non è un quadrato esatto)
391 + 9 = 400 = 20²

Troviamo i fattori:

391 + 3² = 20²

391 = 20² – 3²

391 = (20 – 3) x (20 + 3)

391 = 17 x 23

Come si può facilmente verificare.

Anche in questo caso può essere utile una tabella di quadrati perfetti. Qui ne diamo una da 1 a 30:

I metodi di fattorizzazione fin qui esposti diventano lenti quando si debbano fattorizzare numeri di centinaia di cifre. In tal caso si usano metodi sofisticati che richiedono conoscenze di matematiche superiori che esulano da questa breve trattazione. Citiamo ad esempio il metodo Pollard Rho (probabilistico), il metodo Pollard P-1 (probabilistico) ed il metodo delle curve ellittiche (ECM).