Álgebra abstracta
1.3 Números primos y el teorema fundamental de la aritmética
Es inmediato que todo entero \(x > 1 \) tiene al menos un divisor primo. En efecto, pues si \(x \) es primo, entonces éste es su propio divisor primo, y si es compuesto, entonces el menor de los divisores \(p > 1 \) de \(x \) ha de ser primo, pues de lo contrario existiría un \(d > 1 \) que divide a \(p \) y por tanto a \(x \), lo que no puede ser pues \(d < p \) y hemos supuesto que \(p \) es el menor de los divisores de \(x \) mayores a la unidad. Observemos que este divisor primo verifica \(p \leq \sqrt {x} \), pues \(x = py \) y \(1 < p \leq y \), así que \(p^2 \leq x \).
El hecho siguiente se conocía desde la antigüedad y aparece como la Proposición 20 del Libro IX de los Elementos de Euclides.
-
Demostración: Lo probaremos por reducción al absurdo. Supongamos que, contrario a lo que afirma el teorema, existe un número finito de primos, digamos \(p_1,\ldots ,p_n \). Entonces \(x = p_1p_2p_3\cdots p_n + 1 \) es un entero que no es divisible por ninguno de los primos listados, pues cada uno de ellos divide al primer término y para dividir a \(x \) tendrían que dividir también al 1. Se sigue entonces que \(x \) es, o bien un número primo mayor que todos los listados, o bien, como explicamos en el párrafo anterior al teorema, tiene un divisor primo que no puede ser ninguno de los que hemos listado.
A la fecha en la que se escriben estas letras, el más grande de los números primos que se conoce es
\[ 2^{82,589,933} - 1, \]
consistente de \(24,862,048 \) dígitos y encontrado en diciembre de 2018.
Como observábamos más arriba, todo número entero \(x\) mayor a la unidad tiene al menos un divisor primo. Se deduce entonces por inducción que \(x\) puede descomponerse como un producto de números primos. Esto incluye, por supuesto, el caso en que \(x\) es él mismo un número primo, pues ahí lo que tenemos es un producto de primos con \(x\) como su único factor. Más aún, podemos definir el producto vacío de enteros (un producto sin ningún factor) como la unidad, y así afirmar que
-
Demostración: Sea \(x\) un entero positivo, y razonemos por inducción sobre \(x\). Si \(x = 1\), el teorema es cierto, pues se trata del producto vacío de primos. Supongamos el teorema cierto para todos los enteros menores o iguales a \(x\). Si \(x + 1\) es primo, no hay nada más que decir. Si no lo es, entonces es un producto \(ab\) de enteros tales que \(a,b > 1\), o sea que \(a,b < x + 1\) y por lo tanto \(a,b\leq x\), luego la hipótesis de inducción nos dice que \(a\) y \(b\) son primos o producto de primos, por lo que \(x + 1 = ab\) es un producto de primos.
Como el lector pudo haberlo supuesto ya, la factorización de un entero positivo en producto de números primos es única salvo el orden de los factores. La razón detrás de esta propiedad es esencialmente la siguiente.
-
Demostración: Supongamos que \(p\mid xy\) y que \(p\nmid x\). Entonces \(\mcd {p,x} = 1\) pues \(p\) es primo, así que \(p\mid y\) por el corolario 1.22.
Observemos que el recíproco del lema de Euclides también es cierto: si un entero \(p\) satisface la propiedad enunciada en el lema para cualesquiera enteros \(x\) y \(y\), entonces \(p\) ha de ser un número primo. En efecto, pues si en tales condiciones tuviésemos \(p = xy\) con \(x > 1\), entonces \(p\mid x\) pero también \(x\mid p\), o sea que \(x = p\) y \(y = 1\), y por lo tanto \(p\) es primo.
-
Demostración: Por la proposición 1.26, \(x\) puede escribirse como un producto \(p_1\cdots p_n\) de \(n \geq 0\) números primos. Supongamos que \(q_1\cdots q_m\) es otra factorización prima de \(x\) de \(m\) factores. Sin pérdida de generalidad, podemos asumir que \(n \geq m\). Demostraremos por inducción sobre \(n\) que \(m = n\) y que ambas factorizaciones consisten de los mismos factores. Para \(n=0\), \(x = 1\) y la afirmación es trivialmente cierta. Supongamos ahora el teorema cierto para todo entero que sea producto de \(n\geq 1\) primos. Si \(p_1\cdots p_{n+1} = q_1\cdots q_m\) son factorizaciones primas de \(x\), entonces el lema Euclides nos dice que \(p_{n+1}\) divide a alguno de los primos \(q_1,\ldots ,q_m\), lo que sólo puede ocurrir si \(p_{n+1}\) es uno de estos primos, digamos \(p_{n+1} = q_i\). Dividiendo ambas factorizaciones de \(x\) entre este número, tenemos que
\[ p_1\cdots p_n = q_1\cdots q_{i-1}q_{i+1}\cdots q_{m-1}, \]
y por hipótesis de inducción, ambos miembros consisten exactamente de los mismos factores. Por lo tanto, \(p_1\cdots p_{n+1}\) y \(q_1\cdots q_m\) son factorizaciones de \(x\) que difieren, cuando mucho, en el orden de los factores.
Se sigue entonces que todo entero \(x\) es de forma única un producto
\[ p_1^{k_1}\cdots p_n^{k_n},\quad i = 1,\ldots ,n, \]
de potencias de números primos distintos. A esta forma de representar a \(x\) la llamamos la factorización prima de \(x\). Si admitimos factores \(p^{k_i} = 1\) de exponentes nulos, la factorización deja de ser única, pues obviamente factores así pueden insertarse arbitrariamente en la factorización. No obstante, la inclusión de estos factores permite que en las factorizaciones primas de dos o más enteros intervengan los mismos números primos.
-
Demostración: Es claro que todo producto de esta forma es un divisor de \(x\). Recíprocamente, si \(d\) es un divisor de \(x\), entonces \(x = dq\) para cierto \(q\in \Z \). Considerando la factorización prima de cada entero en esa igualdad, el lema de Euclides nos dice que que los únicos primos que pueden aparecer en la factorización prima de \(d\) son \(p_1,\ldots ,p_n\), y esto mismo aplica para \(q\). Puesto que el exponente de \(p_i\) en la factorización prima de \(x\) es la suma de los exponentes (posiblemente nulos) que \(p_i\) tiene en las factorizaciones primas de \(d\) y \(q\), concluimos que \(d = p_1^{l_1}\cdots p_n^{l_n}\) con \(l_i \leq k_i\) para todo \(i=1,\ldots ,n\).
Insertando primos con exponentes nulos en caso de ser necesario, podemos hacer que en las factorizaciones primas de dos enteros aparezcan los mismos números primos. Esto nos permite enunciar una caracterización útil del máximo común divisor de enteros.
-
Demostración: Sea \(d = p_1^{\min (k_1,l_1)}\cdots p_n^{\min (k_n,l_n)}\). Claramente \(d\) es un divisor común de \(x\) y \(y\). Si \(d'\) es otro divisor común de \(x\) y \(y\), entonces, por la proposición anterior, \(d'\) es de la forma \(p_1^{t_1}\cdots p_n^{t_n}\) con \(t_i\leq k_i,l_i\), por lo que \(d'\) divide a \(d\), lo que nos dice que \(d\) es el máximo común divisor de \(x\) y \(y\).
La demostración de la proposición anterior se deja como ejercicio al lector.
De las proposiciones 1.30 y 1.32 se de duce la siguiente relación entre el máximo común divisor y el mínimo común múltiplo.
En particular, tenemos que \(\mcd {x,y} = 1\) si y sólo si \(\mcm {x,y} = xy\). De esto se deducen hechos como el siguiente:
-
Demostración: La suficiencia es evidente. Para el recíproco se sigue de que \(xy = \mcm {x,y}\), y como \(n\) es un múltiplo común de \(x\) y \(y\), éste ha de ser divisible entre \(xy\) por el teorema 1.33.