Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas.

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El $1$ no es primo pues su único divisor es él mismo. Pero $2$, $17$ y $31$ sí son primos. De aquí y el algoritmo de la división, si $p$ es primo y $a$ es un entero, entonces $p\mid a$ o $\MCD{p,a}=1$.

Proposición 1. Si $p$ es un número primo que divide al producto de enteros $ab$, entonces $p\mid a$ ó $p\mid b$.

Demostración. Si $p$ no divide a $a$, entonces $\MDC(p,a)=1$, así que existe una combinación lineal entera $pn+am=1$. Multiplicando esta combinación por $b$, tenemos que $pbn+abm=b$. Como $p$ divide a $pbn$ y a $ab$, entonces divide a $b$.

$\square$

Problema. Muestra que si $p$ es un primo que divide a $123456^{654321}$, entonces $p$ divide a $123456$.

Sugerencia pre-solución. Aquí $123456$ y $654321$ no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea $a$ un entero, $n$ un entero positivo y $p$ un primo. Vamos a mostrar por inducción en $n$ que si $p\mid a^n$, entonces $p\mid a$. Para $n=1$ la conclusión es inmediata. Supongamos el resultado cierto para $n$. Si $p\mid a^{n+1}$, por la Proposición 1 tenemos que $p\mid a$ (en cuyo caso terminamos), o que $p\mid a^n$ (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando $a=123456$ y $n=6543321$.

$\square$

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si $p$ es primo, $a$ un entero y $n$ un entero positivo tales que $p\mid a^n$, entonces $p^n\mid a^n$.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean $a$ un entero positivo. Entonces existe un único $n$, únicos primos $p_1<\ldots<p_n$ y exponentes $\alpha_1,\ldots,\alpha_n$ tales que $$a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.$$

La idea de la demostración es factorizar y factorizar. Si $n$ está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que $\sqrt[3]{7}$ es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos $\sqrt[3]{7}=\frac{a}{b}$ con $a$ y $b$ enteros. De aquí, $7b^3=a^3$. En la factorización en primos de $a^3$ y $b^3$ tenemos una cantidad múltiplo de $3$ de factores $7$. Así, en el lado derecho tenemos una cantidad mútiplo de $3$ de factores $7$ (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

$\square$

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos $n$ para los cuales $2^8+2^{11}+2^n$ es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo $m^2=2^8+2^{11}+2^n$. De aquí, \begin{align*}
2^n&=m^2-2^8(1+2^3)\\
&=m^2-(3\cdot 2^4)^2\\
& =(m+48)(m-48).
\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números $m+48$ y $m-48$ tienen que ser potencias de $2$, digamos $m+48=2^a$ y $m-48=2^b$ con $a>b$ y $a+b=n$. Además tenemos que $$2^b(2^{a-b}-1)=96=2^5\cdot 3.$$

Como $2^{a-b}-1$ es impar, de nuevo por la unicidad de la factorización en primos debemos tener que $2^{a-b}-1=3$, y por lo tanto que $2^b=2^5$. De aquí, $b=5$ y $a-b=2$, y así $a=7$. Por lo tanto, el único candidato es $n=5+7=12$.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que $n$ en efecto es solución. Hacemos esto último notando que $2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2$ que en efecto es un número cuadrado.

$\square$

Fórmulas que usan el teorema fundamental de la aritmética

Sean $a$ y $b$ números enteros positivos y $P={p_1,\ldots,p_n}$ el conjunto de números primos que dividen a alguno de $a$ o $b$. Por el teorema fundamental de la aritmética, existen exponentes $\alpha_1,\ldots,\alpha_n$ y $\beta_1,\ldots,\beta_n$, tal vez algunos de ellos cero, tales que \begin{align*}
a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si $a=21, b=28$, entonces $P={2,3,7}$, $a=2^0 3^1 7^1$ y $b=2^2 3^0 7^1$.

Proposición 3. Se tiene que $a$ divide a $b$ si y sólo si para todo primo $p_i$ se tiene que $\alpha_i\leq \beta_i$.

Problema. ¿Cuántos múltiplos de $108$ hay que sean divisores de $648$?

Sugerencia pre-solución. Factoriza en primos a $108$ y a $648$ y usa la Proposición 3.

Solución. Tenemos que $108=2^23^3$ y que $648=2^3\cdot 3^4$. Por la Proposición 3, un número que funcione debe ser de la forma $2^a3^b$ con $2\leq a \leq 3$ y con $3\leq b \leq 4$. Así, $a$ tiene $2$ posibilidades y $b$ también, de modo que hay $2\cdot 2=4$ números que cumplen.

$\square$

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero $a$ tiene $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)$ divisores positivos.

Problema. Determina cuántos enteros hay entre $1$ y $10000$ que tienen $49$ divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se $49$.

Solución. Tomemos $a$ un entero y $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ su factorización en primos. Por la Proposición 4, necesitamos que $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49$.

A la izquierda tenemos puros números mayores o iguales que $2$. El número $49$ tiene como únicos divisores a $1$, $7$ y $49$. De esta forma, sólo hay dos casos posibles:

• El número $a$ tiene sólo un divisor primo y $a=p_1^{48}$.
• El número $a$ tiene dos divisores primos y $a=p_1^6p_2^6$.

El primer caso es imposible, pues $p_1$ sería por lo menos $2$ y $$2^{48}>2^{20}=(1024)^2>(1000)^2>10000.$$ Para el segundo caso, recordemos que $p_2>p_1$ en la factorización en primos. Si $p_2\geq 5$, entonces como $p_1\geq 2$, tendríamos $$a\geq (2\cdot 5)^6 = 1000000>10000,$$ así que esto no es posible.

La única otra posibilidad es $p_2=3$ y por lo tanto $p_1=2$. En este caso obtenemos al número $a=(2\cdot 3)^6=6^6=46656$, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

$\square$

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular $\MCD{a,b}$ y $\mcm{a,b}$ como sigue:
\begin{align*}
\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\
\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.
\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que $\MCD{a,b}\mcm{a,b}=ab$.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a $a$ y $b$ en su factorización en primos como lo discutimos arriba. Al multiplicar $\MCD{a,b}$ y $\mcm{a,b}$, el exponente de $p_i$ es $\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i+\beta_i$. Este es el mismo exponente de $p_i$ en $ab$. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si $p$ es primo, entonces todo entero $n$ que no sea múltiplo de $p$ tiene inverso módulo $n$. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.