Kriptópolis

28 comentarios sobre Saber si un numero es primo

• 

  condiciones necesarias y suficientes

  anónimo
  9 Noviembre 2008 - 10:59pm

  x es primo si y solo si Suma[Floor[x/ i]-Floor[ (x-1)/i], {i,1,Sqrt[ x]}] = 1 o bien si y sólo si (x-1)!=-1(mod x).
  Métodos muy lentos algorítmicamente.
• 

  Oportuno la interrogante inicial

  anónimo
  7 Noviembre 2008 - 8:08pm

  La verdad, también soy uno de los interesados en saber explicar didácticamente en cuanto si un número "n" es primo y ¿cómo llegar a la explicación breve? porque descomponiendo o buscando divisores u otros, la verdad es que me voy a demorar y lo voy a hacer complejo el trabajo. Razón por el cual, aún continúa mi interrogante. Por favor despeja mi duda.

Como enseñar los numeros primos
anónimo
8 Noviembre 2008 - 8:30pm
No es necesario que utilices números muy grandes para tu ejemplo por lo que si puedes "buscar" los divisores.
Te recomiendo que hagas lo siguiente, para todos los numeros de 1 a 10 calcules los divisores frente a la clase. Para esto tienes que dividir el número por todos los naturales menores o iguales al numero, y ver el resto. Esto lo puedes hacer en voz alta preguntandole a los alumnos como ejercicio de calculo mental.
Entonces en la pizarra te queda:
N Divisores
1 1
2 1 2
3 1 3
4 1 2 4
5 1 5
6 1 2 3 6
7 1 7
8 1 2 4 8
9 1 3 9
10 1 2 5 10
Con eso hecho, les dices que todos los numeros (positivos si corresponde) que tengan sólo dos divisores son primos. Y que necesariamente estos dos divisores tienen que ser 1 y el mismo número.
• 

  numero primo y compuesto

  anónimo
  14 Octubre 2008 - 7:42pm

  lo que haces es declarar variables

  x,i=1,p=0;
  ingresas datos (x)
  while (i
• 

  algoritmo y pseudocodigo

  anónimo
  20 Mayo 2008 - 3:04am

  necesito saber cuando un numero ingresado desde una terminal es primo.

  calcular las raices de una ecuacion de segundo grado de la forma ax2+bx+c=0
• 

  Significado

  anónimo
  4 Mayo 2008 - 6:07am

  que significa mod
• 

  programa conrespecto a esto

  anónimo
  4 Mayo 2008 - 5:36am

  y como crearia un programa que al entrarle un numero cualquiera me diga si es primo o no
• 

  a ver si es correcto...

  anónimo
  28 Marzo 2008 - 7:58pm

  dado un numero x, y un n que toma valores incrementales desde 2 hasta x-1, si x mod n <> 0, en todos los valores de n, es primo.

  billy.ar
• 

  Pregunta

  anónimo
  26 Junio 2007 - 2:30am

  Es el número 2 un número primo? Todos los números pares no son primos, por ende no es primo. O me equivoco?

Si es primo
anónimo
26 Junio 2007 - 9:18pm
el dos si que es primo, 1 ,2 ,3 ,5 etc son primos.

nop ese nop
anónimo
11 Octubre 2007 - 1:29am
todo lo anterior es correcto!!
pero el 1 no es un numero primo
solo el 2 y de ahi en adelante los impares
El conjunto de los números primos es un subconjunto de los números naturales que engloba a todos los elementos de este conjunto mayores que 1 que son divisibles únicamente por sí mismos y por la unidad.
Los números primos, menores que cien, son:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97.
gracias
=)

Definición de número primo (según yo)
anónimo
26 Junio 2007 - 8:57pm
No generalicemos. Ningún número par es primo, *excepto* el número 2. El 2 es la excepción a la regla. (Y no sólo a ésta, piensa que 2+2 = 2*2 = 2^2 = 4, pero no es la idea :-) )
Entiendo que número primo se define como "un número natural divisible sin resto sólo por sí mismo y por la unidad."
Entonces, según esta definición, el 2 es número primo. Así, el 2 es el único número par que es primo.
En efecto: 2/1=2, resto=0; 2/2=1, resto=0. QED.
Espero que te sirva como "demostración"
JRBA
• 

  Bravo, te felicito!!!

  benru_x86
  7 Mayo 2005 - 11:23am

  Muchas gracias 'El Nigromante',la verdad es que me ha dado mucha alegría ver que has encontrado la solución :D porque la verdad es que pensaba que ya el debate se iba a quedar en el olvido.

  Uno con ganas de aprender ;)
