Numeros Primos Y Compuestos

Números Primos y su Distribusión

Definición: Un número $p>1$ es llamado número primo o simplemente primo, si sus únicos divisores positivos son 1 y $p$. Un entero mayor que 1 que no es primo es llamado compuesto.

Notar que $2$ es el único número primo que es par. También notar que el $1$ no es primo ni compuesto.

En general denotaremos a los números primos con las letras $p,q$ a menos que se especifique lo contrario.

En su libro noveno de Euclides (los elementos) aparece una proposición que más tarde sería conocida como el teorema fundamental de la aritmética. A saber, que todo número mayor que uno, puede, excepto por el orden de los factores, expresarse como producto de primos en una forma única. De esta manera, los números primos son los tabiques de los enteros, están en su base.

Teorema: Si $p$ es un primo y $p\mid ab \Rightarrow p\mid a \lor p\mid b$.

Demostración: Esta es una aplicación del teorema de Euclides en divisibilidad. En efecto, si $p\mid a$ entonces no hay nada que hacer. Por el contrario si $p\nmid a$ entonces $(p,a)=1$ y como $p|ab$ concluimos que $p|b$ por el teorema de Euclides. QED.

Corolario: Si $p$ es primo y $p\mid a_1a_2\cdots a_n$ entonces $p\mid a_k$ para algun $k\in \left\{ 1,\cdots, n \right\}$.

La demostración es por inducción…

Corolario: Si $p\mid q_1q_2\cdots q_n$ con todos los $q_i$ primos, entonces $p=q_k$ para algún $k, \quad 1\le k\le n$.

Dado un entero particular, ¿Cómo podemos saber si es primo o no? Si el número es compuesto, ¿Cómo podemos encontrar un divisor no trivial? La primera idea es verificar si todos los enteros menores son divisores, si los únicos divisores son el 1 y el -1 entonces el número será primo. Este método es simple pero costoso en términos de cómputo.

Sin embargo hay una propiedad que nos podría facilitar el cálculo.

Proposición Todo número compuesto $n$ tiene un divisor $a$ tal que $1\le a\le \sqrt{n}$.

En efecto, como $n$ es compuesto, $n=ab$ con $1\le a,b \le n$. Si $a=b$ entonces $a=\sqrt n$. En caso contrario podemos suponer, sin perdidia de generalidad, que $1< a < b < n$ y entonces $a^2<ab=n$ por lo que $a < \sqrt n$. QED.

Corolario: Todo entero compuesto $n$ tiene un divisor primo $p \le \sqrt n$.

En efecto, si $a$ es un divisor de $n$ tal que $a\le \sqrt n$ entonces como $a$ o es primo o producto de primos, concluimos que cualquier divisor primo $p$ de $a$ cumplirá con que $p\le \sqrt n$.

Así, para ver si un número es primo, basta ver que ningún primo menor o igual que su raíz cuadrada lo divide. Si éste es el caso, el número en cuestión será primo.

Ejemplo: Supongamos que quiero averiguar si el número 231 es primo. Como la raíz de 231 está entre 15 y 16 bastará entonces ver si algún primo menor que 15 divide a 231. Es decir si 2, 3, 5, 7 ,11 o 13 lo dividen. Obviamente 2 no lo divide, pero 3 lo divide, así que 231 es compuesto. Similarmente si trabajamos con 509 vemos que su raíz cuadrada está entre 22 y 23 por lo que tenemos que verificar si los primos menores que 22 lo dividen o no. Si hacemos las divisiones vemos que ninguno de estos primos lo divide así que 509 es primo.

La Criba de Eratóstenes

Otro matemático Griego que trabajó en teoría de números fue Eratóstenes de Cirene (Actualmente Libia), entre los años 276-194 A.C. [Eratostenes en Wikipedia] quien fue director de la famosa librerìa de Alexandría. Entre otras cosas, Eratostenes midió con gran precisión la circunferencia de la tierra usando simplemente geometría euclidiana. La aportación más famosa de Eratóstenes a la teoría de números es usar el resultado anterior para crear una criba para encontrar números primos menores que $n$ [Animación de la Criba]. Ésta consiste en ir eliminando todos los múltiplos de 2, de 3, de 3 etc en orden hasta llegar a la raíz de $n$. Todos los números no eliminados serán entonces primos.

