Divisibilidad y factorización · Definición

Infinitud de los primos

teoría de números elementaldivisibilidad y factorización

Antes de empezar necesitas conocer

Euclides mostró que ninguna lista finita de primos puede contener a todos. La idea central es construir un número que escape a cualquier lista dada.

Definición

La infinitud de los primos es el teorema de Euclides que afirma que el conjunto de los números primos es infinito: dada cualquier lista finita de primos \(p_1,\dots,p_n\), existe un primo fuera de ella.

\[p\mid p_1p_2\cdots p_n+1\ \Longrightarrow\ p\neq p_i\ \text{para todo } i\]

Si el conjunto de primos fuera finito, podríamos listarlo como \(p_1, p_2, \dots, p_n\). Entonces el número \(N = p_1 p_2 \cdots p_n + 1\) es mayor que 1 y, por el teorema fundamental de la aritmética, tiene al menos un divisor primo.

Tomemos la lista 2, 3, 5, 7, 11, 13 y formemos \(N = 30031\). Ningún primo de la lista divide a \(N\), porque cada uno deja resto 1 al dividirlo. Por tanto \(N\) tiene un primo fuera de la lista, lo cual contradice la hipótesis.

Un error típico es afirmar que \(N = p_1 p_2 \cdots p_n + 1\) es siempre primo. Por ejemplo, \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509\), así que el argumento no construye primos, solo garantiza uno nuevo.

Para pensar

¿Por qué \(N = p_1\cdots p_n + 1\) no siempre es primo?

Porque \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59\cdot 509\), así que puede ser compuesto.

Ejercicios 10

  1. ¿Cuál de estas afirmaciones resume el teorema de Euclides sobre los primos?
  2. Enuncia la idea de la demostración de Euclides por reducción al absurdo.
  3. ¿Qué número se construye en la demostración de Euclides a partir de los primos 2, 3 y 5?
  4. Según el argumento de Euclides, ¿qué propiedad tiene el número \(N = p_1 p_2 \cdots p_n + 1\) respecto a los primos de la lista?
  5. ¿Cuál de estas afirmaciones sobre la lista 2, 3, 5, 7 es correcta?
  6. Calcula \(N = 2\cdot 3\cdot 5\cdot 7\cdot 11 + 1\) y determina su menor divisor primo.
  7. ¿Cuál es el resto de \(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1\) al dividirlo entre \(7\)?
  8. Si \(p_1,\dots,p_n\) son primos y \(N = p_1\cdots p_n + 1\), ¿cuál afirmación es cierta sobre \(N\)?
  9. Usando la lista 2, 3, 5, 7, 11, ¿cuál es el número construido y un primo que no pertenece a la lista?
  10. Supón que \(p_1,\dots,p_n\) son todos los primos. Explica por qué \(N = p_1\cdots p_n + 1\) produce una contradicción usando el teorema fundamental de la aritmética.

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 3
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1