Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.
Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.
Y si los símbolos < y > te dan problemas al escribir en LaTeX, te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.
Tienes un 20% de descuento y envío gratis en toda la web de La Tostadora con al menos dos artículos. Usa el código GAUSSIANOS entrando con el enlace de la imagen.
Y usando el código REBAJAS tienes un 30% de descuento hasta el 8 de agosto con al menos 3 artículos.
Si quieres recibir los artículos de Gaussianos en tu mail haz click en la imagen.
Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.
Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.
y 
.
es primo si y sólo si 
, 
Um… ahora mismo me sale una implicacion
Para esto, veamos que
es múltiplo de n (bajo algunas condiciones).
Si k = 1 o k = n,
Si k es diferente de 1 y n.
Todos los factores de
y 
son, obviamente, mas pequeños que n. Y como n es primo, es imposible que esos numeros dividan a n. Así pues
para un cierto k.
Ahora solo tenemos que desarrollar
.
Y haciendo la congruencia modulo n, todos los elementos del sumatorio «desaparecen» porque son múltiplos de n.
sí, Ryochi. Te faltó indicar que
, pero se asume que ésto es bien conocido.
Vamos a por el recíproco que tiene un pelín más de gracia y es la implicación realmente más interesante.
¿Este problema no es equivalente a demostrar que n es primo si el pequeño teorema de Fermat
se cumple para todo 0<a<n?
Tampoco entiendo por qué x aparece elevado a n en la derecha de la igualdad. O mucho me equivoco o así también sería correcto:
Es decir, a un cambio de variable de distancia del pequeño teorema de Fermat.
Hola Sive, de hecho el resultado es una generalización del teorema de Fermat, para poder dar una caracterización de número primo (cosa que no permite el teorema de Fermat).
El criterio
(
) no implica que 
es primo (sino pseudoprimo: http://es.wikipedia.org/wiki/N%C3%BAmero_pseudoprimo).
Por esta razón, aparece
en el lado derecho de la congruencia que se propone.
Cierto M, es que en informática solemos usar el pequeño teorema de Fermat así:
La cual es una prueba que no pasan ni siquiera los pseudoprimos (la demostración es trivial, si n = A·B, ambos diferentes de 1, para z=A, ningún exponente diferente de 0 puede dar 1).
Apresuradamente supuse que al multiplicar por z ambos miembros de la congruencia, seguía siendo cierto.
Pues debe haber algo más que se me escapa porque ahora estoy convencido de que lo que plantea el problema es falso :S
Pero bueno, sabe Dios de que estaré convencido dentro de un rato.
Voy a exponer el razonamiento porque no veo el fallo.
Dado este enunciado resumido:
Supongamos que se ha demostrado falso para un determinado n=N, que es compuesto pero que cumple la relación de congruencia. Ya M ha comentado que hay números así, sólo estoy suponiendo que N es uno de estos números.
Pues bien, para este número se cumplen estas dos cosas para cualquier par de enteros x y a:
Por tanto el enunciado del problema planteado también es falso.
Si esto también es erróneo prometo no añadir más comentarios a este problema 😛
Por lo que entiendo, el pseudoprimo es respecto de una base, es decir: el número N del intento de contraejemplo cumple la congruencia pero para un determinado valor de x (coprimo con él), no para todo entero x.
Por eso, es falso la implicancia (las dos ecuaciones) y por lo tanto el razonamiento.
Una manera más fácil de desmostrar la «ida» es así:
Se sabe que para todo
si 
es primo, entonces 
.
De ello se sigue que
. Luego «sustituyendo» el primer resultado en el segundo, queda que 
.
El primer resultado se puede demostrar en pocas líneas haciendo un análisis de dos casos y usando el pequeño teorema de Fermat; pero no pongo la demostración porque es un ejercicio interesante.
hernan, sí y no.
La definición de pseudoprimo, al menos tal y como está en wikipedia, se basa en el PTF tal y como lo solemos usar los informáticos, así:
.
Y en este caso es justo como dices, se cumple para valores concretos de a, pero no hay pseudoprimos en los que esto se cumpla para todo entero
.
Pero sí hay pseudoprimos en los que se cumple el PTF, expresado de la forma más habitual,
para todo entero 
.
Por ejemplo, el 561
Los números que a pesar de no ser primos verifican el PTF, para cualquier base, se llaman números de Carmichael.
El 1729, de la matrícula del célebre taxi, es otro de estos números.
Que conste que no los conocía hasta el comentario de M, pero me ha picado la curiosidad y los estoy estudiando. Son interesantes, y algunas de las propiedades que deben tener se deducen muy fácilmente. Yo creo se merecen una entrada en Gaussianos.
Hola Sive, Damián. Lleváis razón, tal cual está planteado el problema . Efectivamente, el número de Carmichael 561 cumple la propiedad (tal cual está enunciada) y no es primo. Y en esas condiciones el enunciado es ciertamente falso. Pido disculpas por el lapsus en el enunciado y las consecuentes molestias que haya ocasionado. La confusión surge de poner «». Si se me permite rectificar ligeramente el enunciado, y ^Diamond^ lo considera oportuno, el enunciado bien interpretado debe decir: «Sea y . Demostrar que es primo si y sólo si . Aclaración: La igualdad entre los polinomios en , , se… Lee más »
con lo cual la equivalencia nos sirve de test («no polinomial») para saber si un número dado es primo o no.
Bueno, en lo que a mí respecta, ha sido un feliz error.
A lo mejor para los matemáticos era algo archiconocido, pero para mí los números de Carmichael han sido todo un hallazgo.
M lo cambio ahora mismo. Dejo como enunciado lo que has puesto entre comillas en el comentario donde lo rectificas.
Jejeje, ¿qué andas leyendo por ahí, ^DiAmOnD^? Mira que me sonaba el problema, pero no me recordaba de qué… y al leer lo del test de primalidad (no polinómico) me he acordado: Este resultado es el primer lema del artículo de Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of Mathematics 160 (2004), no. 2, pp. 781–793. En este artículo (que se hizo muy famoso el año de su publicación) se demuestra que es posible determinar la primalidad de un número en tiempo polinómico, y se da un algoritmo específico para hacerlo (que a pesar de ser… Lee más »
jejeje, ahí le has dado 🙂
vengoroso yo no he sido quien ha estado leyendo por ahí…el problema es propuesto por alguien…(carita silbando :D)
¿Nadie se atreve con el problema o es que ya hemos mirado la solución todos?
bueno, Sive, por mi parte entendí zanjado el asunto entre los comentarios de vengoroso y Asier (en https://gaussianos.com/%C2%A1%C2%A1tenemos-dos-nuevos-primos-de-mersenne/#comments)