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
    $\begingroup$ 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$. $\endgroup$ May 9 '14 at 14:20
  • $\begingroup$ @AndréNicolas thanks. i query this identity at math.stackexchange.com/q/787937/85100, to try to understand why it's natural $\endgroup$ May 9 '14 at 14:25
  • $\begingroup$ 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. $\endgroup$ May 9 '14 at 14:39
  • $\begingroup$ @MarcvanLeeuwen thanks. I blighted the directions. edited now $\endgroup$ May 9 '14 at 14:42
  • $\begingroup$ $ \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} $ ? $\endgroup$
    – cactus314
    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...

  • $\begingroup$ @frank-muer anything I can do to improve this answer? $\endgroup$
    – cactus314
    May 29 '14 at 20:47

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.