Números primos I

Para clasificar un entero positivo podemos mirar cuántos divisores positivos tiene. Observa los primeros números:

Esto motiva las definiciones.

1.1 La unidad

El número $1$ tiene un solo divisor positivo: él mismo.
Por eso no es primo ni compuesto.

1.2 Números primos

Un entero positivo es primo absoluto, o simplemente primo, si tiene exactamente dos divisores positivos:

$$1 \quad \text{y} \quad \text{él mismo}.$$

Ejemplos:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\dots$$

El menor número primo es $2$.
También se les llama números simples, junto con la unidad, porque tienen a lo más dos divisores.

En $\mathbb{Z}^+$, “primo” significa primo absoluto: exactamente dos divisores positivos. No confundas con el uso en $\mathbb{Z}$, donde $p$ y $-p$ se consideran primos enteros.

1.3 Números compuestos

Un entero positivo es compuesto si tiene más de dos divisores positivos.

Ejemplos:

$$4,\ 6,\ 8,\ 9,\ 10,\ 12,\ 14,\ 15,\dots$$

El menor número compuesto es $4$.

Una observación muy útil:

Todo número compuesto tiene al menos un divisor primo.

Por ejemplo, $6$ tiene divisor primo $2$ y $3$; $15$ tiene divisores primos $3$ y $5$.

1.4 Primeros números primos

Conviene memorizar al menos los primos menores que $100$:

$$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.$$

Esta lista permite aplicar con rapidez el criterio de la raíz cuadrada que veremos pronto.

1.5 Propiedades básicas de los números primos

Algunas propiedades inmediatas:

1. Existen infinitos números primos.
   Euclides dio un argumento clásico: si existiera un número finito de primos $p_1,p_2,\dots,p_k$, entonces
   $$P=p_1p_2\cdots p_k+1$$ sería mayor que $1$ y tendría un divisor primo. Ese divisor no podría ser ninguno de los $p_i$, porque al dividir $P$ entre cada $p_i$ deja residuo $1$. Por tanto habría un primo nuevo, lo que contradice que la lista era finita.

2. El único primo par es $2$.
   Todos los demás primos son impares, porque cualquier otro par mayor que $2$ es divisible entre $2$.

3. Los únicos números consecutivos que son primos a la vez son $2$ y $3$.
   Entre dos números consecutivos, uno es par. Si ambos fueran primos, el par debería ser $2$.

4. Los únicos impares consecutivos que son primos a la vez son $3,5,7$.
   Porque en tres impares consecutivos siempre hay uno múltiplo de $3$.

5. Todo primo $p>2$ es de la forma
   $$p=4k+1 \quad \text{o} \quad p=4k-1.$$ Lo contrario no siempre es cierto: $15=4(4)-1$, pero $15$ no es primo.

6. Todo primo $p>3$ es de la forma
   $$p=6k+1 \quad \text{o} \quad p=6k-1.$$ Justificación: todo entero se expresa como $6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5$.
   Si $p>3$, no puede ser $6k$ ni $6k+2$ ni $6k+4$, porque serían pares; tampoco puede ser $6k+3$, porque sería múltiplo de $3$. Solo quedan $6k+1$ y $6k+5=6(k+1)-1$.
   Lo contrario no siempre se cumple: $25=6(4)+1$, pero $25$ es compuesto.

No hace falta dividir un número entre todos los enteros menores que él. Basta usar el criterio de la raíz cuadrada:

Sea $n>1$. Si $n$ es compuesto, entonces $n=a\cdot b$ con $1<a\le b<n$.
En ese caso, $a\le \sqrt{n}$. Por tanto, si $n$ no tiene ningún divisor primo menor o igual que $\sqrt{n}$, entonces $n$ es primo.

Pasos prácticos

1. Calcula $\sqrt{n}$ y toma su parte entera.
2. Escribe todos los primos menores o iguales que esa parte entera.
3. Divide $n$ entre cada uno de esos primos.
   • Si ninguna división es exacta, $n$ es primo.
   • Si al menos una es exacta, $n$ es compuesto.

Ejemplo 1

Determina si $229$ es primo.

$$\sqrt{229}\approx 15,13$$

Los primos menores o iguales que $15$ son:

$$2,3,5,7,11,13.$$

Ahora dividimos:

$$229 \text{ no es divisible entre } 2,3,5,7,11,13.$$

Por lo tanto, $229$ es primo.

Ejemplo 2

Determina si $221$ es primo.

