1
$\begingroup$

$\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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – user724963
    Feb 15 '20 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.