Números primos y compuestos#
Introducción#
En este capítulo vamos a ver dos tipos de números. Los números compuestos, los cuales podemos expresar como un producto de dos o más números distintos de \(1\) y él mismo. Por ejemplo \(12 = 6\cdot 2 = 4\cdot3\), \(15 = 5\cdot 3\) o también \(12 = 2\cdot 2\cdot 3\). En otras palabras estos números tienen más de dos divisores positivos. Y los números primos, que son aquellos que únicamente podemos expresar como el producto de él mismo con el \(1\). Por ejemplo \(13 = 13\cdot 1\). Dicho de otra forma, estos números sólo tienen dos divisores: \(1\) y él mismo.
Cabe destacar que el número \(1\) no se considera primo ni compuesto, ya que únicamente tiene un divisor: el mismo \(1\).
También definiremos formalmente el concepto de número compuesto y número primo. Los números primos y compuestos son conceptos fundamentales en matemáticas que desempeñan un papel crucial en la teoría de números. Estos números son la base de muchas propiedades y aplicaciones en diversos campos.
Definición de números compuestos y ejemplos#
Con base en la Definición 2 de divisibilidad, para cualquier entero \(n\) se tiene que \(-n\), \(-1\), \(1\) y \(n\) son divisores de \(n\). Cuando hay más divisores para \(n\), tenemos una situación especial que definimos a continuación.
Definición 5 (Divisor propio y divisor no trivial)
Sea \(n\) un entero y \(d\) un divisor de \(n\). Decimos que:
\(d\) es un divisor trivial de \(n\) si \(d\) es igual a \(-n\), \(-1\), \(1\) y \(n\).
\(d\) es un divisor propio de \(n\) si es diferente de los divisores triviales.
Definición 6 (Número compuesto)
Un número entero \(n\) se dice que es compuesto si tiene algún divisor propio.
Ejemplo 20
Por ejemplo, si tomamos el número \(12\), podemos encontrar los divisores positivos de éste, los cuales son \(1,2,3,4,6,12\). Por lo tanto, ya que \(12\) tiene a \(2,3,4,6\) como divisores propios, es un número compuesto.
Teorema 4
Para cada entero positivo \(n\), hay \(n\) enteros consecutivos que son números compuestos.
Demostración. Vamos a considerar los siguientes \(n\) enteros consecutivos,
Lo anterior se cumple para cada valor que puede tomar \(k\), lo cual significa que cada uno de los enteros \((n+1)! + k\) es un número compuesto. Así, los \(n\) enteros consecutivos son \((n+1)! + 2, (n+1)! + 3, (n+1)! + 4, \ldots , (n+1)! + (n+1)\). \(\square\)
Ejemplo 21
Encuentra \(5\) enteros consecutivos que sean números compuestos.
Solución.
Usando el Teorema 4, tendríamos que el primer número de los \(5\) sería,
Ejemplo 22
Muestra que \(n^4 + 4\) es un número compuesto para toda \(n > 1\).
Solución.
Vamos a ver que \(n^4 + 4\) se puede factorizar.
Ahora veamos que
Definición de números primos y ejemplos#
Definición 7 (Número primo)
Un entero \(p>1\) es un número primo si sus únicos divisores positivos son: \(1\) y él mismo.
Notemos que por la definición de número primo, el entero \(1\) no es primo y tampoco es compuesto.
Los primeros 10 números primos son \(2,3,5,7,11,13,17,19,23,29\). Esto nos permite hacer una partición de los números enteros positivos en tres conjuntos disjuntos, el conjunto de los números primos \(\{2,3,5,7,\ldots\}\) el conjunto de los números compuestos \(\{4,6,8,9,\ldots\}\) y \(\{1\}\).
Ya con la definición de número primo podemos hacernos algunas preguntas muy naturales:
¿Hay alguna manera de representar a todos los números primos?
¿Por qué son importantes los números primos?
¿Cuántos números primos hay?
Primero, representar a todos los números primos de manera explícita es una tarea en la se sigue trabajando e investigando. Sin embargo, existen varias formas de describirlos, generar secuencias de números primos o caracterizarlos de forma matemática, en capítulos posteriores veremos algunas de estas formas.
Los números primos son esenciales en la teoría de números porque actúan como los bloques de construcción fundamentales de los números enteros, algo que veremos más adelante, es que cualquier número entero mayor que 1 puede ser descompuesto de manera única en factores primos. Son cruciales para la criptografía moderna, proporcionando seguridad en la comunicación digital mediante la factorización de grandes números. Además, su distribución en la recta numérica presenta patrones complejos que han motivado importantes desarrollos en teoría de números y matemáticas en general, y son el origen de problemas abiertos que siguen impulsando avances significativos en la ciencia matemática.
La última pregunta la vamos a responder con precisión a continuación, para ello veamos un lema previo.
Lema 1
Todo entero \(n\geq 2\) tiene por lo menos un factor primo.
Demostración. Procederemos por inducción fuerte.
Sea \(P(n)\) la proposición que afirma que para el entero positivo \(n \ge 2\) se cumple que: \(n\) tiene por lo menos un factor primo.
Base inductiva. Verifiquemos que \(P(2)\) es verdadera. Cuando \(n=2\) podemos notar que \(2=2\cdot 1\) entonces \(2\) tiene como factor primo a él mismo.
Hipótesis inductiva. Supongamos que \(P(n)\) es verdadera, para un entero positivo \(n \le k\), donde \(k\ge 2\).
Paso inductivo. Ahora vamos a probar que \(P(1),P(2),\ldots ,P(k)\) implican \(P(k+1)\).
Consideremos al entero \(k + 1\).
Si el entero \(k + 1\) es primo, entonces \(k + 1\) tiene como factor primo a él mismo.
Si el entero \(k + 1\) no es primo, entonces debe ser un número compuesto, por lo cual tiene un divisor propio \(d \le k\) tal que \(k + 1 = ad\). Por la hipótesis inductiva, ya que \(1 < d \le k\), entonces \(d\) tiene un factor primo, digamos \(p\) por lo cual \(d = bp\). Por lo tanto, tenemos que \(k + 1 = ad = abp\). Entonces \(k + 1\) tiene un factor primo.
Así, por inducción fuerte la proposición \(P(n)\) es verdadera para todo entero \(n\geq2\). \(\square\)
Ahora podemos probar que hay una infinidad de números primos. Este resultado, ideado por Euclides, es uno de los resultados elegantes de la teoría de números.
Teorema 5
Hay una infinidad de números primos.
Demostración. Procedamos por contradicción.
Supongamos que hay un número finito de números primos \(p_1 < p_2 <p_3 < \ldots < p_n\) y consideremos el entero
Si \(N\) es un número primo \(p\), entonces \(p>p_n\) lo cual contradice que \(p_n\) es el primo más grande.
Cuando \(N\) no es primo y \(N\ge 2\), entonces por el Lema 1 \(N\) es divisible por algún primo \(p_i\), donde \(1\le i \leq n\). Entonces tenemos que \(p_i \mid N\) y \(p_i\mid p_1\cdot p_2\cdot \ldots \cdot p_n\), lo que quiere decir que \(p_i \mid (N - p_1\cdot p_2\cdot \ldots \cdot p_n)\), lo cual es lo mismo que \(p_i \mid 1\), pero esto no es posible.
Por lo tanto nuestra suposición es falsa y nuestro primo elegido \(p_i\) no pertenece al conjunto finito de primos que teníamos inicialmente. Así, concluimos que hay una infinidad de números primos. \(\square\)
Veamos algunos ejercicios que están relacionados con número primos.
Ejemplo 23
Prueba que, para cualquier entero \(n > 1\) el número \(n^5+n^4+1\) no es un número primo.
Solución.
Veamos qué pasa si \(n = 2\). En este caso tendríamos que,
En general, notemos lo siguiente:
Notemos que \(n^2+n+1 > 1\) para cualquier valor de \(n>1\). Por otro lado, como \(n>1\) entonces
por lo cual \(n^3-n+1 = n(n^2 - 1) + 1 > 1\), para cualquier valor de \(n>1\).
Dado que reescribimos la expresión \(n^5+n^4+1\) como una factorización, esto implica que es un número compuesto para cualquier valor de \(n > 1\). \(\square\)
Ejemplo 24
Encuentra todos los enteros positivos \(n\) que cumplen que \(3n-4\), \(4n-5\) y \(5n-3\) son todos números primos.
Solución.
Notemos que cuando sumamos las tres expresiones obtenemos un número par.
Para que la suma de tres números sea par, hay dos posibles combinaciones de números pares e impares:
Los tres números sean pares.
Un número sea par y los otros impares.
Notemos que \(4n-5 = 4n-6+1 = 2(2n-3) +1\), lo cual nos dice que es un número impar, por lo cual descartamos la opción de que todos sean pares. Entonces sabemos que dos números deben ser impares y uno par.
Como \(4n-5\) es un número impar, entonces \(3n-4\) y \(5n-3\) son los que podrían ser pares. Luego podemos igualar a \(2\) las expresiones para encontrar el valor de \(n\) en cada caso,
Si \(n=1\), entonces el número \(3n-4 = 3\cdot 1-4 = -1,\) el cual no es primo.
Por lo tanto \(n=2\) y los números resultantes son \(2,3,7\). \(\square\)
¿Primo o compuesto?#
A lo largo de la historia, el interés en los números primos ha crecido, impulsando la creación de métodos para descubrir nuevos primos y verificar si un número es primo. Como vimos en el Teorema 5, Euclides demostró que existen infinitos números primos, un resultado que sigue siendo fundamental hoy en día. Durante siglos, los matemáticos han tratado de entender mejor la distribución de los primos y de encontrar nuevos métodos para identificar números primos grandes.
Con la llegada de la era moderna y la computación, se han desarrollado algoritmos sofisticados para encontrar números primos extremadamente grandes, conocidos como primos de Mersenne, que tienen la forma \(2^p−1\), donde \(p\) es un número primo de los cuales hablaremos más adelante.
El descubrimiento de números primos grandes y el desarrollo de algoritmos eficientes para la verificación de primos han sido esenciales en campos como la criptografía, donde los primos desempeñan un papel clave en la seguridad de los sistemas de encriptación modernos. A pesar de estos avances, la búsqueda de números primos y la comprensión de su comportamiento siguen siendo áreas activas de investigación matemática.
Observación 1
El número primo mas largo conocido hasta el día de hoy que se hicieron estas notas es un número con 24,862,048 cifras.
Durante el paso de los tiempos se han encontrado peculiaridades sobre los números primos. Veamos una que nos da una clasificación de estos números.
Si un entero \(n\) es dividido entre \(4\), podríamos expresarlo de la forma \(n = 4q + r\), en donde \(r\) podría tomar los valores de \(0,1,2\) o \(3\). Por lo tanto tendríamos que todo entero positivo se puede expresar de la forma
Notemos que \(4k\) no es un número primo, ya que para cualquier valor de \(k\), \(4k\) es divisible entre \(4\).
Por otro lado, \(4k+2\) es primo cuando \(k = 0\), pero para cualquier otro valor de \(k\) no es un número primo, ya que \(2|(4k+2)\).
Veamos qué pasa con las expresiones \(4k+1\) y \(4k+3\) para algunos valores de \(k\).
Con lo anterior podemos decir que todo número primo impar es de la forma \(4k+1\) o \(4k+3\), en donde \(k\) es un entero positivo. Podemos observar que no todos los números en ambas secuencias son primos, pero lo que podemos demostrar es que en cualquiera de las dos secuencias, hay una infinidad de primos.
Antes de pasar al siguiente teorema notemos que la secuencia \(4k+3\) es la misma que la secuencia \(4k-1\) ya que \(4k + 3 = 4k + 4 - 1 = 4(k+1) - 1 = 4q - 1\), donde \(q = k+1\).
Teorema 6
Hay una infinidad de números primos de la forma \(4q+3\).
Demostración. Procedamos por contradicción. Supongamos que hay una cantidad finita de primos de la forma \(4q+3\), digamos \(p_1, p_2, p_3, \ldots , p_k\).
Sea
Si \(m\) es primo, entonces \(m > p_k\) lo cual contradice que \(p_k\) sea el primo más grande de la forma \(4k+3\).
Cuando \(m\) es un número compuesto, ya que \(m\) es un número impar, también lo es cada primo \(p\) que divide a \(m\), por lo que \(p\) tiene la forma \(4q+1\) o \(4q-1\) para algún entero \(q\).
Notemos que \((4s+1)(4t+1) = 4(4st + s+t) + 1\), es decir que el producto de dos números de la forma \(4k+1\), sigue siendo de la forma \(4k+1\), luego por inducción podríamos probar que el producto de cualquier cantidad de números de la forma \(4k+1\), sigue siendo de la forma \(4k+1\).
Entonces, si cada uno de los \(p\) que divide a \(m\) es de la forma \(4q+1\), resulta en que \(m\) también debería tener esa forma, lo cual es falso.
Por lo tanto, \(m\) debe ser divisible por al menos un primo \(p\) de la forma \(4q - 1\). Según nuestra suposición, como los primos de la forma \(4q-1\) son finitos, tendríamos que \(p = p_i\) para algún \(1 \le i \le k\), por lo que \(p|(4p_1p_2\cdot \ldots \cdot p_k - m) = 1\), lo cual es imposible. \(\square\)
Veamos el siguiente resultado, en donde se demuestra que no existe un polinomio que produzca primos para cada valor que se sustituya.
Proposición 6
No existe ningún polinomio \(f(n)\) con coeficientes enteros que produzca primos para todos los números enteros n.
Demostración. Procedamos por contradicción.
Supongamos que existe tal polinomio \(f(n) = a_kn^k + a_{k-1}n^{k-1} + a_{k-2}n^{k-2} + \ldots + a_1n + a_0\), en donde \(a_k \neq 0\). Sea \(b\) algún entero. Como \(f(n)\) siempre es primo, \(f(b)\) también debe de ser un primo, es decir que
Sea \(t\) un entero arbitrario, entonces
en donde \(g(t)\) es un polinomio con coeficientes enteros. Así, tendríamos que
Por lo anterior tenemos que \(p|f(b+tp)\). Pero todo valor de \(f\) es un primo, entonces \(f(b + tp)\) debe de ser un primo para todo \(t\) entero y por lo tanto \(f(b+tp) = p\). Así, \(f(b) = p = f(b + tp)\). Esto implica que \(f\) toma el mismo valor una infinidad de veces, ya que \(t\) es un entero arbitrario.
Pero \(f(n)\) es un polinomio de grado \(k\), entonces no podría tomar el mismo valor mas de \(k\) veces, lo cual genera la contradicción.
Por lo tanto, no existe un polinomio con coeficientes enteros que produzca sólo primos. \(\square\)
Por último, veamos una proposición que nos ayuda a saber si un número es primo o compuesto.
Proposición 7
Si \(n\) es un número compuesto, entonces \(n\) tiene un factor primo \(p \le \sqrt{n}\).
Demostración. Como \(n\) es un número compuesto por definición sabemos que tiene algún divisor propio, lo que significa que existen enteros positivos \(a\) y \(b\) tales que \(n = ab\), en donde \(1 < a < n\) y \(1 < b < n\).
En caso de que \(a = b\), sin perdida de generalidad tendremos que \(n = a^2\), entonces \(\sqrt{n} = a\), luego por el Lema 1 \(a\) debe tener un factor primo \(p\) tal que \(p|a\) y así, \(p\le a = \sqrt{n}\). Por lo tanto, \(p\) es un factor de \(a^2 = n\) y podemos concluir que \(n\) tiene un factor primo \(\le \sqrt{n}\).
Si \(a\neq b\), vamos a ver que \(a \le \sqrt{n}\) o \(b \le \sqrt{n}\). Para ello hagamos lo siguiente.
Supongamos que \(a>\sqrt{n}\) y \(b>\sqrt{n}\). Entonces tendríamos que \(n = ab > \sqrt{n} \cdot \sqrt{n} = n\), lo cual es imposible.
Ahora, tenemos los siguientes dos casos:
Si \(a \le \sqrt{n}\), por el Lema 1 tendremos que \(a\) debe tener un factor primo, digamos \(q\), entonces \(q|a\) y así \(q\le a\le \sqrt{n}\).
Si \(b \le \sqrt{n}\), nuevamente por el Lema 1 tendremos que \(b\) debe tener un factor primo, digamos \(p\), entonces \(p|b\) y así \(p\le b \le \sqrt{n}\).
En cualquiera de los dos casos tendremos que \(p\) o \(q\) es un factor de \(ab = n\) y podemos concluir que \(n\) tiene un factor primo \(\le \sqrt{n}\). \(\square\)
Ejemplo 25
Utilicemos la Proposición 7 para ver que el número 539 tiene como factor un número primo \(p \le \sqrt{n}\).
Solución.
Primero calculemos los siguiente:
Si bien, la Proposición 7 anterior nos ayuda a saber si un número es compuesto, también es una herramienta útil como prueba de primalidad, es decir que si el entero \(n\) no tiene factores primos menores que \(\sqrt{n}\) entonces \(n\) es un número primo.
En casos pequeños funciona bien como prueba de primalidad, pero en la práctica no es eficiente para números grandes, por lo que se recurre a otros métodos más sofisticados para números de gran magnitud.
Código para comprobar si un número es primo o compuesto.#
El siguiente código nos dirá si un número entero es primo o compuesto, además, si es compuesto nos dirá uno de sus divisores.
def primo_vs_compuesto(n):
i = 0
factores = []
for divisor in range(2,int(n**0.5)+1):
if n % divisor == 0:
factores.append(divisor)
i += 1
if i == 0:
print("El número ", n," es primo!")
else:
print("El número", n,"es compuesto \nsus divisores menores que",n**0.5 ,"son: ",factores)
primo_vs_compuesto(51)
El número 51 es compuesto
sus divisores menores que 7.14142842854285 son: [3]
primo_vs_compuesto(2574)
El número 2574 es compuesto
sus divisores menores que 50.73460357586329 son: [2, 3, 6, 9, 11, 13, 18, 22, 26, 33, 39]
primo_vs_compuesto(1997)
El número 1997 es primo!
primo_vs_compuesto(10001)
El número 10001 es compuesto
sus divisores menores que 100.00499987500625 son: [73]
primo_vs_compuesto(237581)
El número 237581 es primo!
Explicación del código#
En este capítulo introducimos una estructura de datos que permite almacenar una colección ordenada de elementos, las listas. Cada elemento en una lista puede ser de cualquier tipo de dato, como números, cadenas, booleanos, objetos, e incluso otras listas. Las listas son mutables, lo que significa que podemos modificar, agregar o eliminar elementos después de que la lista ha sido creada. Para crear una lista en Python, simplemente encerramos los elementos entre corchetes [ ] y los separamos con comas.
Por ejemplo, podemos crear la lista que contiene los números del \(1\) al \(7\), o incluso crear una lista vacía sin poner elementos dentro.
lista = [1,2,3,4,5,6,7]
lista_vacia = []
Las listas en Python admiten diversas operaciones y métodos, en este caso utilizamos el método .append(), el cual sirve para añadir elementos al final de una lista. Dentro del método .append() agregamos el elemento que queremos añadir a nuestra lista. Este método nos sirve para construir listas dinamicamente agregando elementos en el proceso de ejecución del programa. Asignando la lista a una variable, la sintaxis sería
lista.append(elemento_a_agregar)
Usamos una forma abreviada de escribir que a una variable \(i\) se le sume una unidad. Esta construcción es comúnmente utilizada en bucles para actualizar el valor de una variable de control o en cualquier otro lugar donde sea necesario incrementar el valor de una variable en un paso constante.
i = i + 1
i += 1
Usamos una nueva operación en python la potencia, la cual se representa con el símbolo ** doble asterisco. Básicamente tenemos que poner una base y un exponente, los exponentes pueden ser números enteros o flotantes. La sintaxis sería la siguiente.
base**exp
b = 3**5
El resultado de la variable «b» sería igual a \(243\).
Ahora vamos a explicar cómo funciona el código.
def primo_vs_compuesto(n):
i = 0
factores = []
for divisor in range(2,int(n**0.5)+1):
if n % divisor == 0:
factores.append(divisor)
i += 1
if i == 0:
print("El número ", n," es primo!")
else:
print("El número", n,"es compuesto \nsus divisores menores que",n**0.5 ,"son: ",factores)
Creamos una función llamada «primos_vs_compuestos» la cual recibe como argumento un número entero. Creamos las variables «i» con un valor inicial de cero y la variable «factores» la cual es una lista vacía.
def primo_vs_compuesto(n):
i = 0
factores = []
Comenzamos un ciclo
forel cual recorre lo valores en el rango de \(2\) a \(\sqrt{n}\), con un condicionalifverificamos si los valores que va tomando el ciclofordividen a la variable «n». De ser cierta la condición se reproduce el código dentro del condicional, se agrega el divisor a la lista «factores» y se incrementa en una unidad la variable «i». Cuando termine el cicloforsi el número es compuesto, obtendremos una lista con los factores menores que \(\sqrt{n}\) y en la variable «i» la cantidad de divisores. Si el número es primo, la lista seguirá estando vacía y la variable «i» seguirá teniendo un valor de cero.
for divisor in range(2,int(n**0.5)+1):
if n % divisor == 0:
factores.append(divisor)
i += 1
Finalmente utilizamos los condicionales
ifyelse. El condicionalifrevisa el valor de la variable «i». Si el valor de «i» es cero, entonces se reproduce el código dentro del condicionalif, el cual nos imprime en pantalla que el número es primo.
Si el valor de «i» es diferente de cero se reproduce el código del condicionalelse, el cual imprime en pantalla que el número es compuesto, y nos dice cuales son los factores menores que \(\sqrt{n}\).
if i == 0:
print("El número ", n," es primo!")
else:
print("El número", n,"es compuesto \nsus divisores menores que",n**0.5 ,"son: ",factores)
Ejercicios de práctica#
Demuestra que si \(n\) es un número compuesto, entonces \(2^n - 1\) es un número compuesto.
Sean \(b\ge 2\) y \(n\ge 1\). Demuestra que \(b^{3n} \pm 1\) es compuesto.
Muestra que \(n^4 + n^2 + 1\) es un número compuesto si \(n > 1\).
Demuestra que \(2\) y \(3\) son los únicos enteros consecutivos que son primos.
Encuentra todos los primos \(p\) para los que se cumple lo siguiente. Si \(p\) y \(p^2 + 8\) son primos, entonces \(p^3 + 4\) también es primo. Pista: Considera que al dividir un entero \(n\) entre \(3\) puede expresarse de la forma \(3n, 3n+1\) o \(3n-1\).
Encuentra todos los primos \(p\) tales que los seis números \(p, p+2, p+6, p+8, p+12\) y \(p+14\) son primos. Pista: Considera que al dividir un entero \(n\) entre \(5\) puede expresarse de la forma \(n = 5q+r\), donde \(r = 0,1,2,3,4\).