Test de primalidad

Vamos con el problema de la semana:

Sea a\in\mathbb{Z}, n\in\mathbb{N}, n\geq 2 y mcd(a,n)=1.

Demostrar que n es primo si y sólo si (x+a)^n=x^n+a \; (mod \; n)

Aclaración: la igualdad entres los polinomios en x, (x+a)^n=x^n+a \; (mod \; n), se interpreta como identidad polinomial coeficiente a coeficiente

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

21 Comentarios

  1. Um… ahora mismo me sale una implicacion
    n \text{es primo} \Longrightarrow (x + a)^n = x^n + a \mod{n}

    Para esto, veamos que \binom{n}{k} es múltiplo de n (bajo algunas condiciones).

    Si k = 1 o k = n, \binom{n}{k} = 1

    Si k es diferente de 1 y n.
    \binom{n}{k} = \dfrac{n \cdot (n-1)!}{k! \cdot (n-k)!}

    Todos los factores de k! y (n-k)! son, obviamente, mas pequeños que n. Y como n es primo, es imposible que esos numeros dividan a n. Así pues
    \binom{n}{k} = n \cdot k para un cierto k.

    Ahora solo tenemos que desarrollar (x + a)^n.

    (x+a)^n = x^n + \sum_{i=1}^{n-1} \binom{n}{i} x^i \cdot a^{n-i} + a = x^n + \sum_{i=1}^{n-1} n \cdot l_{i} \cdot x^i \cdot a^{n-i}

    Y haciendo la congruencia modulo n, todos los elementos del sumatorio “desaparecen” porque son múltiplos de n.

    Publica una respuesta
  2. sí, Ryochi. Te faltó indicar que a^n\equiv a (mod\;n), 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.

    Publica una respuesta
  3. ¿Este problema no es equivalente a demostrar que n es primo si el pequeño teorema de Fermat a^n=a (\mod n) se cumple para todo 0<a<n?

    Publica una respuesta
  4. 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:

    (x+a)^n=x+a (mod n), \forall x\in\mathbb{Z}

    Es decir, a un cambio de variable de distancia del pequeño teorema de Fermat.

    Publica una respuesta
  5. 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 z^n=z (mod \;n), \forall z\in\mathbb{Z} (z=x+a) no implica que n es primo (sino pseudoprimo: http://es.wikipedia.org/wiki/N%C3%BAmero_pseudoprimo).

    Por esta razón, aparece x^n en el lado derecho de la congruencia que se propone.

    Publica una respuesta
  6. Cierto M, es que en informática solemos usar el pequeño teorema de Fermat así:

    z^{n-1}=1 (mod \;n) \forall z\in\mathbb{Z}

    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.

    Publica una respuesta
  7. 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.

    Publica una respuesta
  8. Voy a exponer el razonamiento porque no veo el fallo.

    Dado este enunciado resumido:

    n es primo si y sólo si x^n=x (mod \;n), \forall a\in\mathbb{Z} \quad \quad \quad (1)

    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:

    (x + a) ^ N = (x + a) (mod \;n)
    x^N = x (mod \;n)

    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 😛

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. Una manera más fácil de desmostrar la “ida” es así:

    Se sabe que para todo x\in \mathbb{Z} si n es primo, entonces x^n \equiv x \pmod{n}.

    De ello se sigue que (x+a)^n \equiv x+a \pmod{n}. Luego “sustituyendo” el primer resultado en el segundo, queda que (x+a)^n \equiv x^n+a \pmod{n}.

    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.

    Publica una respuesta
  11. 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í: a^{n-1} = 1 (mod \;n).

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

    Pero sí hay pseudoprimos en los que se cumple el PTF, expresado de la forma más habitual, a^n = a (mod \;n) para todo entero a.

    Por ejemplo, el 561

    Publica una respuesta
  12. 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.

    Publica una respuesta
  13. 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 “\forall x\in \mathbb{Z}”.

    Si se me permite rectificar ligeramente el enunciado, y ^Diamond^ lo considera oportuno, el enunciado bien interpretado debe decir:

    “Sea a\in\mathbb{Z}, n\in\mathbb{N}, n\geq 2 y mcd(a,n)=1.

    Demostrar que n es primo si y sólo si (x+a)^n=x^n+a \;(mod\; n).

    Aclaración: La igualdad entre los polinomios en x, (x+a)^n=x^n+a \;(mod\; n), se interpreta como identidad polinomial coeficiente a coeficiente.”

    Una implicación ya ha sido probada por Ryochi, y la idea es ésa: ver que todos los coeficientes intermedios del desarrollo (x+a)^n se anulan (módulo n) si y sólo si n es primo.

    Pido disculpas de nuevo, y espero que la confusión creada no quite interés al problema.

    Publica una respuesta
  14. con lo cual la equivalencia nos sirve de test (“no polinomial”) para saber si un número dado es primo o no.

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. M lo cambio ahora mismo. Dejo como enunciado lo que has puesto entre comillas en el comentario donde lo rectificas.

    Publica una respuesta
  17. 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 polinómico no es demasiado eficiente). Obviamente, la solución al problema está en el archivo, así que el que quiera resolverlo que no mire 😛

    Publica una respuesta
  18. vengoroso yo no he sido quien ha estado leyendo por ahí…el problema es propuesto por alguien…(carita silbando :D)

    Publica una respuesta
  19. ¿Nadie se atreve con el problema o es que ya hemos mirado la solución todos?

    Publica una respuesta

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.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *