jueves, 16 de febrero de 2012

Problema del dia: Viernes

a) Sea $p$ un primo tal que $2p+1$ es primo, $p$ de la forma $4k+1$. Demuestra que $2$ es raiz primitiva modulo $2p+1$.
b) Sea $p$ primo. Determine el maximo grado de un polinomio $T(x)$ con coeficientes en $0,1,...,p-1$ y grado menor a $p$ que satisface $T(n)\equiv T(m) \mod{p}$ implica $m\equiv n \mod{p}$

21 comentarios:

Juan dijo...

(a) Le llamo q=2p+1. Si x es un divisor propio de q-1=2p, queremos que q no divida a $2^x-1$. Pero x sólo puede ser 1, 2, o p. Si es 1 o 2 quiero que q no divida a 1 ni a 3, lo cual es fácil pues si sí divide a alguno, q=3, p=1 y 1 no es primo. Así, basta probar que q no divide a $2^p-1$. Pero por la fórmula de Euler, $\left(\frac{2}{q} \right)\equiv 2^p$ módulo q, y como q=3(mod 4) se ve que éste valor es -1, por lo que q divide a $2^p+1$, no $2^p-1$, y acabamos. $\clubsuit$

Juan dijo...

Perdón, es q=3(mod 8), pues con mod 4 no es suficiente.

alberto dijo...

que es $á^1$ ?
deberia decir p?

Flavio dijo...

ya esta corregido, si debia decir $p$

Chuck dijo...

Supongamos que el orden de $2$ módulo $2p+1$ es $\sigma$, entonces como por el Teorema de Fermat $2^{2p+1-1}\equiv 1\pmod {2p+1}$, entonces $\sigma |2p$, ahora, veamos que $p\geq 2$ y por lo tanto $2p+1\geq 5$ así que $\sigma\neq 1,2$. Supongamos que $\sigma =p$ en cuyo caso usando el Símbolo de Legendre, el criterio de Euler nos dice que $\left(\frac{2}{2p+1}\right)\equiv 2^{p}\equiv 1\pmod {2p+1}$ pero sabemos que $p=4k+1$ así que $2p+1=8k+3$ y entonces es imposible, porque esto sólo ocurre con los primos de la forma $8n\pm 1$ por lo tanto $\sigma =2p$ y por lo tanto $2$ es raíz primitiva módulo $2p+1$.

jorge garza vargas dijo...

Sea $a$ el orden de $2$ $(mod 2p+1)$, entonces ya que $2p+1$ es primo, por el pequeño teorema de Fermat, $a|2p$, entonces $a=2,p,2p$, claramente $a$ no puede ser $2$, luego, es un hecho conocido que $\left(\frac{2}{q}\right)\equiv -1^{\frac{q^2-1}{8}}(mod q)$ y como $2p+1=8k+3$ entonces $2$ no es residuo cuadrtático y entonces $2^p\equiv -1(mod 2p+1)$ por lo que $a$ tampoco es $p$, por lo tanto $a=2p$ así que $2$ es raìz primitiva de $2p+1$.

jorge garza vargas dijo...

El polinomio $T(x)=x^{p-1}+x$ cumple por el pequeño teorema de Fermat que $T(a)\equiv T(b)(mod p)$ implica $a\equiv b(mod p)$, entonces el máximo grado que que puede tener $T$ menor a $p$ es $p-1$. ¿estoy entendiendo bien el enunciado del problema?

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Para el b) tengo que por Fermat, $x^{p-1}+x-1\equiv x \pmod{p}$, y ese polinomio cumple las condiciones.

Para el a) tengo que como $q=2p+1$ no es de la forma $8k\pm1$, entonces usando Legendre, tenemos que $\left(\frac{2}{p}\right)=-1$, y si tomamos a $P$ como el orden de $2$ en $\pmod{q}$, veremos que $q-1=2p$, así que $P$ divide a $2p$, y es fácil ver que $p\neq 1, 2$. Ahora, tampoco puede ser $p$ pues $2^{p}\equiv -1\pmod{q}$, y por lo tanto, $P=2p$, y tenemos que $2$ es raíz primitiva de $q$ como queríamos.

