Cómo demostrar que 1033 es número primo

Answer 1

Si está calculando esto usando una computadora, puede usar la prueba de primalidad Miller-Rabin.

La prueba se basa en las siguientes relaciones, que son verdaderas solo para los números primos, pero no para todos. Si podemos encontrar múltiples valores de [math] a \ in \ Z / n \ Z [/ math] que no verifican estas relaciones, podemos estar bastante seguros de que [math] n [/ math] no es primo.

[matemáticas] a ^ d \ not \ equiv 1 \ pmod n [/ matemáticas]

[matemáticas] a ^ {2º} \ not \ equiv -1 \ pmod n [/ matemáticas]

Con [math] 0 \ leq r \ leq s-1 [/ math] donde tenemos [math] s [/ math] tal que [math] n-1 = 2 ^ s \ cdot d [/ math], [math ] d [/ math] es impar.

Para [matemática] n = 1033 [/ matemática], tenemos [matemática] n-1 = 1032 = 2 ^ 3 \ cdot 129 [/ matemática], entonces [matemática] d = 129 [/ matemática] y [matemática] s = 3 [/ matemáticas].

Entonces queremos [math] a [/ math] tal que [math] a ^ {129} \ not \ equiv 1 \ pmod {1033} [/ math]

y [matemáticas] a ^ {2 \ cdot 129 \ cdot r} \ not \ equiv -1 \ pmod {1033} [/ math].

Marque [math] a \ in \ {2,3,4 \} [/ math].

Answer 2

Quería escribir esto para que los principiantes también puedan aprender cómo abordar estas preguntas. para eso, debemos conocer la definición de número primo. ¿Cuáles son los criterios de cualquier número para que pueda clasificarse como número primo? Entonces, mi objetivo es mostrar cómo cualquier número puede considerarse como primo para que cualquiera pueda abordar este tipo de preguntas.

Número primo

Un número primo es un número entero que es mayor que uno y tiene exactamente dos factores, 1 y en sí mismo, lo que significa que

Un número compuesto es un número entero que es mayor que uno y tiene más de dos factores. El número 1 no es primo ni compuesto. El número 2 es el único número par primo.

Metodología manual

Dado que con respecto a estas preguntas en la aplicación de computadora de formulario, también podemos formar un algoritmo, existe un algoritmo muy famoso como Sieve of Eratosthenes, uno de los antiguos.

También podemos usar la prueba de primalidad de Lucas

Pero mi enfoque es encontrar un programa general que resuelva no solo este, sino también la misma clase de este problema

# Programa de Python para verificar si el número de entrada es primo o no

num = 407

# tomar entrada del usuario
# num = int (input (“Ingrese un número:”))

# los números primos son mayores que 1
si num> 1:
# verificar factores
para i en rango (2, num):
if (num% i) == 0:
print (num, “no es un número primo”)
print (i, “veces”, num // i, “es”, num)
rotura
más:
print (num, “es un número primo”)

# si el número de entrada es menor que
# o igual a 1, no es primo
más:
print (num, “no es un número primo”)

Answer 3

Para que un número sea primo, no debe ser divisible por ningún número primo múltiplo.
Entonces lo dividimos por 2 y seguimos subiendo.
Como 2,3,5,7,11,13 y así sucesivamente.
Obtenga el número primo múltiplo hasta 517 y verifique.
¿Por qué 517?
Porque para 1033 (+1 para hacerlo par) 1034/2 = 517.
517 sería el último múltiplo, ya que todo lo que esté debajo tendrá 2 como múltiplo o un número primo mayor que 517 será mayor que 1033 (517 × 2 = 1034), por lo que no necesitamos verificar ningún número primo por encima de la mitad.

Sí, también podemos sacarle la raíz cuadrada de manera similar.
Como el factor será la parte de un número menor o en sí mismo.

P.ej. 35 cuadrado es 1225, que es más que el número. Así que verifique todos los números primos por debajo de 35.

Answer 4

Para mostrar la primalidad de 1033, puedes intentar dividir entre números pequeños, hasta la raíz cuadrada. Si conoces algunos trucos, puedes ahorrarte mucho tiempo.

1033 termina en 3, los dígitos se suman a 7, por lo que 2,3,5 no dividen esto.

1001 = 7 * 11 * 13, 1033-1001 = 32, que ninguno de 7,11,13 divide.

1033 = 1, 4, 13 en la base 30, no da una suma que 29 divide ni 1-4 + 13 es un múltiplo de 31.

Por lo tanto, deja 17, 19, 23

Vemos que 1033 = 1020 + 13, donde 17 divide el primero pero no el segundo.

Del mismo modo, 1033 = 133 + 900, donde 19 divide el primero pero no el segundo.

Del mismo modo, 1033 = 23 + 1010, donde 23 divide el primero, pero no el segundo.

No primo menor que 31 divide esto, por lo tanto es primo.

Answer 5

Podemos usar la prueba de primalidad de Lucas con [math] a = 5 [/ math]. La factorización prima de [math] 1032 [/ math] es [math] 2 ^ 3 \ cdot 3 \ cdot 43 [/ math]. Usando la exponenciación modular rápida al cuadrado, calculamos

[matemáticas] \ begin {align *} 5 ^ {1032} & = (((((((((5 ^ 2) ^ 2) ^ 2) ^ 2) ^ 2) ^ 2) ^ 2 \ cdot 5) ^ 2) ^ 2) ^ 2 \ equiv 1 \ pmod {1033}, \\ 5 ^ {1032/2} & = ((((((((5 ^ 2) ^ 2) ^ 2) ^ 2) ^ 2) ^ 2) ^ 2 \ cdot 5) ^ 2) ^ 2 \ equiv 1032 \ not \ equiv 1 \ pmod {1033}, \\ 5 ^ {1032/3} & = ((((((5 ^ 2) ^ 2 \ cdot 5) ^ 2) ^ 2 \ cdot 5) ^ 2 \ cdot 5) ^ 2) ^ 2) ^ 2 \ equiv 837 \ not \ equiv 1 \ pmod {1033}, \\ 5 ^ { 1032/43} & = (((5 ^ 2 \ cdot 5) ^ 2) ^ 2) ^ 2 \ equiv 995 \ not \ equiv 1 \ pmod {1033}. \ End {align *} [/ math]

