¿Es uno un número primo? números primos

Enumeración de divisores. Por definición, número norte es primo sólo si no es divisible por 2 y otros números enteros excepto 1 y él mismo. La fórmula anterior elimina pasos innecesarios y ahorra tiempo: por ejemplo, después de comprobar si un número es divisible por 3, no es necesario comprobar si es divisible por 9.

• La función Floor(x) redondea x al entero más cercano que sea menor o igual a x.

Aprende sobre aritmética modular. La operación "x mod y" (mod es una abreviatura de la palabra latina "módulo", es decir, "módulo") significa "dividir x entre y y encontrar el resto". En otras palabras, en aritmética modular, al alcanzar un cierto valor, que se llama módulo, los números “vuelven” a cero nuevamente. Por ejemplo, un reloj marca la hora con un módulo de 12: marca las 10, las 11 y las 12 y luego vuelve a 1.

• Muchas calculadoras tienen una tecla mod. El final de esta sección muestra cómo calcular manualmente esta función para números grandes.

Conozca los peligros del pequeño teorema de Fermat. Todos los números para los cuales no se cumplen las condiciones de la prueba son compuestos, pero los números restantes son solo probablemente se clasifican como simples. Si desea evitar resultados incorrectos, busque norte en la lista de "números de Carmichael" (números compuestos que satisfacen esta prueba) y "números pseudoprimos de Fermat" (estos números cumplen las condiciones de la prueba sólo para algunos valores a).

Si es conveniente, utilice la prueba de Miller-Rabin. A pesar de este método bastante engorroso cuando se calcula manualmente, a menudo se usa en programas de computador. Proporciona una velocidad aceptable y produce menos errores que el método de Fermat. Un número compuesto no será aceptado como número primo si se realizan cálculos para más de ¼ de los valores. a. Si seleccionas al azar diferentes significados a y para todos ellos la prueba dará un resultado positivo, podemos suponer con un grado bastante alto de confianza que norte es un número primo.

Para números grandes, utilice la aritmética modular. Si no tiene una calculadora con mod a mano, o su calculadora no está diseñada para manejar números tan grandes, use las propiedades de las potencias y la aritmética modular para facilitar los cálculos. A continuación se muestra un ejemplo para 3 50 (\displaystyle 3^(50)) mod 50:

