¿Por qué el aumento de$(p-1)/2$ no siempre es igual a$1$ en$\mathbb{Z}^*_p$? (Manipulación de poderes modulo p)

Question

tl;dr: ¿por qué se está planteando por $(p-1)/2$ no siempre es igual a$1$$\mathbb{Z}^*_p$?

Yo estaba estudiando en la prueba de por qué los generadores no tienen residuos cuadráticos y me encontré en un paso en la prueba que pensé que podría ser una buena pregunta que podría ayudar a otras personas en el futuro a la hora de recaudar los poderes modulo $p$.

Deje $p$ ser el primer y, como de costumbre, $\mathbb{Z}^*_p$ ser los enteros mod $p$ con matrices inversas.

Considere la posibilidad de elevar el generador de $g$ a la potencia de $(p-1)/2$:

$$g^{(p-1)/2}$$

entonces, yo estaba buscando un poco riguroso argumento (o muy buena intuición) sobre el por qué de que fue no siempre es igual a $1$ por fermat poco teorema (cuando digo siempre, me refiero a que, aún cuando NO suponga que el generador tiene una ecuación cuadrática de residuos).

es decir, ¿por qué es esta lógica errónea:

$$ g^{(p-1)/2} = (g^{(p-1)})^{\frac{1}{2}} = (1)^{\frac{1}{2}} \ (mod \ p)$$

para resolver el último paso encontrar un x tal que $1 = x \ (mod \ p)$. $x$ es, obviamente,$1$, con lo que finaliza el mal prueba de que la recaudación de nada a $(p-1)/2$ es siempre igual a $1$. Obviamente, esto no debería ser el caso, especialmente para un generador, ya que el único poder que debe rendir $1$ para un generador es $p-1$, de lo contrario, no puede generar uno de los elementos en el conjunto cíclico.

La razón por la que yo pensaba que esto era ilegal, era porque sólo se puede elevar a potencias de números enteros mod $p$ $1/2$ obviamente no es válida (ya que no es un número entero). También, si recuerdo correctamente, no todos los números en un conjunto tiene una k-ésima raíz, derecho? Y $1/2$ en realidad sólo significa plaza de enraizamiento...¿verdad? También, tal vez fue una anotación confusión donde el poder de la $1/2$ en realidad sólo significa una función/algoritmo que "se encuentra" a la inversa tal que $z = x^2 \ (mod \ p)$. Así que es ilegal el paso alegando que usted puede separar los poderes, porque en ese paso, sería elevar a la potencia de un elemento no permitido en el set?

Answer 1

Tenga en cuenta que$1$ tiene dos raíces cuadradas modulo$p$ if$p\gt 2$.

Así que de$g^{p-1}\equiv 1\pmod{p}$, concluimos que$$\left(g^{(p-1)/2}\right)^2\equiv 1\pmod{p},$ $ y por lo tanto$$g^{(p-1)/2}\equiv \pm 1\pmod{p}.$ $

Si$g$ es una raíz primitiva de$p$ y$p\gt 2$, entonces$g^{(p-1)/2}\equiv 1\pmod{p}$ no es posible, así que$g^{(p-1)/2}\equiv -1\pmod{p}$.

Answer 2

Lo he intentado aplicar un método para calcular los $k$-th raíces fuera de su ámbito de aplicabilidad.

Tambien es cierto que si $\,(k,p\!-\!1) = 1\,$ $\,{\rm mod}\ p\!-\!1\!:\ \,k^{-1}\! = \color{#c00}{1/k \equiv i}\,$ existe, por lo $\ g^{\Large{j/k}} \equiv (g^{\Large j})^{\large{ \color{#c00}{1/k}}} \equiv g^{\Large j\color{#c00}i}.$

Pero esto no se aplica en su caso $\,k =2\ $ desde $\,2\mid p\!-\!1\,$$\,(k,p\!-\!1) = (2,p\!-\!1) = 2\ne 1$.

Esencialmente, usted está tratando de invertir $\,2\,$ en el ring $\,\Bbb Z/(p\!-\!1),\,$ donde $\,2\,$ es un cero-divisor, ya que $\,2\mid p\!-\!1.\, $, Esto es una especie de anillo de la teoría de la generalización de el pecado de la división por cero, ya que el único anillo con una invertible cero divisor es el trivial anillo de $\{0\}.$

Answer 3

Tomar raíces en la aritmética modular no funciona.

Por ejemplo, compruebe esto:

$9 \equiv 4 \pmod 5$, Pero$2 \equiv 3 \pmod 5$, no se mantiene.

Ahora al problema. Si$(g,p) = 1$, entonces

ps

Esto es porque:

Unesdoc.unesco.org unesdoc.unesco.org

Obviamente, sólo uno de los factores puede ser 0 modulo$$g^{\frac{p-1}{2}} \equiv 1 \pmod p \text { or } g^{\frac{p-1}{2}} \equiv -1 \pmod p$.