• 

  Explicación (x^2 = 1 (mod n))

  El Nigromante
  6 Mayo 2005 - 1:26pm

  Investigando un poco he encontrado una posible explicación al tema planteado. En concreto, ver el ejercicio 15 de la sección 2.6 del libro "Discrete Mathematics and its Applications" Fifth Ed., de K.H. Rosen, Ed. McGraw-Hill. (Ver también el ejercicio 53 de la misma sección).

  Según la citada referencia, si n es primo, las únicas soluciones de x^2 = 1 (mod n) son los enteros x tales que: x = 1 (mod n) ó x = -1 (mod n).

  La demostración es como sigue: x^2 = 1 (mod n) ==> x^2 - 1 = 0 (mod n) ==> (x+1)(x-1) = 0 (mod n) ==> n divide a (x+1)(x-1). Si n divide a (x+1)(x-1) y n es primo ==> n divide a (x+1) ó n divide a (x-1) ==> x+1 = 0 (mod n) ó x-1 = 0 (mod n) ==> x = -1 (mod n) ó x = 1 (mod n)

  Por otra parte, si existiera un x tal que no cumpliese x = 1 (mod n) y tampoco x = -1 (mod n), pero verificase la congruencia que tenemos x^2 = 1 (mod n), entonces n no puede ser primo, pues estaríamos negando la conclusión (que las únicas soluciones de la congruencia son x = 1 (mod n) y x = -1 (mod n)) y eso implica la negación de la premisa (n primo).

  Nota sobre los primos de Mersenne: son aquellos números primos de la forma 2^p - 1, siendo p primo también (me remito también al citado libro).

Utilidad de la propiedad
anónimo
10 Noviembre 2008 - 6:29pm
La propiedad antes descrita no sirve de mucho para detectar numeros primos. Ya que de hecho solo asegura que si se encuentra un x distinto de 1 y n-1, tal que x^2=1 mod n, entonces n no es primo, el caso opuesto no es cierto.
Con los primeros numeros enteros compuestos vemos que está propiedad no sirve mucho para encontrar numeros primos.
Ya que 1^2 = 1 mod n, y que (n-1)^2 = 1 mod n, para todo n, basta revisar el resto de los numeros.
2^2 = 4 = 0 mod 4
2^2 = 4 mod 6
3^2 = 9 = 3 mod 6
4^2 = 16 = 4 mod 6
2^2 = 4 mod 8
3^2 = 9 = 1 mod 8
4^2 = 16 = 0 mod 8
5^2 = 25 = 1 mod 8
6^2 = 36 = 4 mod 8
2^2 = 4 mod 9
3^2 = 9 = 0 mod 9
4^2 = 16 = 7 mod 9
5^2 = 25 = 7 mod 9
6^2 = 36 = 0 mod 9
7^2 = 49 = 4 mod 9
Con lo anterior solo sabemos que 8 no es primo pues tiene un x distinto de 1 y 7 tal que x^2 = 1 mod 8.
Sobre el resto de los numeros no podemos decir nada.
• 

  Mersenne

  kilburn
  3 Mayo 2005 - 10:52pm

  Los números que cumplen esa condición son llamados "primos de Mersenne". Muchísima más información en: www.mersenne.org
• 

  Mi pobre aportación

  El Nigromante
  28 Abril 2005 - 6:30pm

  La verdad es que tampoco acabo de comprender muy bien la x. La ecuación que has puesto es x*x + y*n = 1. Me recuerda al algoritmo de Euclides, pero es a lo más que llego (no soy matemático)

  Lo que si sé es que para comprobar que un número es primo sólo hace falta comprobar sus posibles divisores desde 2 hasta n^(1/2) (o sea, sqrt(n)).

  Sólo añadir también que hasta la fecha - que yo sepa -, no existe una fórmula matemática explícita para resolver que un número sea primo o compuesto, sino tests que dan cierta probabilidad, exceptuando la prueba evidente claro (dividir sucesivamente...).

Creo recordar que hace dos a
modn
29 Abril 2005 - 4:24am
Creo recordar que hace dos años o así en una univerdad de ¿Israel? sacaron un método nuevo para saber si un número era primo o no sin tener que dividirlo hasta la raiz cuadrada.
Había implementaciones en software y el algoritmo del método.
Tampoco profundicé, así que solo puedo comentarlo de oidas.
Respecto a la ecuación de este post, ya solo por salir de dudas, a ver si alguien entiende algo.
Me suena al algoritmo de primalidad de Rabit-Miller.
Si existe un raiz cuadrada no trivial de de 1 mod n, entonces n no es primo.