• Reescribe la expresión en una forma más conveniente: mod 50. Al realizar cálculos manuales, es posible que sean necesarias más simplificaciones.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Aquí tomamos en cuenta la propiedad de la multiplicación modular.
• 3 25 (\displaystyle 3^(25)) mod 50 = 43.
• (3 25 (\displaystyle (3^(25)) modelo 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) modelo 50.
• = 1849 (\displaystyle =1849) modelo 50.
• = 49 (\displaystyle =49).

número primo es un número natural (entero positivo) que es divisible sin resto por sólo dos números naturales: por y por sí mismo. En otras palabras, un número primo tiene exactamente dos divisores naturales: y el número mismo.

Por definición, el conjunto de todos los divisores de un número primo es de dos elementos, es decir representa un conjunto.

El conjunto de todos los números primos se denota con el símbolo. Así, debido a la definición del conjunto de los números primos, podemos escribir: .

La secuencia de números primos se ve así:

Teorema fundamental de la aritmética

Teorema fundamental de la aritmética afirma que todo número natural mayor que uno se puede representar como producto de números primos, y la única forma hasta el orden de los factores. Por tanto, los números primos son los "bloques de construcción" elementales del conjunto de los números naturales.

Título de expansión de números naturales="Representado por QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} canónico:

donde es un número primo y . Por ejemplo, la expansión canónica de un número natural se ve así: .

La representación de un número natural como producto de números primos también se llama factorización de un número.

Propiedades de los números primos

Tamiz de Eratóstenes

Uno de los algoritmos más famosos para buscar y reconocer números primos es tamiz de Eratóstenes. Así, este algoritmo lleva el nombre del matemático griego Eratóstenes de Cirene, a quien se considera el autor del algoritmo.

Para encontrar todos los números primos menores que un número determinado, siguiendo el método de Eratóstenes, sigue estos pasos:

Paso 1. Escribe todos los números naturales del dos al , es decir. .
Paso 2. Asigne a la variable el valor, es decir, el valor igual al número primo más pequeño.
Paso 3. Tacha en la lista todos los números desde hasta que sean múltiplos de , es decir, los números: .
Etapa 4. Encuentre el primer número no cruzado en la lista mayor que y asigne el valor de este número a una variable.
Paso 5. Repita los pasos 3 y 4 hasta alcanzar el número.

El proceso de aplicación del algoritmo se verá así:

Todos los números no cruzados restantes en la lista al final del proceso de aplicación del algoritmo serán el conjunto de números primos desde hasta .

Conjetura de Goldbach

Portada del libro “El tío Petros y la hipótesis de Goldbach”

A pesar de que los matemáticos han estudiado los números primos durante bastante tiempo, muchos problemas relacionados siguen sin resolverse en la actualidad. Uno de los problemas sin resolver más famosos es La hipótesis de Goldbach, que queda formulado de la siguiente manera:

• ¿Es cierto que todo número par mayor que dos puede representarse como la suma de dos números primos (hipótesis binaria de Goldbach)?
• ¿Es cierto que todo número impar mayor que 5 puede representarse como la suma de tres números primos (hipótesis ternaria de Goldbach)?

Cabe decir que la hipótesis ternaria de Goldbach es un caso especial de la hipótesis binaria de Goldbach o, como dicen los matemáticos, la hipótesis ternaria de Goldbach es más débil que la hipótesis binaria de Goldbach.

La conjetura de Goldbach se hizo ampliamente conocida fuera de la comunidad matemática en el año 2000 gracias a un truco de marketing promocional de las editoriales Bloomsbury USA (EE.UU.) y Faber and Faber (Reino Unido). Estas editoriales, después de publicar el libro "El tío Petros y la conjetura de Goldbach", prometieron pagar un premio de 1 millón de dólares a quien demuestre la hipótesis de Goldbach en un plazo de dos años a partir de la fecha de publicación del libro. A veces, el mencionado premio de las editoriales se confunde con premios por resolver los Problemas del Premio del Milenio. No nos equivoquemos, la hipótesis de Goldbach no está clasificada por el Instituto Clay como un “desafío del milenio”, aunque está estrechamente relacionada con hipótesis de riemann- uno de los “desafíos del milenio”.

El libro “Números primos. Largo camino hacia el infinito"

Portada del libro “El Mundo de las Matemáticas. Números primos. Largo camino hacia el infinito"

Además, recomiendo leer un fascinante libro de divulgación científica, cuya anotación dice: “La búsqueda de números primos es uno de los problemas más paradójicos de las matemáticas. Los científicos llevan varios milenios intentando resolverlo, pero, a medida que crecen las nuevas versiones e hipótesis, este misterio sigue sin resolverse. La aparición de los números primos no está sujeta a ningún sistema: aparecen espontáneamente en la serie de números naturales, ignorando todos los intentos de los matemáticos por identificar patrones en su secuencia. Este libro permitirá al lector rastrear la evolución de los conceptos científicos desde la antigüedad hasta nuestros días e introducir las teorías más interesantes sobre la búsqueda de números primos”.

Además, citaré el comienzo del segundo capítulo de este libro: “Los números primos son uno de los temas importantes que nos remontan a los inicios mismos de las matemáticas y luego, por un camino de complejidad creciente, nos llevan a la vanguardia. ciencia moderna. Por tanto, sería muy útil rastrear la fascinante y compleja historia de la teoría de los números primos: exactamente cómo se desarrolló, exactamente cómo se recogieron los hechos y verdades que ahora son generalmente aceptados. En este capítulo veremos cómo generaciones de matemáticos estudiaron cuidadosamente los números naturales en busca de una regla que predijera la aparición de los números primos, regla que se volvió cada vez más difícil de alcanzar a medida que avanzaba la búsqueda. También veremos en detalle el contexto histórico: en qué condiciones trabajaron los matemáticos y en qué medida su trabajo implicaba prácticas místicas y semirreligiosas, que no se parecen en nada a metodos cientificos, utilizado hoy en día. Sin embargo, poco a poco y con dificultad, se preparó el terreno para nuevas ideas que inspiraron a Fermat y Euler en los siglos XVII y XVIII”.

M. Gardner describe detalladamente cómo se hizo esta observación en “Mathematical Leisure” (M., “Mir”, 1972). Aquí está esta pieza (p. 413417):

Dependiendo de la disposición de los números enteros, los números primos pueden formar un patrón u otro. Érase una vez, el matemático Stanislaw M. Ulam tuvo que asistir a un informe muy largo y, según sus palabras, muy aburrido. Para divertirse de alguna manera, dibujó líneas verticales y horizontales en una hoja de papel y quiso empezar a componer. estudios de ajedrez, pero luego cambió de opinión y comenzó a numerar las intersecciones, poniendo 1 en el centro y moviéndose en una espiral en sentido antihorario. Sin pensarlo dos veces, rodeó todos los números primos. Pronto, para su sorpresa, los círculos comenzaron a alinearse en líneas rectas con una tenacidad asombrosa. En la Fig. 203 muestra cómo era una espiral con los primeros cien números (del 1 al 100). [ Esta es una versión de dos vueltas de la Figura 1 anterior, por lo que no la incluiré aquí. mi E.G.A.] Por conveniencia, los números están escritos en celdas y no se encuentran en la intersección de líneas.

Cerca del centro, todavía se podría esperar la alineación de los números primos a lo largo de líneas rectas, ya que la densidad de los números primos es inicialmente grande y todos, excepto el número 2, son impares. Si las casillas de un tablero de ajedrez están numeradas en espiral, todos los números impares terminarán en casillas del mismo color. Tomando 17 peones (correspondientes a 17 números primos que no excedan el número 64) y colocándolos al azar en cuadrados del mismo color, encontrarás que los peones están alineados a lo largo de líneas diagonales. Sin embargo, no había razón para esperar que en la región de los números grandes, donde la densidad de los números primos es mucho menor, también se alinearan en línea recta. Ulam se interesó en cómo sería su espiral si se extendiera a varios miles de números primos.

En el departamento de informática del Laboratorio de Los Álamos, donde trabajaba Ulam, había una cinta magnética en la que estaban grabados 90 millones de números primos. Ulam, junto con Myron L. Stein y Mark B. Wells, compilaron un programa para la computadora MANIAC que hizo posible trazar números enteros consecutivos del 1 al 65.000 en una espiral. Se muestra el patrón resultante (a veces llamado "el mantel de Ulam"). en la Fig. 204. [ Y esta es una versión ampliada de la Figura 2 anterior, así que la presento. mi E.G.A.] Tenga en cuenta que incluso en el borde de la imagen, los números primos siguen encajando obedientemente en las líneas rectas.

Lo primero que llama la atención son los grupos de números primos en las diagonales, pero también es bastante evidente otra tendencia de los números primos a alinearse a lo largo de líneas verticales y horizontales, en las que todas las celdas libres de números primos están ocupadas por números impares. perceptible. Los números primos que caen en líneas rectas que se extienden más allá de un segmento que contiene números consecutivos que se encuentran en alguna vuelta de la espiral pueden considerarse los valores de ciertas expresiones cuadráticas que comienzan con el término 4. X². Por ejemplo, la secuencia de números primos 5, 19, 41, 71, ubicada en una de las diagonales de la Fig. 204, estos son los valores que toma el trinomio cuadrático 4 X² + 10 X+ 5 en X, igual a 0, 1, 2 y 3. De la Fig. 204 está claro que las expresiones cuadráticas que toman valores simples, hay "pobres" (que dan pocos números primos) y "ricos" y que en las líneas de "ricos" hay "dispersiones" enteras de números primos.

Al comenzar la espiral no desde 1, sino desde algún otro número, obtenemos otras expresiones cuadráticas para números primos alineados en línea recta. Considere una espiral que comienza con el número 17 (Fig. 205, izquierda). Los números a lo largo de la diagonal principal que va del "noreste" al "suroeste" se generan mediante el trinomio cuadrático 4 X² + 2 X+ 17. Sustituyendo valores positivos X, obtenemos la mitad inferior de la diagonal sustituyendo la mitad superior por valores negativos. Si consideramos toda la diagonal y reorganizamos los números primos en orden ascendente, resulta (y esto es una agradable sorpresa) que todos los números se describen mediante una fórmula más simple. X² + X+ 17. Esta es una de las muchas fórmulas "generadoras" de números primos descubiertas en el siglo XVIII por el gran matemático Leonhard Euler. En X, tomando valores del 0 al 15, da sólo números primos. Por lo tanto, si continuamos la diagonal hasta llenar un cuadrado de 16 x 1 6, vemos que toda la diagonal está llena de números primos.

El trinomio cuadrático más famoso de Euler, que produce números primos, X² + X+ 41, resulta si comienzas la espiral con el número 41 (Fig. 205, derecha). ¡Este trinomio te permite obtener 40 números primos consecutivos que llenan toda la diagonal de un cuadrado de 40x4 0! Se sabe desde hace tiempo que de los 2398 primeros valores que toma este trinomio, exactamente la mitad son simples. Después de revisar todos los valores del famoso trinomio que no superaban los 10.000.000, Ulam, Stein y Wells descubrieron que la proporción de números primos entre ellos era 0,475... . A los matemáticos les gustaría mucho descubrir una fórmula que les permita obtener todos en general X varios números primos, pero hasta ahora no se ha encontrado tal fórmula. Quizás no exista.

33 32 31 30 29 34 21 20 19 28 35 22 17 18 27 36 23 24 25 26 37 38 39 40 41		57 56 55 54 53 58 45 44 43 52 59 46 41 42 51 60 47 48 49 50 61 62 63 64 65
Arroz. 205. Diagonales llenas de números primos generados por trinomios cuadráticos X² + X+ 17 (izquierda) y X² + X+ 41 (derecha).

La espiral de Ulam planteó muchas preguntas nuevas sobre patrones y aleatoriedad en la distribución de números primos. ¿Hay rectas que contienen infinitos números primos? ¿Cuál es la densidad máxima de distribución de números primos a lo largo de líneas? ¿Difieren significativamente las distribuciones de densidad de los números primos en los cuadrantes del mantel de Ulam, si suponemos que continúa indefinidamente? La Espiral de Ulam es divertida, pero debe tomarse en serio.

El artículo analiza los conceptos de números primos y compuestos. Las definiciones de dichos números se dan con ejemplos. Presentamos una prueba de que el número de números primos es ilimitado y lo registraremos en la tabla de números primos utilizando el método de Eratóstenes. Se dará evidencia para determinar si un número es primo o compuesto.

Yandex.RTB R-A-339285-1

Números primos y compuestos: definiciones y ejemplos

Los números primos y compuestos se clasifican como números enteros positivos. Deben ser mayores que uno. Los divisores también se dividen en simples y compuestos. Para comprender el concepto de números compuestos, primero debes estudiar los conceptos de divisores y múltiplos.

Definición 1

Los números primos son números enteros mayores que uno y que tienen dos divisores positivos, es decir, ellos mismos y 1.

Definición 2

Los números compuestos son números enteros mayores que uno y que tienen al menos tres divisores positivos.

Uno no es un número primo ni compuesto. Tiene un solo divisor positivo, por lo que es diferente de todos los demás números positivos. Todos los números enteros positivos se llaman números naturales, es decir, se utilizan para contar.

Definición 3

números primos Son números naturales que sólo tienen dos divisores positivos.

Definición 4

Número compuesto es un número natural que tiene más de dos divisores positivos.

Cualquier número mayor que 1 es primo o compuesto. De la propiedad de divisibilidad tenemos que el 1 y el número a siempre serán divisores de cualquier número a, es decir, será divisible por sí mismo y por 1. Demos una definición de números enteros.

Definición 5

Los números naturales que no son primos se llaman números compuestos.

Números primos: 2, 3, 11, 17, 131, 523. Sólo son divisibles por sí mismos y por 1. Números compuestos: 6, 63, 121, 6697. Es decir, el número 6 se puede descomponer en 2 y 3, y el 63 en 1, 3, 7, 9, 21, 63 y el 121 en 11, 11, es decir, sus divisores serán 1, 11, 121. El número 6697 se descompone en 37 y 181. Tenga en cuenta que los conceptos de números primos y números coprimos son conceptos diferentes.

Para facilitar el uso de números primos, es necesario utilizar una tabla:

Una tabla para todos los números naturales existentes no es realista, ya que hay un número infinito de ellos. Cuando los números alcanzan tamaños de 10000 o 1000000000, entonces deberías pensar en usar el Tamiz de Eratóstenes.

Consideremos el teorema que explica el último enunciado.

Teorema 1

El divisor positivo más pequeño distinto de 1 de un número natural mayor que uno es un número primo.

Evidencia 1

Supongamos que a es un número natural mayor que 1, b es el divisor no uno más pequeño de a. Es necesario demostrar que b es un número primo mediante el método de la contradicción.

Supongamos que b es un número compuesto. De aquí tenemos que hay un divisor para b, que es diferente tanto de 1 como de b. Tal divisor se denota como b 1. Es necesario que la condición 1< b 1 < b Se completó.

De la condición se desprende claramente que a se divide por b, b se divide por b 1, lo que significa que el concepto de divisibilidad se expresa de la siguiente manera: a = b q y b = b 1 · q 1 , de donde a = b 1 · (q 1 · q) , donde q y q 1 son números enteros. Según la regla de la multiplicación de números enteros, tenemos que el producto de números enteros es un número entero con igualdad de la forma a = b 1 · (q 1 · q). Se puede observar que b 1 es el divisor del número a. Desigualdad 1< b 1 < b No corresponde, porque encontramos que b es el divisor positivo más pequeño y distinto de 1 de a.

Teorema 2

Hay una cantidad infinita de números primos.

Evidencia 2

Presumiblemente tomamos un número finito de números naturales n y los denotamos como p 1, p 2,…, p n. Consideremos la opción de encontrar un número primo diferente a los indicados.

Consideremos el número p, que es igual a p 1, p 2, ..., p n + 1. No es igual a cada uno de los números correspondientes a números primos de la forma p 1, p 2, ..., p n. El número p es primo. Entonces el teorema se considera probado. Si es compuesto, entonces debes tomar la notación p n + 1 y demostrar que el divisor no coincide con ninguno de p 1, p 2, ..., p n.

Si esto no fuera así, entonces, con base en la propiedad de divisibilidad del producto p 1, p 2, ..., p n , encontramos que sería divisible por pn + 1. Tenga en cuenta que la expresión p n + 1 dividir el número p es igual a la suma p 1, p 2, ..., p n + 1. Obtenemos que la expresión p n + 1 El segundo término de esta suma, que es igual a 1, debe dividirse, pero esto es imposible.

Se puede ver que cualquier número primo se puede encontrar entre cualquier número de números primos dados. De ello se deduce que hay infinitos números primos.

Como hay muchos números primos, las tablas se limitan a los números 100, 1000, 10000, etc.

Al compilar una tabla de números primos, se debe tener en cuenta que dicha tarea requiere una verificación secuencial de los números, comenzando del 2 al 100. Si no hay divisor, se registra en la tabla; si es compuesto, entonces no se ingresa en la tabla.

Veámoslo paso a paso.

Si comienzas con el número 2, entonces solo tiene 2 divisores: 2 y 1, lo que significa que se puede ingresar en la tabla. Lo mismo con el número 3. El número 4 es compuesto; hay que descomponerlo en 2 y 2. El número 5 es primo, lo que significa que se puede registrar en la tabla. Haz esto hasta el número 100.

Este método es inconveniente y requiere mucho tiempo. Es posible crear una tabla, pero tendrás que dedicar mucho tiempo. Es necesario utilizar criterios de divisibilidad, lo que acelerará el proceso de encontrar divisores.

El método que utiliza el tamiz de Eratóstenes se considera el más conveniente. Veamos las tablas de ejemplo a continuación. Para empezar se anotan los números 2, 3, 4, ..., 50.

Ahora necesitas tachar todos los números que sean múltiplos de 2. Realizar tachados secuenciales. Obtenemos una tabla como:

Pasamos a tachar números que sean múltiplos de 5. Obtenemos:

Tacha los números que sean múltiplos de 7, 11. Al final la mesa parece

Pasemos a la formulación del teorema.

Teorema 3

El divisor positivo más pequeño y distinto de 1 del número base a no excede a, donde a es la raíz aritmética del número dado.

Evidencia 3

Es necesario denotar b como el divisor más pequeño de un número compuesto a. Existe un número entero q, donde a = b · q, y tenemos que b ≤ q. Las desigualdades de forma son inaceptables. b > q, porque se viola la condición. Ambos lados de la desigualdad b ≤ q deben multiplicarse por cualquier número positivo b distinto de 1. Obtenemos que b · b ≤ b · q, donde b 2 ≤ a y b ≤ a.

Del teorema probado se desprende claramente que tachar números en la tabla lleva al hecho de que es necesario comenzar con un número que sea igual a b 2 y satisfaga la desigualdad b 2 ≤ a. Es decir, si tachas números que son múltiplos de 2, entonces el proceso comienza con el 4, y los múltiplos de 3 con el 9, y así hasta el 100.

La compilación de una tabla de este tipo utilizando el teorema de Eratóstenes sugiere que cuando se tachan todos los números compuestos, quedarán números primos que no excedan n. En el ejemplo donde n = 50, tenemos que n = 50. De aquí deducimos que el tamiz de Eratóstenes separa todos los números compuestos que no tienen un valor significativo. mayor valor raíz de 50. La búsqueda de números se realiza tachando.

Antes de resolver, debes averiguar si el número es primo o compuesto. A menudo se utilizan criterios de divisibilidad. Veamos esto en el siguiente ejemplo.

Ejemplo 1

Demuestre que el número 898989898989898989 es compuesto.

Solución

La suma de los dígitos de un número dado es 9 8 + 9 9 = 9 17. Esto significa que el número 9 · 17 es divisible por 9, según la prueba de divisibilidad por 9. De ello se deduce que es compuesto.

Estos signos no pueden demostrar la primacía de un número. Si se necesita verificación, se deben tomar otras acciones. Mayoría manera adecuada- son un montón de números. Durante el proceso, puedes encontrar números primos y compuestos. Es decir, los números no deben exceder a en valor. Es decir, el número a debe descomponerse en factores primos. si esto se cumple, entonces el número a puede considerarse primo.

Ejemplo 2

Determina el número compuesto o primo 11723.

Solución

Ahora necesitas encontrar todos los divisores del número 11723. Necesidad de evaluar 11723.

Desde aquí vemos que 11723< 200 , то 200 2 = 40 000 y 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Para obtener una estimación más precisa del número 11723, debes escribir la expresión 108 2 = 11 664, y 109 2 = 11 881 , Eso 108 2 < 11 723 < 109 2 . Se deduce que 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Al expandir encontramos que 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107 son todos números primos. Todo este proceso se puede representar como una división por una columna. Es decir, divida 11723 entre 19. El número 19 es uno de sus factores, ya que obtenemos la división sin resto. Representemos la división como una columna:

De ello se deduce que 11723 es un número compuesto, porque además de sí mismo y 1 tiene un divisor de 19.

Respuesta: 11723 es un número compuesto.

Si nota un error en el texto, resáltelo y presione Ctrl+Enter