$$\sqrt{221}\approx 14,87$$

Primos menores o iguales que $14$:

$$2,3,5,7,11,13.$$

Al dividir:

$$221 = 13\cdot 17.$$

Como $13\mid 221$, el número $221$ es compuesto.

La criba de Eratóstenes es el método clásico para obtener primos menores que una cota dada: se colocan los números del $2$ en adelante, se tachan los múltiplos de $2$ salvo el $2$, luego los de $3$ salvo el $3$, y así sucesivamente. Los que quedan sin tachar son primos.

Criba de Eratóstenes del 2 al 60: primos resaltados y compuestos tachados

El teorema fundamental de la aritmética afirma lo siguiente:

Todo entero $N>1$ se puede expresar de manera única como producto de números primos elevados a exponentes positivos.

Ordenando los primos de menor a mayor, escribimos:

$$N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m},$$

donde

$$p_1<p_2<\cdots<p_m$$

son primos distintos y los exponentes $\alpha_i$ son enteros positivos.

Esta expresión se llama descomposición canónica, abreviada D.C..

Ejemplo

Descompongamos $360$:

$$360 = 2^3\cdot 3^2\cdot 5.$$

Aquí los primos son $2,3,5$, ordenados de menor a mayor.

No está en D.C. si hay bases compuestas o no ordenadas. Por ejemplo,

$$N=2^2\cdot 4^3\cdot 5$$

no está en forma canónica, porque $4$ es compuesto. Su forma canónica es:

$$2^2\cdot 4^3\cdot 5 = 2^2\cdot (2^2)^3\cdot 5 = 2^8\cdot 5.$$

La descomposición canónica permite calcular cuántos divisores tiene un número y cuánto suman o cuánto vale su producto.

4.1 Cantidad de divisores positivos

Si

$$N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m},$$

entonces todo divisor positivo $d$ de $N$ tiene la forma

$$d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_m^{\beta_m},$$

donde cada exponente $\beta_i$ puede tomar los valores

$$0,1,2,\dots,\alpha_i.$$

Hay $\alpha_i+1$ opciones para cada exponente. Por tanto:

$$\operatorname{CD}(N)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_m+1).$$

Ejemplo

Para $N=360=2^3\cdot 3^2\cdot 5^1$,

$$\operatorname{CD}(360)=(3+1)(2+1)(1+1)=4\cdot 3\cdot 2=24.$$

Así, $360$ tiene $24$ divisores positivos.

4.2 Suma de divisores positivos

Para un solo factor primo $p^\alpha$, la suma de sus divisores es la suma geométrica:

$$1+p+p^2+\cdots+p^\alpha = \frac{p^{\alpha+1}-1}{p-1}.$$

Como los factores primos de la D.C. son independientes, la suma de todos los divisores de $N$ es el producto de esas sumas:

$$\operatorname{SD}(N)=\prod_{i=1}^{m}\frac{p_i^{\alpha_i+1}-1}{p_i-1}.$$

Ejemplo

Para $N=360=2^3\cdot 3^2\cdot 5$,

$$\operatorname{SD}(360)= \frac{2^{4}-1}{2-1}\cdot \frac{3^{3}-1}{3-1}\cdot \frac{5^{2}-1}{5-1}.$$

Calculamos:

$$\frac{2^4-1}{1}=15, \quad \frac{3^3-1}{2}=13, \quad \frac{5^2-1}{4}=6.$$

Luego,

$$\operatorname{SD}(360)=15\cdot 13\cdot 6 = 1170.$$

4.3 Promedio de divisores positivos

Si se pide el promedio de los divisores positivos de $N$, basta recordar:

$$\text{promedio} = \frac{\operatorname{SD}(N)}{\operatorname{CD}(N)}.$$

Esto aparece en problemas aplicados donde se habla de bonificaciones, repartos o precios.

4.4 Producto de divisores positivos

Si agrupamos cada divisor $d$ con su complementario $N/d$, cada pareja tiene producto $N$. Hay $\operatorname{CD}(N)$ divisores, así que se forman $\operatorname{CD}(N)/2$ parejas. Por tanto:

$$\operatorname{PD}(N)=N^{\operatorname{CD}(N)/2}.$$

También suele escribirse:

$$\operatorname{PD}(N)=\sqrt{N^{\operatorname{CD}(N)}}.$$

Ejemplo

Para $360$, ya vimos que $\operatorname{CD}(360)=24$. Entonces

$$\operatorname{PD}(360)=360^{12}.$$

