Números, divisores y números primos (III). ¿Es primo o compuesto?

¿Es un número primo o compuesto?

 Publicado: 2020-09-28

En una entrada anterior ya hablamos de los números primos y que son infinitos. También vimos cómo averiguar si un número es primo o no mediante la criba de Eratóstenes. Ahora vamos a hablar un poquito sobre los divisores de un número. 

La entrada será larga, pues está dividida en cinco apartados, pero cada uno de ellos podría ser una entrada independiente. 

No todo lo que explico aquí se imparte en Educación Secundaria (al menos en España). Parte de lo que voy a contar, especialmente los apartados 4 y 5 estarían inmersos dentro del temario de una asignatura de Matemática Discreta de primero de carrera. Quédate con aquello que necesites, te guste o te apetezca.

1.- ¿Cómo se sabe si un número es primo o no?

Hay dos preguntas que nos podemos hacer con respecto a ésto. La primera es ¿es un número primo?; la segunda es ¿cuál es la descomposición factorial de este número? Lo que quiero dejar claro es que la respuesta a estas preguntas puede ser tremendamente enrevesada. 

Es muy fácil saber si 11,19, 43 son primos (todos lo son). Incluso números como 127 (que también es primo) es sencillo conocerlo, pero... ¿qué me dices de 30031? ¿y qué me dices de 100003? 

Voy a darte tres formas de calcular si un número es primo o no. Una que siempre explico en clase en 1º ESO; otra que a veces puedo explicar en 1º ESO o 2º ESO (dependiendo de cómo sean los alumnos de ese año); y otra que claramente pertenece a un ámbito universitario. Tampoco voy a introducirme en disquisiciones matemáticas de alto nivel, pues no es el objetivo de este blog. 

1.1.- Dividiendo por los primos anteriores

Si un número es compuesto será divisible por algún número primo menor que él. Basándonos en esto, y como podemos construir una tabla de números primos mediante la criba de Eratóstenes podemos ir probando por todos los números primos menores que el número que estamos estudiando a ver si tenemos suerte y alguno lo divide. Si no lo divide ninguno, entonces es primo. 

Ejemplo: los números primos menores de 100 son $\mathbb{P}=\{2,\ 3,\ 5,\ 7, \ 11, \ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 83,\ 89,\ 97,\ 101,\ 103,\ 107,\ 109,\ 113,\ 127,\ 131,\ 137,\ 139,\ 149,\ 151,\ 157,\ 163,\ 167,\ 173,\ 179,\ 181,\ 191,\ 193,\ 197,\ 199\}$

Que puestos en forma de tabla: 

Para saber si 11 es primo o no sólo debemos hacer las siguientes divisiones: 

$11=\mathbb{2}\cdot 5+1$

$11=\mathbb{3}\cdot 3+2$

$11=\mathbb{5}\cdot 2+1$

$11=\mathbb{7}\cdot 1+4$

Por lo que concluímos que 11 no es divisible por ningún primo menor que él y por tanto, 11 es un número primo. Observa que este es el razonamiento de Euclides para demostrar que hay infinidad de números primos. 

Para saber si 143 es primo o no, podemos ir probando todos los números primos menores que él (en total hay 33 números que probar)

$143=\mathbb{2}\cdot 70+1$

$143=\mathbb{3}\cdot 47+2$

$143=\mathbb{5}\cdot 28+3$

$143=\mathbb{7}\cdot 20+3$

$143=\mathbb{11}\cdot 13+0$

Y por tanto, $143$ no es un número primo. 

Ahora puedes intentar saber si $10103$ o $10231$ son primos o no (pista: uno de ellos es primo y otro no)

Ventajas de este método

• Es un método sencillo.
• Es muy fácil de entender. 
• Siempre lleva a una solución. 

Desventajas de este método

• Para números un poco grandes es casi imposible de hacerlo a mano. 
• Consume muchísimo tiempo. 
• Hay que hacer tantas operaciones que, al final, es fácil equivocarse (aún cuando uses calculadora).

1.2.- Usando la raíz cuadrada.

Si tenemos todos los números naturales hasta uno dado $P=\{1,\ 2,\ \ldots, \ n\}$ y queremos saber cual es el mayor número que podemos conseguir multiplicando dos de ellos (pueden ser iguales), es muy fácil comprobar que el mayor de ellos es $n^2$. Este principio lo podemos usar al revés: "si ningún número primo, menor que la raíz cuadrada del que estamos estudiando, divide a nuestro número en estudio; entonces ese número es primo". 

Ejemplo: queremos saber si el número 101 es primo o no. De acuerdo con el procedimiento anterior, deberíamos ir probando todos los números menores que 101 a ver si hay suerte y alguno lo divide. Pero ahora, tan solo debemos usar aquellos que sean menores que su raíz cuadrada, lo cual simplifica mucho las operaciones, ya que ahora solo tenemos que probar con los números primos $p<\sqrt{101}=10,0498\ldots<11$; es decir ahora solo tenemos que probar con $2,\ 3,\ 5,\ 7$ 

$101=2\cdot 50 +1$

$101=3\cdot 33 +2$

$101=5\cdot 20 +1$

$101=7\cdot 14 +3$

Y por tanto deducimos que $101$ es un número primo.

Ventajas de este método.

• "Elimina" muchos números a probar, así que facilita los cálculos. 
• Se puede hacer en un número finito de pasos. 

Desventajas de este método

• Las mismas que en el caso anterior. Sobre todo si los números son grandes

1.3.- Algoritmo de factorización de Fermat.