Infinidad de los Primos

Teorema (Euclides): Hay una infinidad de primos.

Demostración: La demostración de Euclides es por contradicción. Supongamos que sólo hay un número finito, Sean estos $\left\{ p_1, p_2, \ldots, p_n \right\}$. Consideremos ahora el número $P= p_1\cdots p_n +1$. Tenemos dos opciones, o $P$ es primo o $P$ es compuesto. Pero $P$ no puede ser primo pues es más grande que todos los primos en la lista (que estamos suponiendo son todos), por lo que entonces $P$ es compuesto y existe un primo $p\mid P$ pero entonces $p=p_k$ para algún $k$, es decir es un miembro de la lista, pero entonces como $p \mid \prod p_k +1$ y $p| \prod p_k$ concluimos que $p\mid 1$ lo cual no es posible. Esto contradice la suposición de que sólo hay un número finito de primos.

Ejercicio: Es interesante notar que el número $P_k = \prod_i^k p_i +1$ es primo para los primeros valores de $k = 1,\cdots, 5$ sin embargo para $P_6, P_7, P_8$ no lo son.

El teorema de Euclides es tan importante que hay que dar más de una prueba. Presentemos una variante de la prueba anterior.

Consideremos la sucesión infinita de enteros:

(1)
\begin{align} n_1 = 2 \\ n_1 = n_1+1 \\ n_3= n_1n_2+1\\ n_4 = n_1n_2n_3+1 \\ \vdots n_k= n_1n_2n_3\cdots n_{k-1}+1 \end{align}

Como cada uno de estos enteros es mayor que uno, entonces cada uno de estos enteros tiene un factor primo, sin embargo, para cuales quiera dos de estos enteros si mcd es uno, esto es $(n_r,n_k)=1$ pues si suponemos que $(n_k,n_r)=d$ con $r<k$ entonces $d \mid n_1n_2\ldots n_{k-1}$ pues divide a $n_r$ pero como divide a $n_k$ entonces tenemos que $d\mid n_k - n_1n_2\cdots n_{k-1} =1$ lo que implica que $d=1$. Por lo tanto los factores primos de $n_k$ son distintos para todo $k$ y debemos tener entonces una infinidad de primos (al menos uno para cada $k \in \left\{ 1,2 \ldots \right\}$).

Ahora tomemos $\left\{ p_n \right\}$ a la sucesión infinita de números primos en orden creciente. La prueba de Euclides nos muestra que

(2)
\begin{align} p_{n+1} \le p_1p_2\ldots p_n +1 < p_n^n+1 \end{align}

pues $p_1p_2\ldots p_n +1$ tiene un factor primo $p \ne p_k$ con $k=1, \cdots , n$ y por lo tanto $p_{n+1}\le p (< p_1p_2\ldots p_n +1)$. Esto nos da una estimación de la taza de crecimiento de $p_n$. Por ejemplo para $n=3$ tenemos que la desigualdad anterior nos dice que

(3)
\begin{equation} 7 = p_4 < p_3^3+1 = 5^3 +1 = 126. \end{equation}

Es una estimación no muy buena, pero estimación a fin de cuentas. Una mejor estimación está dada en el siguiente teorema:

Teorema: Si $p_n$ es el n-ésimo primo, entonces $p_n \le 2^{2^{n-1}}$.

Demostración: La prueba es por inducción: La base de la inducción es para $n=1$ en cuyo caso el resultado es obvio. La hipótesis de inducción es suponer que para $n>1$ el resultado es verdadero para todos los enteros positivos hasta $n$. Entonces:

(4)
\begin{align} p_{n+1} \le p_1p_2\cdots p_n +1 \le 2(2^2)\cdots(2^{2})+1 \le 2^{1+2+\cdots + 2^{n-1}} +1 = 2^{2^{n-1}}+1 \end{align}

pero $1\le 2^{2^{n-1}}$ por lo que $p_n \le 22^{2^{n-1}} = 2^{2^n}$.

Corolario: Para $n\ge 1$, hay al menos $n+1$ primos menores que $2^{2^n}$.

En efecto, de el teorema anterior tenemos que $p_1, p_2, \ldots p_{n+1}$ son menores que $2^{2^n}$.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License