Enviado por El Nigromante el 6. Mayo 2005 - 13:26.
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).
Explicación (x^2 = 1 (mod n))
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).