Scomposizione dei numeri interi in fattori primi
Ogni numero non primo N deve avere almeno un numero primo come divisore.
Infatti, se N non è primo, allora è scomponibile in fattori, mediante numeri più piccoli. Poniamo allora che, in un primo tentativo di scomposizione, si siano trovati fattori non primi; questi saranno ulteriormente scomponibili. Procedendo in tal modo, si perviene sempre alla scomposizione di N in fattori primi.
Ad esempio, si prenda N=32.
Una prma scomposizione potrebbe essere data da 16 x 2, per cui
32 = 16 x 2
Si nota che uno dei due fattori non è primo, per cui si cerca di scomporlo, trovando 16 = 8 x 2; di nuovo compare un fattore non primo
32 = 8 x 2 x 2
Si procede allo stesso modo, finchè si arriva alla scomposizione massima, che è interamente composta di numeri primi:
32 = 2 x 2 x 2 x 2 x 2 x = 25