Desconozco el algoritmo pero, haciendo pruebas
tiocharly
2 Mayo 2005 - 11:22am
Desconozco el algoritmo pero, haciendo pruebas creo que estas en lo cierto, para un valor de n=21, tenemos en la parte izquierda,0.16 cuya raiz es 0.4. Número no primo-->raiz trivial. Aunque no se cumple con todos los numeros primos(p.ej n=27-->0.19, raíz no trivial). El algortimo se cumple para alguno valores(4,10,12,13,..) y para otros no(6,8,9,..).
Espero no haberme equivocado y poder ayudar en algo.

Algoritmo
Ori
8 Mayo 2005 - 1:37pm
Lo que si existe es un algoritmo que determina la "primalidad" de un numero en un tiempo polinómico, es el llamado algoritmo AKS.
http://www.cse.iitk.ac.in/news/primality.html
• 

  Os muestro exactamente lo que me pidieron hacer

  benru_x86
  25 Abril 2005 - 4:28pm

  En realidad, lo que os he propuesto es un ejercicio que me mandaron hacer y decía exactamente lo siguiente:

  Un test de primalidad podría consistir en saber si el entero 'n' es o no primo por la simple resolución de la congruencia:

  x^2 = 1 mod n

  ¿Qué valores de x daría la pista para saber si el número elegido 'n' es primo? Hacer una prueba con el anterior algoritmo para saber si los numeros n=7 y n=8 son primos no par

  Uno con ganas de aprender ;)
• 

  Saber si un numero es primo

  stolander
  24 Abril 2005 - 10:08pm

  Todo numero primo mayor que tres es igual a un multiplo de seis aumentado o disminuido en una unidad. Ademas, todo numero primo distinto de dos termina en uno, tres, siete o nueve. Ademas, si un numero cualquiera se divide por un numero primo menor que el y arroja un resultado exacto, no es primo. Por el contrario, si el resultado no es exacto y al mismo tiempo el cuociente es menor que el divisor, el numero es primo. Todo eso se debe combinar con los caracteres basicos de divisibilidad por tres, siete, nueve y once y tendras una prueba de primalidad cuya probabilidad de error es proporcional al orden de magnitud del numero.
  Como puedes ver, lo puse todo en español para que tu hagas la traduccion a algebra y asi lo puedas comprender cabalmente.
• 

  Que es la x?

  raspa atonal
  24 Abril 2005 - 9:30pm

  En ningún momento dices que es la x.

  Lo único que te puedo decir es que si p ES PRIMO entonces:
  b^(p-1)=1(mod p) para todo b
  (pequeño teorema de Fermat???).
  Pero no es cierto el reciproco.Es decir, si encuentras algún b que no cumpla la congruencia tendras que p no es primo. Pero, que todo b lo cumpla no significa que p sea primo. Ahora mismo no me acuerdo de los detalles pero busca información sobre el pequeño teorema de Fermat , sobre pseudoprimos y sobre números de Carmichael.
• 

  No entiendo bien

  modn
  22 Abril 2005 - 11:13am

  3^2 mod 8 = 1, siendo 8 número no primo.
• 

  Pues no entiendo la respuesta

  benru_x86
  22 Abril 2005 - 2:34am

  No veo donde esta contestada mi pregunta en el codigo.

  def isprime(aNumber):
  '''return True if the number is prime, false otherwise'''
  if aNumber < 2: return False
  if aNumber == 2: return True
  if (( aNumber / 2 ) * 2 == aNumber) : return False
  else:
  klist = primes(int(math.sqrt(aNumber+1)))
  for k in klist[1:]:
  if (( aNumber / k ) * k == aNumber ): return False
  return True

  Si me puedes explicar en que parte...

  Gracias.

  Uno con ganas de aprender ;)
• 

  No buscaba un programa

  benru_x86
  21 Abril 2005 - 6:27pm

  Hola,
  la cosa es que el objetivo no era hacer un programa que me devolviera si un numero es primo.
  El problema es que me gustaría saber porque si ocurre lo que arriba comento: x^2 = 1 mod n ; n entonces es primo.
  Además me gustaría que alguien me dijese como resolver esta congruencia.

  Para poder resolverla, la única manera es que ocurra que x = x^(-1), ¿no? Y para que pase eso, ¿¿que tiene que ocurrir??

  Muchas gracias por ayudar

  Uno con ganas de aprender ;)

Pero no es un programa...
spy (no verificado)
21 Abril 2005 - 7:47pm
Es una respuesta ;)
• 

  Una recetilla en Python

  spy (no verificado)
  21 Abril 2005 - 5:54pm

  http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/410662