# 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)$

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

• The pairing $i$ with $p-i$ is very natural, recall for example the standard proof for the sum $1+2+\cdots+n$, where we pair $i$ with $(n+1)-i$. Modulo $p$, the number $p-i$ is better thought of as $-i$. May 9 '14 at 14:20
• @AndréNicolas thanks. i query this identity at math.stackexchange.com/q/787937/85100, to try to understand why it's natural May 9 '14 at 14:25
• Could you spell out what implication you mean with the forward direction? To me the conclusion of the forward direction would seem to be $p\equiv1\pmod4$, but that does not seem to be your conclusion. May 9 '14 at 14:39
• @MarcvanLeeuwen thanks. I blighted the directions. edited now May 9 '14 at 14:42
• $\big[ (\frac{p-1}{2})! \big]^2 \equiv -1 (\mod p)$ is a very nice identity, which we prove using various properties of mod $p$ arithmetic. What happens if we use a different starting different combinatorial identity mod $p$ ? Wostonholme's theorem states: $$\binom{2p}{p} \equiv 2 \mod p^3$$ How do we know the factor's of $p$ cancel out correctly in $\frac{(2p)!}{(p!)^2}$ ? May 15 '14 at 19:49

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

• @frank-muer anything I can do to improve this answer? May 29 '14 at 20:47