Nuestro principal objetivo es determinar de alguna forma sencilla los divisores de un número. Sabemos que todo número $n\in\mathbb{Z}$ tiene por lo menos cuatro divisores enteros: $\pm 1$ y $\pm n$. Si éstos fueran los únicos (como por ejemplo para $n=2$), el número sería lo más sencillo posible en lo que se refiere a divisibilidad A estos números se les llama números primos, nombre que proviene de número primero y es que los números primos son los ladrillos fundamentales de los números enteros. Esto quedará claro una vez que veamos el Teorema fundamental de la aritmética.
Es importante darse cuenta que el número $1$ no es un número primo porque tiene sólo un divisor positivo: el propio $1$. En general, se puede hablar también de primos negativos: $-p$ es primo si, y sólo si, $p$ es primo. En la siguiente tabla podemos los cien primeros números primos positivos: \[\begin{array}{rrrrrrrrrr} 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 \\ 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 \\ 73 & 79 & 83 & 89 & 97 & 101 & 103 & 107 & 109 & 113 \\ 127 & 131 & 137 & 139 & 149 & 151 & 157 & 163 & 167 & 173 \\ 179 & 181 & 191 & 193 & 197 & 199 & 211 & 223 & 227 & 229 \\ 233 & 239 & 241 & 251 & 257 & 263 & 269 & 271 & 277 & 281 \\ 283 & 293 & 307 & 311 & 313 & 317 & 331 & 337 & 347 & 349 \\ 353 & 359 & 367 & 373 & 379 & 383 & 389 & 397 & 401 & 409 \\ 419 & 421 & 431 & 433 & 439 & 443 & 449 & 457 & 461 & 463 \\ 467 & 479 & 487 & 491 & 499 & 503 & 509 & 521 & 523 & 541 \end{array}\]
Si observas la tabla, pronto descubrirás que no hay ninguna regla sencilla que te permita pasar de un primo al siguiente y es que realmente no se conoce ninguna forma sencilla de generar los números primos. ¿Qué hay que hacer entonces para ver si un número es primo? Pues no queda otra opción que comenzar a dividirlo por otros números más pequeños a ver si la división es o no exacta. Tendríamos que probar con todos los números menores que el número, pero esto se puede acortar un poco y lo vamos a ver con un ejemplo. Imaginemos que tenemos el número $7919$ y queremos ver si es primo: lo dividimos porn $2$, por $3$, por $4$, y así sucesivamente (en cuanto veamos el Teorema fundamental de la aritmética veremos que sólo hace falta probar con los primos). Vemos que no nos sale exacta la división por ningún número, pero cuando llegamos a dividir por $88$ obtenemos cociente $89$ y resto $87$ y, cuando dividimos por $89$, obtenemos cociente $88$ y resto $87$. No nos ha salido ninguna división exacta pero el cociente empieza a ser menor que el divisor: evidentemente ya no nos saldrá ninguna porque si $7919=a\cdot b$ y $a>89$, entonces $b\lt 89$ y nos tendría que haber salido el factor $b$ antes. Por tanto, $7919$ es primo (es el primo número $1000$). Todo esto se resume en la siguiente regla.
Los números primos son los más sencillos en todo lo que a productos y divisibilidades se refiera. Vamos a probar que todo número entero se puede expresar de forma única como producto de primos, pero antes necesitaremos una propiedad importante.
Para probar la existencia procedamos por inducción. Es obvio que $2$ es un número primo luego cumple el enunciado. Supuesto que todo número menor que $n>2$ pueda expresarse de tal manera, consideremos $n$. Si $n$ es primo habremos acabado pero si no es primo es porque existen $a,b\in\mathbb{N}$ tales que $n=ab$ y $1\lt a,b\lt n$, en cuyo caso aplicamos la hipótesis de inducción a $a$ y a $b$ obteniendo números primos $p_1,\ldots,p_r$ y $q_1,\ldots,q_s$ tales que $a=p_1\cdots p_r$ y $b=q_q\cdots q_s$, de donde $n=p_1\cdots p_rq_1\cdots q_s$ y hemos expresado $n$ como producto de primos.
Para la unicidad, supongamos que tenemos expresado $n=p_1\cdots p_r=q_1\cdots q_s$ de dos formas como producto de primos. Entonces $p_1|n=q_1\cdots q_s$ de donde por el lema previo existe $i_1\in\{1,\ldots,s\}$ tal que $p_1|q_{i_1}$ luego como $p_1\neq 1$ tenemos que $p_1=q_{i_1}$ y podemos cancelarlo en la expresión de $n$ obteniendo $p_2\cdots p_r=q_1\cdots q_{i_1-1}q_{i_1+1}q_s$. Ahora repetimos el proceso con $p_2$, $p_3$, etc. Es claro así que debe ocurrir que $r=s$ y existe una permutación $i_1,\ldots,i_r$ de los números $1,\ldots,r$ tal que $p_k=q_{i_k}$ para cualquier $k$.
Si agrupamos todos los factores primos iguales de un número $n>1$, podemos escribirlo de forma única como \[n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\] donde los $p_i$ son primos distintos y los exponentes $e_i$ números naturales. A una expresión de esta forma la llamaremos descomposición de $n$ en factores primos y sabemos que siempre existe.
Vamos a demostrar ahora uno de los resultados más conocidos de Euclides que nos asegura que hay tantos primos como queramos.
Vamos a aplicar la misma técnica a otro caso parecido.
Hasta ahora hemos hablado de números primos y de cómo estos ayudan a comprender la estructura de todos los números. No obstante, a veces es útil hablar de números que son primos con otros números, lo que significa que los números en cuestión no tienen divisores comunes distintos de $\pm 1$ o bien que su máximo común divisor es $1$.
Como la misma definición dice, si $a,b\in\mathbb{Z}$ son primos entre sí, entonces no tienen factores primos comunes luego si descomponemos $a=p_1^{e_1}\cdots p_r^{e_r}$ y $b=q_1^{f_1}\cdots q_s^{f_s}$, donde $p_1,\ldots,p_s,q_1,\ldots,q_s$ son números primos y los exponentes son naturales, entonces ninguno de los factores primos $p_i$ puede ser igual a uno de los factores $q_j$, es decir, las descomposiciones son disjuntas.
Si ahora $a$ y $b$ no son primos entre sí, entonces $d=\mathrm{mcd}(a,b)>1$, pero siempre podemos considerar $a'=\frac{a}{d}$ y $b'=\frac{b}{d}$. Estos nuevos números $a'$ y $b'$ sí son primos entre sí como puedes comprobar pues hemos eliminado todos los factores comunes. Esto no es nada nuevo pues es lo que se hace normalmente al simplificar una fracción: si tenemos el número racional $\frac{a}{b}$ (siempre que $b\neq 0$), entonces podemos multiplicar el numerador y el denominador simultáneamente por el número (distinto de cero) que queramos luego, si los multiplicamos por $\frac{1}{d}$, llegamos a la nueva fracción $\frac{a'}{b'}$, donde $\mathrm{mcd}(a',b')=1$. Esta fracción no puede simplificarse más y la llamamos fracción irreducible. Observa que las siguientes afirmaciones son equivalentes:
Vamos a usar la descomposición de un número en factores primos para calcular el número de divisores de un número y la suma de éstos.
Supongamos que $n$ es un número natural y lo descomponemos en factores primos como $n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$, donde sabemos que $p_1,\ldots,p_r$ son números primos distintos y $e_1,\ldots,e_r$ son números naturales. Entonces, si $d$ es un divisor de $n$, se cumplirá que $n=d\cdot d'$ para cierto $d'\in\mathbb{N}$ (que también es divisor de $n$). Factorizando $d$ y $d'$ y multiplicando sus factorizaciones, llegamos a que $d$ y $d'$ tienen que tener los mismos factores primos que $n$, es decir, $d=p_1^{f_1}p_2^{f_2}\cdots p_r^{f_r}$ y $d'=p_1^{f'_1}p_2^{f'_2}\cdots p_r^{f'_r}$, donde cada $f_k$ puede ser cero y $f_k+f_k'=e_k$. Por tanto, los divisores de $n$ son los números de la forma \[p_1^{f_1}p_2^{f_2}\cdots p_r^{f_r}, \text{ donde }0\leq f_k\leq e_k.\] De aquí podemos sacar algunas conclusiones.
Veamos cómo aplicar esto al caso de $n=2520=2^3\cdot 3^2\cdot 5\cdot 7$. Como los exponentes son $3$, $2$, $1$ y $1$, el número de divisores de $2520$ es $(3+1)\cdot(2+1)\cdot(1+1)\cdot(1+1)=48$ y la suma de éstos es $(1+2+4+8)(1+3+9)(1+5)(1+7)=15\cdot 13\cdot6\cdot 8=9360$.
También tenemos la siguiente regla conocida para hallar el máximo común divisor y el mínimo común múltiplo a partir de la factorización.
La demostración la dejamos al lector pero antes observemos que el máximo común divisor coincide con la regla comunes elevados al menor exponente y el mínimo común múltiplo con comunes y no comunes elevados al mayor exponente.
Para terminar, simplemente comentar que el método de la factorización es un buen método teórico en general pero en la práctica es muy deficiente porque es muy difícil factorizar un número medianamente grande (es el mismo problema que tenemos para saber si un número es primo o no). Para convencernos, dejamos el siguiente ejercicio: calcular el máximo común divisor de $62773913$ y $77075627$ primero intentando factorizar y después mediante el algoritmo de Euclides... ¡Suerte!.