Saber si un numero es primo

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

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 ;)

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 ;)

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

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.

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.

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 ;)

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...).

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

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).

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 ;)

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?

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

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

que significa mod