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^ | Publicado el 9 de Septiembre de 2008
Categorías: Juegos

21 comentarios

Ryochi | 9 de Septiembre de 2008 | 9:48

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.
M | 9 de Septiembre de 2008 | 14:25

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.
Sive | 10 de Septiembre de 2008 | 8:49

¿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?
Sive | 10 de Septiembre de 2008 | 8:55

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.
M | 10 de Septiembre de 2008 | 11:48

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.
Sive | 10 de Septiembre de 2008 | 14:18

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.
Sive | 10 de Septiembre de 2008 | 15:01

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.
Sive | 10 de Septiembre de 2008 | 15:53

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
hernan | 10 de Septiembre de 2008 | 17:03

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.
Damián | 10 de Septiembre de 2008 | 17:15

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.
Sive | 10 de Septiembre de 2008 | 17:24

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
Sive | 10 de Septiembre de 2008 | 17:42

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.
M | 10 de Septiembre de 2008 | 17:45

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.
M | 10 de Septiembre de 2008 | 17:48

con lo cual la equivalencia nos sirve de test (”no polinomial”) para saber si un número dado es primo o no.
Sive | 10 de Septiembre de 2008 | 17:50

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.
^DiAmOnD^ | 10 de Septiembre de 2008 | 21:10

M lo cambio ahora mismo. Dejo como enunciado lo que has puesto entre comillas en el comentario donde lo rectificas.
vengoroso | 11 de Septiembre de 2008 | 22:56

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
M | 11 de Septiembre de 2008 | 23:03

jejeje, ahí le has dado
^DiAmOnD^ | 12 de Septiembre de 2008 | 4:06

vengoroso yo no he sido quien ha estado leyendo por ahí…el problema es propuesto por alguien…(carita silbando :D)
Sive | 14 de Septiembre de 2008 | 19:23

¿Nadie se atreve con el problema o es que ya hemos mirado la solución todos?
M | 14 de Septiembre de 2008 | 20:05

bueno, Sive, por mi parte entendí zanjado el asunto entre los comentarios de vengoroso y Asier (en http://gaussianos.com/%C2%A1%C2%A1tenemos-dos-nuevos-primos-de-mersenne/#comments)