Muchas preguntas no piden todos los divisores de $N$, sino los divisores que cumplen una condición. La más común es:

¿Cuántos divisores de $N$ son múltiplos de $k$?
¿Cuánto suman los divisores de $N$ múltiplos de $k$?

El procedimiento es simple. Si $k\mid N$, escribimos:

$$N=k\cdot m.$$

Un divisor $d$ de $N$ que sea múltiplo de $k$ debe tener la forma

$$d=k\cdot t,$$

donde $t\mid m$. Por lo tanto:

$$\operatorname{CD}_{\dot{k}}(N)=\operatorname{CD}(m)=\operatorname{CD}\left(\frac{N}{k}\right).$$

Para la suma:

$$\operatorname{SD}_{\dot{k}}(N) = \sum_{t\mid m} kt = k\sum_{t\mid m} t = k\cdot \operatorname{SD}(m).$$

Ejemplo

Hallemos la cantidad y suma de los divisores de $144$ que son múltiplos de $6$.

Como

$$144=6\cdot 24,$$

entonces

$$\operatorname{CD}_{\dot{6}}(144)=\operatorname{CD}(24).$$

Además,

$$24=2^3\cdot 3$$

así que

$$\operatorname{CD}(24)=(3+1)(1+1)=8.$$

La suma de los divisores múltiplos de $6$ es:

$$\operatorname{SD}_{\dot{6}}(144)=6\cdot \operatorname{SD}(24).$$

Calculamos:

$$\operatorname{SD}(24)=\frac{2^4-1}{2-1}\cdot \frac{3^2-1}{3-1} =15\cdot 4=60.$$

Luego,

$$\operatorname{SD}_{\dot{6}}(144)=6\cdot 60=360.$$

Divisores múltiplos de un número pero no de otro

Si se pide, por ejemplo, cuántos divisores de $N$ son múltiplos de $2$ pero no de $3$, usamos:

$$\operatorname{CD}_{2,\ \text{no }3}(N) = \operatorname{CD}_{\dot{2}}(N)-\operatorname{CD}_{\dot{6}}(N).$$

Porque “múltiplo de $2$ y de $3$” equivale a “múltiplo de $6$”.

Dos o más enteros positivos son primos entre sí, coprimos o PESI si su único divisor común positivo es $1$. Equivalentemente:

$$\operatorname{MCD}(a,b)=1.$$

Ejemplos

• $2$ y $13$ son PESI, porque $\operatorname{MCD}(2,13)=1$.
• $9$ y $20$ son PESI, porque $\operatorname{MCD}(9,20)=1$, aunque ambos son compuestos.

Esto es importante: PESI no significa que los números sean primos. Significa que no comparten factores primos.

6.1 PESI dos a dos

Un conjunto de números es PESI dos a dos cuando cada pareja tomada entre ellos es PESI.

Ejemplo: $8,21,25$ son PESI dos a dos porque

$$\operatorname{MCD}(8,21)=1, \quad \operatorname{MCD}(8,25)=1, \quad \operatorname{MCD}(21,25)=1.$$

Si un conjunto es PESI dos a dos, entonces todo el conjunto es PESI. El recíproco no siempre se cumple.

Contraejemplo clásico: $6,10,15$.

$$\operatorname{MCD}(6,10,15)=1,$$

así que como conjunto son PESI, pero no son PESI dos a dos, porque

$$\operatorname{MCD}(6,10)=2, \quad \operatorname{MCD}(6,15)=3, \quad \operatorname{MCD}(10,15)=5.$$

6.2 Propiedades útiles de los PESI

1. Dos números consecutivos siempre son PESI.
   Si $d\mid n$ y $d\mid n+1$, entonces $d$ divide a su diferencia: $$d\mid (n+1)-n=1.$$ Luego $d=1$.

2. Si $a$ y $b$ son PESI, entonces $a^m$ y $b^n$ también son PESI.

3. Si $a$ es PESI con $b$ y también con $c$, entonces $a$ es PESI con $b\cdot c$.

4. Si un grupo de números incluye al $1$, entonces el grupo es PESI, porque el máximo común divisor siempre será $1$.

5. Dos números pares positivos nunca son PESI, porque ambos comparten el factor $2$.

6. Si $a+b$ es un número primo, entonces $a$ y $b$ son PESI.
   En efecto, si $d\mid a$ y $d\mid b$, entonces $d\mid a+b$. Como $a+b$ es primo, $d=1$ o $d=a+b$. Pero $d$ es divisor de $a$ y de $b$, y $a,b$ son menores que $a+b$, así que no puede ser $a+b$. Luego $d=1$.