Por lo tanto, [matemáticas] 1033 [/ matemáticas] es primo.

(El primer cálculo con [math] 5 ^ {1032} [/ math] solo nos dice que [math] 1033 [/ math] es primo o pseudoprime para basar [math] 5 [/ math]. Necesitamos los otros tres cálculos para garantizar que sea realmente excelente.)

Answer 6

Apóyese en el poder de n-1 y modifíquelo por n; si es igual a 1, es primo (nota, primo ^ el número de modulación total será igual a 1 si no es primo y el primo de prueba no es un factor; por ejemplo, 5 ^ (7-1) (13-1) mod 91 = 1 o 5 ^ 72 mod 91 = 1)

5 ^ 1032 mod 1033

15

2) 5 ^ 2 mod 1033 = 25

4) 25 ^ 2 mod 1033 = 625

8) 625 ^ 2 mod 1033 = 151

16) 151 ^ 2 mod 1033 = 75

32) 75 ^ 2 mod 1033 = 460

64) 460 ^ 2 mod 1033 = 868

128) 868 ^ 2 mod 1033 = 367

256) 367 ^ 2 mod 1033 = 399

512) 399 ^ 2 mod 1033 = 119

1024) 119 ^ 2 mod 1033 = 732

El número 1032 es 1024 + 8

732 * 151 mod 1033 = 1

1033 es primo.

Este es el método manual (Long Prime Division como un juego de palabras).

Answer 7

Una comprobación simple pero algo tediosa es esta:

Intente dividirlo entre todos los números primos, y si llega al número primo más alto que es la mitad o menos de la mitad de 1033 (que sería igual o menor que 516.5) sin poder dividirlo por ninguno de ellos (eso significa , sin obtener un resultado con “señalar algo”), entonces es un número primo.

Primero 1033/2 = 516.5, no funciona

1033/3 = 344.333 … no funciona

1033/5 = 206.6 no funciona

…

hasta 509, el número primo más alto que es igual o menor que la mitad de 1033, y verá que nadie da un resultado redondo. Por lo tanto, es un número primo.

Los únicos números que dan un resultado redondo son, por supuesto, 1 y 1033.

---

Verifique los números primos hasta el 2000 aquí:

Lista de números primos

Answer 8

Demuestre que no es divisible por ninguno de los siguientes: 2,3,5,7,11,13,17,19,23,29,31.

Answer 9

El cuadrado justo antes de 1033 es 1024, es decir 32 al cuadrado.

Ahora solo verifique si 1033 es divisible por cualquier primo antes de 32.

2 – no
3 – no
5 – no
7 – no
11 – no
13, 17, 19, 23, 29, 31 – no

Entonces es un primo.

Answer 10

Realice la prueba de Miller-Rabin para a = 2 (eso es todo lo que necesita).

https://en.wikipedia.org/wiki/Mi …

Answer 11

Si 1033 no es primo, comience a probar con primos debajo de la raíz cuadrada.

p.ej. √1033 = 32.14 .. comience a probar con 31, 29, 23,… 7 –5,3,2 no es necesario.

Solo hay ocho factores para usar en esta prueba larga.

Ninguno funciona, así que 1033 es primo.