Archivo de la etiqueta: teorema fundamental de la aritmética

Álgebra Superior II: Teorema fundamental de la aritmética e infinidad de números primos

Por Ana Ofelia Negrete Fernández

Introducción

En la entrada anterior comenzamos a hablar de los números primos. Lo que ahora veremos es que, en un sentido muy preciso, los números primos son los bloques con los cuales se construyen todos los demás enteros. El enunciado preciso estará dado por el teorema fundamental de la aritmética.

A grandes rasgos, el teorema fundamental de la aritmética afirma que todo entero se puede escribir como producto de primos, quizás algunos repetidos. Nos referimos a situaciones del tipo
\begin{align*}
8 &= 2 \cdot 2 \cdot 2 = 2^3,\\
13 &= 13^1,\\
152 &= 2^3\cdot 19, \enspace \text{etc.}
\end{align*}

Otro resultado que demostraremos en esta entrada es que hay una infinidad de primos. Euclides fue una de las primeras personas de quienes nos queda registro que lo notó. Veremos una demostración similar a la que él dió.

El teorema fundamental de la aritmética

El teorema fundamental de la artimética dice que cualquier número entero es producto de números primos. Pero, más aún, nos dice que este producto es único, bajo ciertas condiciones que le ponemos a la representación. Para simplificar la presentación, estudiaremos primero lo que dice el enunciado para enteros positivos.

Teorema. Sea $n$ un entero positivo. Entonces, existe un único entero $k$ y únicos números primos $p_1\leq p_2 \leq p_3 \leq \ldots \leq p_k$ tales que $$n=p_1\cdot p_2\cdot \ldots \cdot p_k.$$

Por ejemplo, consideremos el número $1060$. Notemos que en efecto se puede escribir como producto de primos de la siguiente manera: $1060=2\cdot 2 \cdot 5 \cdot 53$. El teorema fundamental de la aritmética nos dice que esta es la única manera en la que podemos ponerlo como producto de primos. Si lo piensas un poco, no es totalmente obvio. ¿Qué impide que, por ejemplo, no pase que $1060$ tenga otra posible representación en donde el $5$ aparezca más veces, o el $2$ menos veces? Es lo que debemos estudiar.

Demostración de la existencia

Vamos a partir la demostración del teorema fundamental de la aritmética en dos partes. Primero veremos la existencia, y después la unicidad. Así, nos enfocaremos primero en ver que cualquier entero positivo tiene una factorización en números primos.

La demostración será por inducción fuerte. Si $n=1$, la factorización es la factorización vacía, en donde $k=0$, y como no estamos multiplicando nada obtenemos $1$. Si $n=2$, entonces la factorización es precisamente $2=2$, pues $2$ es un número primo. Supongamos que el resultado es cierto hasta antes de cierto número fijo $n$ y veamos qué pasa con $n$. Si $n$ es un número primo, entonces $n=n$ ya es una factorización como las que buscamos. Si $n$ no es un número primo, entonces lo podemos factorizar como $n=ab$, en donde $a$ y $b$ son enteros positivos distintos de $1$. Por ello, cada uno de $a$ y $b$ son menores que $n$ y por hipótesis inductiva tienen una factorización en primos, digamos
\begin{align*}
a&=q_1\cdot q_2 \cdot \ldots\cdot q_l\\
b&=r_1\cdot r_2 \cdot \ldots \cdot r_m.
\end{align*}

Así, renombrando $q_1,\ldots,q_l,r_1,\ldots,r_m$ como $p_1\leq \ldots \leq p_k$ (donde $k=l+m$) para que queden en orden no decreciente obtenemos la factorización $$n=p_1\cdot p_2\cdot \ldots \cdot p_k $$ buscada. Esto termina la prueba de la primera parte.

Demostración de la unicidad

Veamos ahora que las factorizaciones en primos son únicas. Una vez más, procedemos por inducción fuerte. El resultado claramente es cierto para $n=1$ y $n=2$. Supongamos que el resultado es cierto hasta antes de cierto entero $n$ dado y supongamos que tenemos dos factorizaciones para $n$:

\begin{align*}
n&=p_1\cdot p_2 \cdot \ldots\cdot p_k\\
n&=q_1\cdot q_2 \cdot \ldots \cdot q_l.
\end{align*}

