2.1: El Tamiz de Eratóstenes

Última actualización
Guardar como PDF

Page ID: 114859

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Un primo es un entero mayor que 1 que solo es divisible por 1 y por sí mismo. Los enteros 2, 3, 5, 7, 11 son números enteros primos. Tenga en cuenta que cualquier entero mayor que 1 que no sea primo se dice que es un número compuesto.

El Tamiz de Eratóstenes

El tamiz de Eratóstenes es un método antiguo para encontrar números primos hasta un entero especificado. Este método fue inventado por el antiguo matemático griego Eratóstenes. Hay varios otros métodos utilizados para determinar si un número es primo o compuesto. Primero presentamos un lema que será necesario en la prueba de varios teoremas.

Cada entero mayor que uno tiene un divisor primo.

Presentamos la prueba de este Lema por contradicción. Supongamos que hay un entero mayor que uno que no tiene divisores primos. Dado que el conjunto de enteros con elementos mayores que uno sin divisores primos no está vacío, entonces por el principio de ordenamiento de pozos hay un entero menos positivo\(n\) mayor que uno que no tiene divisores primos. Así\(n\) es compuesto ya que\(n\) divide\(n\). De ahí\[n=ab \mbox{with} \ \ 1<a<n \mbox{and} \ \ 1<b<n.\] Observe que\(a<n\) y como resultado ya que\(n\) es mínimo,\(a\) debe tener un divisor primo el cual también será un divisor de\(n\).

Si\(n\) es un entero compuesto, entonces n tiene un factor primo que no excede\(\sqrt{n}\).

Ya que\(n\) es compuesto, entonces\(n=ab\), donde\(a\) y\(b\) son enteros con\(1<a\leq b<n\). Supongamos ahora que\(a>\sqrt{n}\), entonces

\[\sqrt{n}<a \leq b\]

y como resultado

\[ab>\sqrt{n}\sqrt{n}=n.\]

Por lo tanto\(a\leq \sqrt{n}\). También, por Lema 3,\(a\) debe tener un divisor primo\(a_1\) que también es un divisor primo de\(n\) y por lo tanto este divisor es menor que\(a_1 \leq a\leq \sqrt{n}\).

Presentamos ahora el algoritmo del Tamiz de Eratóstenes que se utiliza para determinar números primos hasta un entero dado.

El Algoritmo del Tamiz de Eratóstenes

Escribe una lista de números desde 2 hasta el número más grande que\(n\) quieras probar. Tenga en cuenta que cada entero compuesto menor que\(n\) debe tener un factor primo menor que\(\sqrt{n}\). De ahí que necesites golpear los múltiplos de los primos que son menores que\(\sqrt{n}\)
Tachar todos los múltiplos de 2 mayores que 2 de la lista. El primer número restante en la lista es un número primo.
Taca todos los múltiplos de este número de la lista.
Repita los pasos anteriores hasta que no se encuentren más múltiplos de los números enteros primos que son menores que\(\sqrt{n}\)

Ejercicios

Usa el Tamiz de Eratóstenes para encontrar todos los primos menores a 100.
Usa el Tamiz de Eratóstenes para encontrar todos los primos menores a 200.
Mostrar que ningún entero de la forma\(a^3+1\) es primo excepto para\(2=1^3+1\).
Demuestre que si\(2^n-1\) es primo, entonces\(n\) es primo.
Pista: Usa la identidad\((a^{kl}-1)=(a^{k}-1)(a^{k(l-1)}+a^{k(l-2)}+...+a^k+1)\).

Colaboradores y Atribuciones

Template:ContribRaji