Estas propiedades son muy útiles para problemas en los que se pide garantizar que dos números no comparten factores.

El teorema de Gauss que se usa en este nivel tiene dos formas equivalentes.

Forma con primos

Si $p$ es un número primo y

$$p\mid ab,$$

entonces

$$p\mid a \quad \text{o} \quad p\mid b.$$

Es decir, si un primo divide a un producto, necesariamente divide a uno de los factores.

Más generalmente, si

$$p\mid a_1a_2\cdots a_k,$$

entonces $p$ divide al menos a uno de los $a_i$.

Forma general con PESI

Si

$$a\mid bc$$

y además $a$ y $b$ son PESI, entonces

$$a\mid c.$$

La idea intuitiva es que los factores primos de $a$ no están en $b$, así que para que $a$ divida al producto $bc$, esos factores deben estar en $c$.

Ejemplo

Sabemos que

$$4\mid 9\cdot 20,$$

porque $9\cdot 20=180$ y $180=4\cdot 45$.

Además, $4$ y $9$ son PESI. Entonces, por el teorema de Gauss:

$$4\mid 20.$$

Efectivamente, $20=4\cdot 5$.

Peligro si no son PESI

Si falla la condición de que sean PESI, el teorema no se aplica. Por ejemplo,

$$6\mid 4\cdot 9$$

porque $4\cdot 9=36$ y $36=6\cdot 6$. Sin embargo,

$$6\nmid 4 \quad \text{y} \quad 6\nmid 9.$$

Aquí $\operatorname{MCD}(6,4)=2\neq 1$, por eso no se cumple la conclusión.

El teorema de Gauss se usa mucho para simplificar condiciones de divisibilidad, especialmente cuando se sabe que un número es PESI con otro.

Un factorial es el producto de todos los enteros positivos desde $1$ hasta $n$:

$$n! = 1\cdot 2\cdot 3\cdots n.$$

Para descomponer canónicamente $n!$, necesitamos saber cuántas veces aparece cada número primo $p$ en ese producto.

Exponente de $p$ en $n!$

El exponente del primo $p$ en la D.C. de $n!$ se calcula con la suma:

$$v_p(n!) = \left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor + \left\lfloor \frac{n}{p^3}\right\rfloor +\cdots$$

Aquí $\lfloor x\rfloor$ significa “parte entera de $x$”, es decir, el mayor entero menor o igual que $x$.

¿Por qué funciona?

• $\lfloor n/p\rfloor$ cuenta los múltiplos de $p$ entre $1$ y $n$.
• $\lfloor n/p^2\rfloor$ agrega un factor $p$ adicional para los múltiplos de $p^2$.
• $\lfloor n/p^3\rfloor$ agrega otro factor para los múltiplos de $p^3$.

Y así sucesivamente.

Ejemplo

Hallemos el exponente de $2$ en $20!$.

$$\left\lfloor \frac{20}{2}\right\rfloor =10, \quad \left\lfloor \frac{20}{4}\right\rfloor =5, \quad \left\lfloor \frac{20}{8}\right\rfloor =2, \quad \left\lfloor \frac{20}{16}\right\rfloor =1.$$

Sumamos:

$$10+5+2+1=18.$$

Por tanto,

$$v_2(20!)=18.$$

Para $3$:

$$\left\lfloor \frac{20}{3}\right\rfloor =6, \quad \left\lfloor \frac{20}{9}\right\rfloor =2.$$

Entonces

$$v_3(20!)=6+2=8.$$

Para $5$:

$$\left\lfloor \frac{20}{5}\right\rfloor =4.$$

Luego

$$v_5(20!)=4.$$

Así, una parte de la D.C. de $20!$ es:

$$20! = 2^{18}\cdot 3^8\cdot 5^4\cdot 7^2\cdot 11\cdot 13\cdot 17\cdot 19.$$

Faltarían los primos mayores que $20$, que no aparecen.

Aplicación: cantidad de ceros finales de un factorial

Un número termina en ceros según cuántas veces aparece el factor $10$, es decir, cuántas veces aparece $2\cdot 5$.

Como en un factorial hay más factores $2$ que $5$, la cantidad de ceros finales de $n!$ es:

$$v_5(n!).$$

En $20!$,

$$v_5(20!)=4,$$

así que $20!$ termina en $4$ ceros.