Notemos que $p_k$ es un divisor de $n$, así que debe dividir a $q_1\cdot\ldots\cdot q_l$. Por una propiedad de divisibilidad que vimos en la entrada pasada, debe suceder que o bien $p_k$ divide a $q_l$, o bien que divide a $q_1\cdot \ldots \cdot q_{l-1}$. Si pasa lo segundo, debe dividir o bien a $q_{l-1}$, o bien a $q_1\cdot \ldots \cdot q_{l-2}$. Y así sucesivamente, de modo que $p_k$ debe dividir a alguno de los $q_i$. Pero como $p_k$ y $q_i$ son primos, debe suceder entonces que $p_k=q_i$. Tras cancelar este término en ambas expresiones de $n$, llegamos a que:

$$p_1\cdot p_2 \cdot \ldots\cdot p_{k-1}=q_1\cdot \ldots \cdot q_{i-1} \cdot q_i \cdot \ldots \cdot q_l,$$

pero esto es una igualdad de factorizaciones en primos para un número menor estricto a $n$. Por hipótesis inductiva, ambas factorizaciones deben de ser la misma. Así, ambas factorizaciones de $n$ son la misma, pues se obtienen a partir de estas multiplicando por el número $p_k=q_i$.

$\square$

Otra forma de escribir el teorema fundamental de la aritmética

Hay otra manera de escribir el teorema fundamental de la aritmética, en donde los primos iguales se agrupan en un mismo término, y se coloca la potencia correspondiente.

Teorema. Sea $n$ un entero positivo. Existe un único entero no negativo $k$, únicos primos $p_1\leq \ldots \leq p_k$ y únicos exponentes $\alpha_1,\ldots,\alpha_k$ tales que:

$$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k}.$$

En realidad esta segunda versión del teorema se deduce de manera inmediata de la anterior.

Ejemplo. Consideremos el número $36$. El $2$ lo divide, así que $36=18\cdot 2$. Luego, el $3$ divide al $18$, de manera que $36=3\cdot 6\cdot 2$. Finalmente, notamos que $6=2\cdot 3$, de donde $36=3\cdot 2 \cdot 3 \cdot 2$. Para obtener la «forma estándar» de la factorización, agrupamos los primos iguales, les ponenmos el orden correspondiente y escribimos en orden creciente de primos. Así, la factorización de $36$ quedaría $36=2^2\cdot 3^2$.

$\square$

El conjunto de primos es infinito

En esta sección queremos demostrar otro resultado importante sobre el conjunto de los números primos.

Teorema. El conjunto de números primos es infinito.

Para dar la demostración, usaremos el método de demostración por contradicción, es decir, partiremos de que el conjunto de primos no es finito y, eventualmente se disparatará el asunto.

Este en efecto parece ser el método más conveniente. Sería difícil usar inducción dado que, si bien el conjunto de primos puede indexarse por $p_1, p_2, p_3, \ldots$, no es fácil determinar cuál es el primo que sigue en la lista. O bien, dado un entero $n$, no es fácil determinar si $n+1$ será o no un número primo. Resultaria igualmente difícil intentar la demostración por algún otro método directo.

La idea que usaremos es la siguiente. Si hay finitos primos, digamos $k$, significa que se puede crear una lista finita con ellos: $p_1, p_2, \ldots , p_k$. Veremos que siempre debe existir un primo distinto de los de la lista, lo que llevará a una contradicción con la hipótesis de que sólo existían $k$ primos.

Veamos primero unos casos partiulares del argumento que usaremos. Supongamos que sólo existieran $2$ primos, el $2$ y el $3$. Consideremos el número $z = 2\cdot 3 + 1$. De acuerdo al teorema fundamental de la aritmética, este número o bien es primo, o bien debe tener un divisor primo $p$. No puede ser primo, pues dijimos que los únicos primos eran $2$ y $3$. No puede ser divisible entre $2$ pues deja residuo $1$ al hacer la división. Tampoco puede ser divisible entre $3$ pues también deja residuo $1$ al hacer la división. Así, debe haber otro primo que no sea $2$ y $3$ y que divida a este número. Esto contradice que sólo existieran $2$ primos.

