Solving the following congruence

41 Views Asked by At

Let $p \equiv 1$ (mod 4) be a prime. Show that $a = \left(\frac{p − 1}{2}\right)!$ satisfies $a^2 \equiv −1$ (mod $p$)

By Wilson's Theorem, $(p − 1)! ≡ −1$ (mod $p$).

If we multiply together the (nonzero) least residues of $p$, we get $a = ((p − 1)/2)!$ and $b$ is the product of the integers $c$ with $p/2 < c < p$. Replacing the factors $c$ in this last product by $c' = c − p ≡ c$, so that $−p/2 < c' < 0$. Then the product of these factors $c'$ is $(−1)^{(p−1)/2} ((p − 1)/2)!)$, so $b \equiv (−1)^{(p−1)/2}a$ (mod p).

I'm struggling from here to get to the end result, is so far so good?

1

There are 1 best solutions below

0
On BEST ANSWER

Multiply $a$ on both sides.

$$ab \equiv (−1)^{(p−1)/2} a^2 \pmod p$$

Since $p \equiv 1 \pmod 4$, $\dfrac{p-1}{2}$ is even, so the factor $(-1)^{(p-1)/2}$ can be omitted.

From the definitions of $a$ and $b$, $ab = (p-1)!$, so apply Wilson's Theorem at the last step of the proof (instead of the first step) to show that $-1$ is a quadratic residue $\mod p$ when $p \equiv 1 \pmod 4$.

$$a^2 \equiv -1 \pmod p$$