We are given that $p$ is a prime congruent to $1$ modulo $4$. The proof for the congruence

$$\left(\frac{p-1}{2}\right)!^2 \equiv (p-1)!\ (\textrm{mod}\ p)$$

is argued as follows:

Proof. Since we are given $p \equiv 1\ (\textrm{mod}\ 4)$, we have $p=4t+1$. By Wilson's theorem, it follows that

$$(4t)! \equiv -1\ (\textrm{mod}\ p)*$$

*I should probably note that proving the congruence in question is necessary to prove that $\left(\frac{p-1}{2}\right)!^2 \equiv -1\ (\textrm{mod}\ p)$, which warrants the use of Wilson's theorem. That part is clear to me.

Thus we want to show that

$$\left(\frac{p-1}{2}\right)!^2 \equiv (p-1)!\ (\textrm{mod}\ p) \quad \Longleftrightarrow \quad (2t)!^2 \equiv (4t)!\ (\textrm{mod}\ p)$$

Up to here is fair, but the author proceeds in the following manner

$$(4t)! = (2t)!\ (2t+1)(2t+2)\cdots(2t+2t)$$ $$\color{red}{= (2t)!\ (p-2t)(p-(2t-1))\cdots(p-1)}$$ $$\color{blue}{\equiv (2t)!\ (-2t)(-(2t-1))\cdots(-1)\ (\textrm{mod}\ p)}$$ $$\equiv (2t)!\ (-1)^{2t}(2t)! \equiv (2t)!^2\ (\textrm{mod}\ p)$$

with $2t=\frac{1}{2}(p-1)$. It is not apparent to me how we are able to jump from the red step to the blue step.

  • 1
    $\begingroup$ Is it because $p \equiv 0 \mod p$ so $p - a \equiv -a \mod p$ ? $\endgroup$
    – user348338
    Jun 27 '16 at 7:12
  • $\begingroup$ Proving the result does not require Wilson's Theorem. $\endgroup$ Jun 27 '16 at 7:14

Between the red step and the blue step, the author is "simplifying" each of the factors mod $p$. Specifically, since $p - 2t \equiv -2t \mod p$, $p-(2t-1) \equiv -(2t-1) \mod p$, and so on until $(p-1) \equiv -1 \mod p$, you can write

$$ (p-2t)(p-(2t-1)) \cdots (p-1) \equiv (-2t)(-(2t-1))\cdots(-1) \mod p$$

which is exactly the red-blue step.


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.