Veamos otro ejemplo. Supongamos que hay únicamente 4 primos: $2,3,5,7$. Consideremos el número $2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211.$ Si dividimos este número entre $2$, nos da $211=105\cdot 2 +1$, así que $2\nmid 211$. Si lo dividimos entre $3$, nos da $211=70\cdot 3 + 1$, así que $3\nmid 211$. De manera similar, se puede ver que las divisiones entre $5$ y $7$ también dejan residuo $1$, así que $5 \nmid 211$ y $7\nmid 211$.

Por el teorema fundamental de la aritmética, debe haber algún primo que divida a $211$. Pero estamos suponiendo que los únicos primos que existen son $2,3,5,7$ y acabamos de ver que ninguno de estos funciona. ¡Esto es una contradicción! Lo mismo ocurrirá sin importar la cantidad de primos $p_1, p_2, \ldots , p_k$ inicial. El problema no es cuántos son exactamente, sino la suposición de que son una cantidad finita.

Demostración. Supongamos, para buscar una contradicción, que el conjunto de números primos es finito y que consiste de exactamente los $k$ números primos $p_1, p_2, \ldots , p_k$. Consideremos el número $$p_1\cdot p_2 \cdot \ldots \cdot p_k +1.$$

El anterior número no es divisible por ninguno de los primos $$p_1, p_2, \ldots , p_k,$$ pues precisamente al hacer la división el residuo que queda es igual a $1$.

Por el teorema fundamental de la aritmética, $$p_1\cdot p_2 \cdot \ldots \cdot p_k + 1$$ debe tener entonces un divisor primo $p$ diferente de $$p_1, p_2, \ldots , p_k. $$ Esto es una contradicción, pues supusimos que sólo existían los primos $p_1,\ldots,p_k$.

$\square$

Más adelante…

Con los dos teoremas de esta entrada hemos profundizando un poco más en por qué los números primos son interesantes e importantes. La exploración de los números primos en este curso no irá mucho más lejos, pues pronto comenzaremos a tratar otros temas de aritmética modular. Sin embargo, te dejamos algunos pocos párrafos más sobre los números primos.

Los números primos siguen siendo interesantes para los matemáticos hoy en día; primero por la irregularidad con que van apareciendo en la recta numérica y porque hay muchas cosas que aún no se sabe acerca de su raro comportamiento. Por ejemplo, se conjetura que hay infinitos «primos gemelos», es decir, se cree que siempre es posible encontrar dos primos $a$ y $b$ que estén distanciados en dos unidades; no importa qué tan alejados estén del cero. El $3$ y el $5$ son primos gemelos. También los son el $17$ y el $19$. Nadie sabe si esta conjetura es cierta o falsa.

Los números primos aparecen en patrones muy irregulares, pero sí es posible decir algunas cosas al respecto. Por ejemplo, después del $2$ todo número primo $p$, es de la forma $4n +1$ o de la forma $4n -1$ para alguna $n \in \mathbb{N}$. Un resultado lindo en teoría de números es que para aquéllos primos que pertenecen a la primera categoría, que son los de la forma $4n+1$, siempre existe su expresión como una suma de cuadrados: $p = 4n + 1 = m^2 + n^2$, $n, m \in \mathbb{Z}.$ Pero a los primos de la segunda categoría es imposible expresarlos como suma de cuadrados. Estos son dos de los muchos resultados que demostró Euler para números primos, y puedes ahondar en ello en un curso de teoría de números.

Los números primos también han encontrado aplicaciones en criptografía, pues es bien sabido que si se eligen dos primos $p_1$ y $p_2$ tales que al multiplicarlos se obtenga un número compuesto $z$ de más de 100 dígitos, y si luego se establece que $p_1$ y $p_2$ sean la «clave» de mi mensaje cifrado pero yo únicamente doy a conocer el número compuesto $z$ a otra persona, entonces a una computadora le resultaría imposible factorizar $z$ en un corto lapso de tiempo. ¡Le tomaría años! De ahí que la contraseña secreta sería indescifrable.