Adán dijo...

Y en el b) por ende, es mayor grado posible es $p-1$.

Adán dijo...

Y arriba debe decir $\left(\frac{2}{q}\right)$, no $\left(\frac{2}{p}\right)$.

Enrique dijo...

a) Demostrar que $2$ es raíz primitiva equivale a demostrar que su orden mod $2p+1$ es $2p$. Vemos que el orden de $2$ divide a $2p$, por lo que éste es $1,2,p$ o $2p$. Si fuera $1$ ó $2$, entonces $2p+1\mid 1$ ó $2p+1\mid 3$, respectivamente, lo cual es imposible. Si fuera $p$, $2^{p}\equiv 1$ (mod $2p+1$), de donde $2p+1\mid 2^{p}-1\Rightarrow 2p+1\mid 2^{\frac{(2p+1)-1}{2}}-1$. Por criterio de Euler, $2^{\frac{(2p+1)-1}{2}}\equiv \left(\frac{2}{2p+1}.\right)$, pero $2$ es residuo cuadrático módulo un primo $q$ si y sólo si $q\equiv \pm 1$ (mod 8), pero como $2p+1=2(4k+1)+1=8k+3\equiv 3$ (mod 8), $2$ no es residuo cuadrático módulo $2p+1$, de donde $2^{p}\equiv -1$, que es una contradicción. Por lo tanto, el orden de $2$ módulo $2p+1$ es $2p$, como queríamos.

Juan dijo...

b) $T(x)=x^{p-1}+x \equiv x+1$ (mod $p$) $\Rightarrow$ la respuesta es $p-1$. $\clubsuit$

JulioC dijo...
Este comentario ha sido eliminado por el autor.
JulioC dijo...

a.) Es conocido que 2 es residuo cuadrático de sólo primos de la forma 8k+1 ó 8k-1. Entonces 2 no es residuo cuadrático de $2p+1=8k+3$. Como $2^{2p}\equiv 1(mod 2p+1)$ por el teorema de Euler. El orden de 2 módulo 2p+1 es 2, p ó 2p.
Pero es claro que no puede ser 2.
Si orden de 2 módulo 2p+1 es p entonces
$2^p\equiv 1(mod 2p+1)$. Pero por el lema de gauss como $p=((2p+1)-1)/2$, 2 es residuo cuadrático de 2p+1. Contradicción.
Entonces $2$ es raiz primitiva modulo $2p+1$.

b) Esta bien escrito?
Porq según entiendo $T(x)=x^(p-1)-x$ funcionaría por el teorema de euler

Enrique dijo...

Creo que las soluciones del b) que han puesto hasta ahora están mal, por ejemplo $T(x)=x^{p-1}+x\equiv x+1$ pero sólo para $x$ no múltiplos de $p$, tenemos que $T(p)\equiv 0$ y $T(p-1)\equiv p-1+1\equiv 0$, por lo tanto no funciona.

Chuck dijo...

A cualquiera se le ocurre ese polinomio, pero como Enrique vio, no funciona del todo... lo que sucede es que $T(n)$ puede no tener constante y eso no afecta su propiedad así que se la podemos quitar, ahora, el problema es que si hay otro número para el cual $T(n)\equiv 0\pmod{p}$ que no sea múltiplo de $n$, entonces no funcionará... y tratar de encontrar un polinomio que permute $\{1,2,\dots,p-1\}$ módulo $p$ es más complicado...

Flavio dijo...

Si entendieron bien el problema b, pero el polinomio que dan no cumple, como dijo enrique

jorge garza vargas dijo...

