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}$
jueves, 16 de febrero de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
21 comentarios:
(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$
Perdón, es q=3(mod 8), pues con mod 4 no es suficiente.
que es $á^1$ ?
deberia decir p?
ya esta corregido, si debia decir $p$
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$.
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$.
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?
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.
Y en el b) por ende, es mayor grado posible es $p-1$.
Y arriba debe decir $\left(\frac{2}{q}\right)$, no $\left(\frac{2}{p}\right)$.
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.
b) $T(x)=x^{p-1}+x \equiv x+1$ (mod $p$) $\Rightarrow$ la respuesta es $p-1$. $\clubsuit$
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
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.
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...
Si entendieron bien el problema b, pero el polinomio que dan no cumple, como dijo enrique
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$.
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