Ahora, lo que se conoce como el «teorema fundamental de la aritmética» también tiene varias extensiones interesantes en otras áreas de las matemáticas. De hecho, en algunas estructuras la unicidad deja de ser cierta. Si combinamos a los números enteros con los números complejos (que veremos después), tenemos algunos ejemplos como $$12 = (1 + \sqrt{-11})(1 – \sqrt{-11})$$ pero también $$12 = (2 + \sqrt{-8})(2 – \sqrt{-8}).$$

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Encuentra la factorización en primos de cada uno de los siguientes números 100, 170, 2022, 5000 y 713.
  2. Encuentra el menor entero positivo $k$ que haga que $775k$ sea un número cuadrado perfecto, es decir, de la forma $n^2$ para algún entero $n$.
  3. Halla el número de divisores de $2360$ y calcula la suma de todos ellos.
  4. ¿Cuál es el número entero de $1$ a $100$ que tiene la mayor cantidad posible de divisores?
  5. Demuestra que un entero tiene una cantidad impar de divisores si y sólo si es un número cuadrado.

Entradas relacionadas


Álgebra Superior II: Números primos y sus propiedades

Por Ana Ofelia Negrete Fernández

Introducción

En esta entrada hablaremos de los protagonistas de entre los números enteros: los números primos. Es difícil poder enunciar en palabras sencillas la importancia que tienen este tipo de números, así que haremos un recorrido que incluye lo siguiente. Comenzaremos dando la definición de qué es un número primo, y haremos algunas aclaraciones conceptuales. Luego, enunciaremos propiedades de divisibilidad que cumplen los números primos y que son muy únicas a ellos. Esto nos ayudará a entender un poco de las razones por las cuales son especiales.

Finalmente, dejaremos preparado el terreno para poder hablar de dos resultados fundamentales sobre los números primos en la próxima entrada: el teorema fundamental de la aritmética y la infinidad del conjunto de números primos. El primer resultado nos permitirá pensar a los números primos como los átomos de los números enteros, ya que a partir de multiplicarlos se obtendrá cualquier entero, sea éste primo o compuesto.

Definición de números primos

La definición con la que trabajaremos es la siguiente.

Definición. Un entero número entero $p$ es primo si y sólo si es positivo y tiene exactamente cuatro divisores: $1, \enspace -1, \enspace z \enspace \text{y } -z \text{.}$

De la definición hay algunos números que inmediatamente debemos descartar por no ser números primos. Por ejemplo, el $1$ no es un número primo pues tiene como divisores únicamente al $-1$ y al $1$, que son dos divisores, y no exactamente cuatro, como pide la definición. Del mismo modo, $-1$ tampoco es número primo pues tiene sólo dos divisores también y, para rematar, es negativo, lo cual no se vale.

Del mismo modo, concluimos que el $0$ no es número primo. Su problema es que tiene demasiados divisores. Cualquier número entero divide al $0$, así que tiene mucho más que cuatro divisores. Veamos nuestro primer ejemplo de un número que sí es primo.

Proposición. El entero $2$ es primo.

Demostración. Lo primero por notar es que $2$ es positivo. Supongamos que $x \in \mathbb{Z}$ divide a $2$. Por cómo se comparan en tamaños un número con un divisor, obtenemos que $|d|\leq 2$. Esto nos deja $5$ posibilidades para $d$: $-2,-1,0,1,2$. El $0$ nunca es divisor y se puede ver que cada uno de los otros cuatro números sí lo son. Así, el $2$ tiene exactamente cuatro divisores, que son $1$, $2$, $-1$ y $-2$. Concluimos entonces que $2$ es un número primo.

$\square$

Si bien el $-2$ también tiene exactamente esos mismos $4$ divisores, a $-2$ no le llamamos número primo porque es negativo. Recuerda que por definición sólo los números positivos pueden ser primos.

En la duda, si no sabemos si un número es primo, siempre podemos regresar a la definición.

Proposición. El entero $57$ no es primo.

Demostración. Notamos que $1$, $3$, $19$ y $57$ son todos ellos divisores de $57$, así como sus negativos. Por ello, el número $57$ tiene ocho divisores, y por lo tanto no es primo.

$\square$

Otras formas de pensar a los números primos

La definición de primos que dimos está en términos de la cantidad de divisores en total que se deben tener. Sin embargo, hay por lo menos otras dos formas de escribir esto mismo.

Proposición. Son equivalentes las siguientes tres afirmaciones para un número entero $p$:

  • El número $p$ es primo de acuerdo a nuestra definición de tener exactamente $4$ divisores.
  • El número $p$ es positivo y tiene exactamente $2$ divisores positivos.
  • El número $p$ es positivo y en cualquier forma de escribir $p=ab$ con $a$ y $b$ enteros positivos, sucede forzosamente que $a=1$ ó $b=1$.

Demostración. Los primeros dos puntos son equivalentes entre sí pues si $d$ es un divisor de $p$, entonces $-d$ también. Así, por cada divisor positivo hay uno negativo y viceversa. De hecho, los dos divisores positivos son, explícitamente, $1$ y $p$.

Si $p$ es primo con respecto a esta segunda definición, entonces el tercer inciso es claro, pues escribir $p=ab$ justo nos dice que $a|p$, de donde $a=1$ ó $a=p$, pues son sus únicos dos posibles divisores. Si $a=1$, tenemos lo que queremos. Y si $a=p$, entonces para que se de $p=ab$, debemos tener $b=1$, como queremos.

Finalmente, a partir del tercer inciso también se puede demostrar el segundo. Supongamos que $p$ cumple con el tercer inciso y supongamos que $d$ es divisor. ESto nos permite escribir $p=dr$ con $r$ algún entero. Por el tercer inciso, debemos tener $d=1$, o bien $r=1$, y entonces $d=p$, tal como nos pide el segundo inciso.

$\square$

Quizás no se ve tanto la ventaja entre distinguir entre las primeras dos versiones de la proposición anterior. De hecho, se parecen mucho. Sin embargo, sí vale la pena pensar en la tercera como algo diferente: nos dice que hay sólamente dos maneras de escribir a un primo como producto de números positivos. Esto nos ayuda, por ejemplo, a darnos cuenta rápidamente que un número no es primo aunque no tengamos todos sus divisores.

Ejemplo. El número $105$ no es primo pues se puede escribir como $5\cdot 21$. En esta expresión ninguno de los dos números es igual a $1$. Así, concluimos que $105$ no es primo.

$\square$

Propiedades de divisibilidad de los números primos

En el caso de los números primos, los máximos comunes divisores son asunto de todo o nada. Esto está escrito más formalmente en la siguiente definición.

Proposición. Sea $p$ un número primo y $a$ un entero. Si $p$ divide a $a$, tenemos $(a,p)=p$. Y si no, tenemos $(a,p)=1$.

Demostración. Sabemos que $(a,p)|p$ y que $(a,p)$ no es negativo. Así, $(a,p)$ debe ser uno de los dos divisores de $p$: $1$ ó $p$. Si $p$ divide a $a$, entonces $(a,p)=p$ pues $p$ es divisor común tanto de $p$ como de $a$. Pero si $p$ no divide a $a$, entonces a $(a,p)$ no le queda más que ser igual a $1$.

$\square$

La proposición anterior nos lleva a un lema de divisibilidad que nos resultará útil cuando enunciemos y probemos el teorema fundamental de la aritmética.

Proposición. Sea $p$ un número primo y $a,b$ números enteros. Si $p|ab$, entonces $p|a$ ó $p|b$.

Demostración. Si $p|a$, entonces ya terminamos. Si no, por la proposición anterior tenemos que $(p,a)=1$. Pero entonces por una propiedad anterior de divisibilidad con primos relativos obtenemos que $p|b$, como queríamos.

$\square$

Para la proposición anterior resultó crucial que $p$ fuera un número primo. Por ejemplo, tenemos que $9|180=15\cdot 12$, pero no es cierto ni que $9|15$, ni que $9|12$.

Más adelante…

En la siguiente entrada veremos dos teoremas importantes relacionados con los números primos: el teorema fundamental de la aritmética y el teorema de que existe una infinidad de primos.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Encuentra todos los números primos de $1$ a $20$.
  2. Sea $n$ un número entero que no sea un número primo, ni el negativo de un número primo. Demuestra $n$ que se puede expresar de la forma $ab$ con $a$ y $b$ enteros (positivos o negativos) de por lo menos ocho formas distintas.
  3. Sea $p>2$ un número tal que ninguno de los números $2,\ldots,\left\lfloor \sqrt{p}\right \rfloor$ lo divide. Muestra que $p$ es un número primo.
  4. Sea $n$ un número entero y $p$ un primo. Muestra que si $p|n^2$, entonces $p|n$. De hecho, muestra que en general, para un entero $k\geq 1$ se cumple que $p|n^k$ si y sólo si $p|n$.
  5. Sea $p$ un número primo. ¿Cuántos divisores tiene el número $p^{10}$? ¿Cuántos son positivos y cuántos negativos?

Entradas relacionadas