Ground plan of Backward direction (<=) - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$

276 Views Asked by At

Apply the identity $p-i \equiv -i \mod p$ for $i=1, \ldots$ to the pink factors

$ \begin{align} \color{seagreen}{ (p-1)! } = 1\times 2\times\cdots\times \dfrac{p-1}{2} & \times \quad \color{magenta}{\dfrac{p+1}{2} \times\cdots\times(p-2)\times(p-1)}\ \\ = \quad \dfrac{p-1}{2}! \quad & \times \quad \color{magenta}{ \dfrac{p-1}{2} \times\cdots\times(2)\times(1) \times \quad (-1)^{ \dfrac{p-1}{2}} } \\ & \equiv \color{seagreen}{ ((\frac{p-1}{2})!)^{2} \cdot (-1)^{ \frac{p-1}{2} } } \mod p . \end{align} $

(1) Why start with $(p - 1)!$ ? How can you prefigure this?

(2) Then how can you prefigure to write $(p - 1)!$ with $ \dfrac{p-1}{2} \times \quad \color{magenta}{ \dfrac{p+1}{2} }$ in the middle?

(3) How can you prefigure to use the trick $p-i \equiv -i \mod p $ ?

Now Wilson's Theorem is $\color{seagreen}{ (p-1)! } \equiv -1 \mod p$ therefore $ \color{seagreen}{ ((\frac{p-1}{2})!)^{2} \cdot (-1)^{ \frac{p-1}{2} } } \equiv -1 \mod p$. Implying $(\dfrac{p-1}{2}!)^{2}\equiv(-1)^{\frac{p+1}{2}} \quad (\#)$.

If $p\equiv 1 \mod 4$ then there exists an natural number n such that $4n = p - 1$. Hence $\dfrac{p-1}{2} = \dfrac{(4n + 1)-1}{2}$, an even number.

$\frac{p-1}{2}$ even implies $(\frac{p-1}{2}!)^{2}\equiv-1$, by reason of $(\#)$. Thence $x=\frac{p-1}{2}!$ solves $x^{2}+1\equiv 0 \mod p$ .

Origin - Elementary Number Theory, Jones, p71, Theorem 4.6

1

There are 1 best solutions below

1
On

Here is problem I liked on math.SE: look at Primes congruent to 1 mod 6

a prime $p$ can be written in the form $p = a^2 + ab + b^2 $ for some $a,b \in \mathbb{Z}$ iff $p \equiv 1 \mod 6$

One part of the solution says it is elementary to show there exists an integer $d$ such that $d^2 \equiv -3 \mod p$. This was not so "elementary to me", but we can prove it using your factorial identity.

Since $p = 6k+1$ we have $6$ divides $ p-1 $ which is the size of $\mathbb{Z}_p^\times$. In particular

$$ \frac{p-1}{3} \in \mathbb{Z}$$

We have a cube root of unity $ z $

Then - mysteriously - we set $z = \frac{-1+d}{2}$ so that $z^3 = \left( \tfrac{-1+d}{2} \right)^3 = \tfrac{-1+3d-3d^2 + d^3}{8} \equiv -1 (\mod p)$.

Notice the algebraic identity - regardless of taking mod $ p$

$$ -9+3d-3d^2 + d^3 = (d^2 + 3)(d-3) \equiv 0 \mod p$$

Therefore either $d \equiv 3 \mod p$ - corresponding to $z=1$ or $d^2 \equiv - 3 \mod p$.


We can't really say what the cube root of unity would be in terms of the factorial...