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 no es primo pues su único divisor es él mismo. Pero
,
y
sí son primos. De aquí y el algoritmo de la división, si
es primo y
es un entero, entonces
o
.
Proposición 1. Si es un número primo que divide al producto de enteros
, entonces
ó
.
Demostración. Si no divide a
, entonces
, así que existe una combinación lineal entera
. Multiplicando esta combinación por
, tenemos que
. Como
divide a
y a
, entonces divide a
.
Problema. Muestra que si es un primo que divide a
, entonces
divide a
.
Sugerencia pre-solución. Aquí y
no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.
Solución. Sea un entero,
un entero positivo y
un primo. Vamos a mostrar por inducción en
que si
, entonces
. Para
la conclusión es inmediata. Supongamos el resultado cierto para
. Si
, por la Proposición 1 tenemos que
(en cuyo caso terminamos), o que
(en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando
y
.
Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.
Proposición 2. Si es primo,
un entero y
un entero positivo tales que
, entonces
.
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 un entero positivo. Entonces existe un único
, únicos primos
y exponentes
tales que
La idea de la demostración es factorizar y factorizar. Si 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 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 con
y
enteros. De aquí,
. En la factorización en primos de
y
tenemos una cantidad múltiplo de
de factores
. Así, en el lado derecho tenemos una cantidad mútiplo de
de factores
(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.
Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.
Problema. Determina todos los enteros positivos para los cuales
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 . De aquí,
Por la unicidad del teorema fundamental de la aritmética, cada uno de los números y
tienen que ser potencias de
, digamos
y
con
y
. Además tenemos que
Como es impar, de nuevo por la unicidad de la factorización en primos debemos tener que
, y por lo tanto que
. De aquí,
y
, y así
. Por lo tanto, el único candidato es
.
Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que en efecto es solución. Hacemos esto último notando que
que en efecto es un número cuadrado.
Fórmulas que usan el teorema fundamental de la aritmética
Sean y
números enteros positivos y
el conjunto de números primos que dividen a alguno de
o
. Por el teorema fundamental de la aritmética, existen exponentes
y
, tal vez algunos de ellos cero, tales que
Por ejemplo, si , entonces
,
y
.
Proposición 3. Se tiene que divide a
si y sólo si para todo primo
se tiene que
.
Problema. ¿Cuántos múltiplos de hay que sean divisores de
?
Sugerencia pre-solución. Factoriza en primos a y a
y usa la Proposición 3.
Solución. Tenemos que y que
. Por la Proposición 3, un número que funcione debe ser de la forma
con
y con
. Así,
tiene
posibilidades y
también, de modo que hay
números que cumplen.
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 tiene
divisores positivos.
Problema. Determina cuántos enteros hay entre y
que tienen
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 .
Solución. Tomemos un entero y
su factorización en primos. Por la Proposición 4, necesitamos que
.
A la izquierda tenemos puros números mayores o iguales que . El número
tiene como únicos divisores a
,
y
. De esta forma, sólo hay dos casos posibles:
- El número
tiene sólo un divisor primo y
- El número
tiene dos divisores primos y
El primer caso es imposible, pues sería por lo menos
y
. Para el segundo caso, recordemos que
en la factorización en primos. Si
, entonces como
, tendríamos
, así que esto no es posible.
La única otra posibilidad es y por lo tanto
. En este caso obtenemos al número
, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.
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 y
como sigue:
Volvamos a ver un problema que ya habíamos resuelto con anterioridad.
Problema. Demuestra que .
Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.
Solución. Expresemos a y
en su factorización en primos como lo discutimos arriba. Al multiplicar
y
, el exponente de
es
. Este es el mismo exponente de
en
. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.
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 es primo, entonces todo entero
que no sea múltiplo de
tiene inverso módulo
. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.