# A question involving orders modulo a prime and $\phi(p) = p - 1$

$$\DeclareMathOperator{\ord}{ord}$$Notation. Let $$e(p, B)$$ stand for the exponent of the prime $$p$$ in the prime factorization of the natural number $$B$$. If $$p$$ doesn't appear in the prime factorization of $$B$$, then $$e(p,B) = 0$$.

Question. Let $$x, p$$ be coprime and $$p$$ an odd prime. If $$e(2,\ord(x,p)) = e(2, p - 1)$$, is it true that $$x^{(p-1)/2} = -1 \bmod{p}$$? I don't know the answer, but I would think so. (I haven't managed to prove it and I'm not seeing it with clarity, so perhaps it is not true.)

What do I know? I know that $$e(2,\ord(x,p)) = e(2, p - 1)$$, then $$x^{(p - 1)/2} \bmod{p}$$ cannot be 1 because $$(p - 1)/2$$ is not a multiple of $$\ord(x,p)$$. (By dividing $$(p - 1)$$ by $$2$$, we removed the last factor of $$2$$ that would still make $$(p - 1)$$ a multiple of $$\ord(x,p)$$).

What I don't know. Although I see $$x^{(p - 1)/2} \neq 1 \bmod{p}$$, I don't see why it is always $$x^{(p - 1)/2} = -1 \bmod{p} = (p - 1) \bmod{p}$$.

Solution after @CardboardBox's answer. Applying Fermat's little theorem, we know $$y = x^{(p-1)/2}$$ satisfies $$y^2 \equiv 1 \bmod{p}$$ and that implies $$(y - 1)(y + 1) \equiv 0 \bmod{p}$$. That leads to the conclusion $$y \equiv \pm 1 \bmod{p}$$ which means I can't say for sure $$y \equiv -1 \bmod{p}$$. However, in the original problem, we know $$y = x^{(p-1)/2} \bmod{p}$$ cannot be 1. Therefore, $$y \equiv -1 \bmod{p}$$ is the only possibility left.

The element $$y = x^{(p-1)/2}$$ satisfies $$y^2 \equiv 1 \bmod p$$ by Fermat's little theorem. Then $$(y-1)(y+1) \equiv 0 \bmod p$$, and so $$y \equiv \pm 1 \bmod p$$.
• I see that $y = x^{(p-1)/2}$ satisfies $y^2 \equiv 1 \bmod{p}$ by Fermat's little theorem and I see that implies $(y - 1)(y + 1) \equiv 0 \bmod{p}$. That leads to the conclusion $y \equiv \pm 1 \bmod{p}$ which means I can't say for sure $y \equiv -1 \bmod{p}$. However, in the original problem, we know $y = x^{(p-1)/2} \bmod{p}$ cannot be 1. Therefore, $y \equiv -1 \bmod{p}$ is the only possibility left. Thanks! Feb 15 '20 at 23:43