Este algoritmo fue desarrollado por Pierre de Fermat. Yo no lo enseño en Educación Secundaria: hay que estar muy loco para meterse en un jardín como este con chavales de 12-18 años. 

Cualquier número primo, salvo el dos, es impar. Por lo tanto, si un número impar es compuesto, sus factores son impares: 

$$n=a\cdot b\qquad \text{con $a,\ b$ impares}$$

Podemos suponer que $1<b\leq a$. Además podemos poner que: 

$$n=\left(\frac{a+b}{2}\right)^2-\left(\frac{a-b}{2}\right)^2$$

Así pues, estudiar si un número impar es compuesto equivale a estudiar la ecuación $y^2= x^2-n$, donde: 

$$y=\frac{a-b}{2}\qquad x=\frac{a+b}{2}$$

Lo primero que debemos hacer es encontrar el menor $q$ tal que $n\neq q^2$ y después probamos si alguno de los siguientes números es un cuadrado: 

$q^2-n, \qquad  (q+1)^2-n, \qquad  (q+2)^2-n, \ldots$ 

Este proceso no es infinito, ya que: 

$$\left(\frac{n+1}{2}\right)^2-n=\left(\frac{n-1}{2}\right)^2$$

Pero esta solución es la factorización trivial $n=n\cdot 1$. Por lo que los únicos valores que hay que estudiar son aquellos números $\alpha$ que satisfacen: 

$$q\leq \alpha <\frac{n+1}{2}$$

Y si, para ninguno de ellos tenemos que $\alpha^2-n$ es un cuadrado, entonces $n$ es primo. 

Ejemplo: queremos saber si $2523$ es primo o no. 

1. $51$ es el menor número tal que $51^2= 2601>2523$ 
2. Ya sabemos que $q=51$, también sabemos que $\displaystyle \frac{2523+1}{2}=1262$
3. Comprobamos si son cuadrados los números siguientes (probamos desde $51$ hasta $1262$): 
1. $51^2-2523=  78$  
2. $\left(51+1\right)^2-2523=  181$  
3. $\left(51+2\right)^2-2523=  286$  
4. $\left(51+3\right)^2-2523=  393$  
5. $\left(51+4\right)^2-2523=  502$  
6. $\left(51+5\right)^2-2523=  613$  
7. $\left(51+6\right)^2-2523=  726$  
8. $\left(51+7\right)^2-2523=  841= 29^2$

Con esto hemos encontrado nuestros números $x$ e $y$, que son: 

$x=58\qquad y=29$

Y puesto que sabemos que $\displaystyle y=\frac{a-b}{2}, \,  x=\frac{a+b}{2}$ tan solo nos queda resolver el siguiente sistema de ecuaciones:

$a-b=58$

$a+b=116$

Cuyas soluciones son $a=87=3\cdot 29$ y $b=29$

Así sabemos que $2523$ no es un número primo. De hecho su factorización es: $2523= 3\cdot 29^2$

Ventajas de este método

• "Aparca" el estudio de muchos primos pequeños, aunque posteriormente puedan volver a salir en la factorización. 
• La resolución de la ecuación $y^2=x^2-n$ es mucho más sutil e inteligente, que otros métodos de "fuerza bruta".

Desventajas de este método

• Conceptualmente es un algoritmo complejo.
• Es necesario entrenar el método antes de poder considerarlo dominado. 
• La cantidad de números $\alpha$ a probar puede ser muy grande, a menos que tengamos la suerte de dar con un cuadrado perfecto al inicio del algoritmo.

BIBLIOGRAFÍA

• Bujalance, E., Bujalance, J. A., Costa, A. F., Martínez, E.; 2005; Elementos de Matemática Discreta; Ed. Sanz y Torres; Madrid; ISBN: 84-96094-61-8

Números, divisores y números primos (II) La criba de Eratóstenes

La criba de Eratóstenes.

 Publicado: 2020-09-14

Eratóstenes fue un matemáticos griego, coetáneo de Arquímedes y Aristarco. Nació en Cirene pero la juventud la pasó en Atenas que abandonó para ir a Alejandría cuando lo llamó Ptolomeo III el cual le encomendó ser tutor de sus hijos y bibliotecario de la ciudad. 

Fue capaz de idear un método para ir aislando los diferentes números primos. Es un algoritmo sencillo, muy fácil de entender y de llevar a la práctica. 

Imagina que quieres saber los números primos que son menores de 50. 

Lo primero que debes hacer es una tabla con dichos números, porque vamos a ir tachando algunos de ellos y los que "sobrevivan", serán los números primos menores de 50: 

 

• Una vez que tenemos los números colocados seleccionamos el primer primo: $2$. 
• Ahora vamos contando y tachamos CADA DOS números. Así tachamos el $4$, $6$, $8$... hasta agotar todos los que sean menores de $50$ (número que por cierto, también tachamos. 
• Ahora elegimos el siguiente número superviviente, el $3$, y vamos tachando CADA TRES lugares (los que están tachados, también los contamos) hasta agotar todos lo que hay. Así tachamos el $6$, $9$, $12$,...
• El siguiente que sobrevive es el $5$ ¿Adivina qué hay que hacer? tachar CADA CINCO lugares. Así tachamos el $10$, $15$, $20$... 
• El siguiente superviviente es el $7$, y tachamos CADA SIETE lugares y... 
• Y así vamos repitiendo con todos los que van quedando sin tachar

Así al final te tiene que quedar la siguiente tabla con 15 números supervivientes

Números primos menores de 50