Todos hemos descompuesto un número en factores primos, por ejemplo: 3420 = 22 x 32 x 5 x 19, pero la pregunta es: ¿se pueden descomponer todos los números en factores primos? y otra más difícil: ¿la descomposición es única?
Estas preguntas las responde el teorema fundamental de la aritmética:
Cualquier número entero, distinto de cero, puede ser representado en forma del producto de números primos, siendo la descomposición en factores única.
La posibilidad de descomposición se demuestra por inducción:
a) Para n = 1, 1 = 1 (el 1 se considera primo por definición).
b) Supongamos que para todos los números positivos m, menores que n, es cierta la posibilidad de descomposición en factores primos y demostrémoslo para el número n.
Si n es un número primo n = n.
Si n es compuesto, n = n1·n2, siendo n1 < n
y n2 < n.
Como en b) hemos aceptado que todos los números menores que n se pueden descomponer en factores primos
n1 = p1·p2···pr
n2 = q1·q2···qs
Entonces ya hemos obtenido la descomposición de n en factores primos:
n = p1·p2···pr· q1·q2···qs