Why is raising by $(p-1)/2$ not always equal to $1$ in $\mathbb{Z}^*_p$? (Manipulating powers modulo p)

Question

tl;dr: why is raising by $(p-1)/2$ not always equal to $1$ in $\mathbb{Z}^*_p$?

I was studying the proof of why generators do not have quadratic residues and I stumbled in one step on the proof that I thought might be a good question that might help other people in the future when raising powers modulo $p$.

Let $p$ be prime and as usual, $\mathbb{Z}^*_p$ be the integers mod $p$ with inverses.

Consider raising the generator $g$ to the power of $(p-1)/2$:

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

then, I was looking for a somewhat rigorous argument (or very good intuition) on why that was not always equal to $1$ by fermat's little theorem (when I say always, I mean, even when you do NOT assume the generator has a quadratic residue).

i.e. why is this logic flawed:

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

to solve the last step find an x such that $1 = x \ (mod \ p)$. $x$ is obviously $1$, which completes the wrong proof that raising anything to $(p-1)/2$ is always equal to $1$. This obviously should not be the case, specially for a generator since the only power that should yield $1$ for a generator is $p-1$, otherwise, it can't generate one of the elements in the cyclic set.

The reason that I thought that this was illegal was because you can only raise to powers of integers mod $p$ and $1/2$ is obviously not valid (since its not an integer). Also, if I recall correctly, not every number in a set has a k-th root, right? And $1/2$ actually just means square rooting...right? Also, maybe it was a notational confusion where to the power of $1/2$ actually just means a function/algorithm that "finds" the inverse such that $z = x^2 \ (mod \ p)$. So is the illegal step claiming that you can separate the powers because at that step, you would be raising to the power of an element not allowed in the set?

Answer 1

Note that $1$ has two square roots modulo $p$ if $p\gt 2$.

So from $g^{p-1}\equiv 1\pmod{p}$, we conclude that $$\left(g^{(p-1)/2}\right)^2\equiv 1\pmod{p},$$ and therefore $$g^{(p-1)/2}\equiv \pm 1\pmod{p}.$$

If $g$ is a primitive root of $p$, and $p\gt 2$, then $g^{(p-1)/2}\equiv 1\pmod{p}$ is not possible, so $g^{(p-1)/2}\equiv -1\pmod{p}$.

Answer 2

Taking roots in modular arithmetics doesn't work.

For example check this:

$9 \equiv 4 \pmod 5$, but $2 \equiv 3 \pmod 5$, doesn't hold.

Now to the problem. If $(g,p) = 1$, then

$$g^{\frac{p-1}{2}} \equiv 1 \pmod p \text { or } g^{\frac{p-1}{2}} \equiv -1 \pmod p$$

This is because:

$$g^{p-1} \equiv 1 \pmod p$$ $$g^{p-1} - 1\equiv 0 \pmod p$$ $$(g^{\frac{p-1}{2}} - 1)(g^{\frac{p-1}{2}} + 1) \equiv 0 \pmod p$$

Obviously only one of the factors can be 0 modulo $p$.

Answer 3

You've attempted to apply a method of computing $k$-th roots outside its domain of applicability.

It is true that if $\,(k,p\!-\!1) = 1\,$ then $\,{\rm mod}\ p\!-\!1\!:\ \,k^{-1}\! = \color{#c00}{1/k \equiv i}\,$ exists, so $\ g^{\Large{j/k}} \equiv (g^{\Large j})^{\large{ \color{#c00}{1/k}}} \equiv g^{\Large j\color{#c00}i}.$

But this does not apply in your case $\,k =2\ $ since $\,2\mid p\!-\!1\,$ so $\,(k,p\!-\!1) = (2,p\!-\!1) = 2\ne 1$.

Essentially you are attempting to invert $\,2\,$ in the ring $\,\Bbb Z/(p\!-\!1),\,$ where $\,2\,$ is a zero-divisor, since $\,2\mid p\!-\!1.\, $ This is a sort of ring-theoretic generalization of the sin of dividing by zero, since the only ring with an invertible zero-divisor is the trivial ring $\{0\}.$