Tienes razón enrique, buena observación.
A ver si no me equivoco. Sea $c$ un residuo tal que $1-4c$ no es residuo cuadrático $\pmod{p}$ (claramente $c$ existe). Demostraremos que $Q(x)=x^{p-1}+x^{p-2}+cx$ cumple.
Lema 1. Es un hecho conocido que si $a,b,c,d$ son residuos tales que $a+b\equiv c+d\pmod{p}$ y $ab\equiv cd\pmod{p}$ entonces $\{a,b\}=\{c,d\}$.
Lema 2. Es un hecho conocido que si $P(x)=ax^2+bx+c$ entonces $P(x)$ tiene solución $\pmod{p}$ si y solo si $b^2-4ac$ es residuo cuadrático $\pmod{p}$.
Regresando al problema, primero veamos que $Q(x)$ es inyectivo cuando su dominio es el conjunto reducido de residuos. Si $Q(x)\equiv Q(y)$ usando el pequeño teorema de Fermat tenemos que $x^{-1}+cx\equiv y^{-1}+cy$ entonces por el lema 1 $x=y$.
Ahora veamos que la única raíz de $Q(x)$ es $x=0$, eso es equivalente a ver que $x^{p-2}+x^{p-3}+c$ no tiene raíces $\pmod{p}$, pero viendo para cada $x$ el polinomio en términos de $x^{-1}$, vemos que lo anterior es equivalente a ver que $R(x)=x^2+x+c$ no tiene soluciones $\pmod{p}$ lo cual se sigue del lema 2 en conjunto con la construcción de $c$.
Entonces $Q(x)=0$ implica $x=0$ con lo que se concluye que $Q$ es inyectiva cuando se tiene como dominio el sistema completo de residuos. Y así $Q$ cumple lo pedido y tiene grado $p-1$.

Unknown dijo...

a. Tenemos que si no fuera raíz primitiva, entonces $2^2$ o $2^p$ serian 1 modulo $2p+1$, ya que solo $1$,$2$ y $p$ dividen a $2p$, y el caso uno implica los otros dos. Si $2^2$ es congruente con uno, entonces $3\equiv 0$mod $2p+1$ entonces $p=1$! Contradicción.
Asi que $2^p\equiv 1$. Pero por el teorema de euler, tenemos que entonces $2$ es residuo cuadratico, pero $2p+1=2(4k+1)+1=8k+3$ entonces no puede ser residuo cuadratico ya que 2 lo es si y solo si el primo es $\pm 1$ modulo 8.

b. Es facil ver que $\frac{1}{(i-1)(i-2)\cdots (i-(i-1)(i-(i+1)\cdots (i-p)}\equiv$ $\frac{(-1)^(i+1)}{(i-1)! (p-i)!}\equiv$ $\frac{(-1)^i (p-1)!}{(i-1)! (p-i)!}=\frac{(-1)^i(p-i+1)(p-i+2)\cdots (p-1)}{(i-1)!}$
$\equiv \frac{(-1)(i-1)!}{(i-1)!}\equiv -1$ modulo $p$

Supongamos que tenemos un polinomio que cumpla $T(x)$. Sea $y_i=T(i)$ la permutación de $i$ con $i=1,\ldots ,p$. Aplicando interpolación de lagrange sobre los puntos en modulo p $Q_i=(i,y_i)$ entonces calculando el coeficiente $x^{p-1}$ del polinomio, tenemos que es $\sum_{i}^{p} y_i\frac{1}{(i-1)(i-2)\cdots (i-(i-1)(i-(i+1)\cdots (i-p)}\equiv \sum_{i=1}^{p} -y_i\equiv \sum_{i=1}^{p} i$ $\equiv \frac{p(p+1)}{2}\equiv p\frac{p+1}{2}\equiv 0$. Asi que siempre es $0$. Por lo tanto, $T$ es de grado a lo más $p-2$. Tenemos que $T(x)=x^{p-2}$ cumple, ya que $T(0)=0$ y $T(r)=\frac{1}{r}$ para $p\not |r$, porlotanto si $T(a)\equiv T(b)$ sii $a\equiv b$ modulo $p$.

Publicar un comentario