1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .