Proving something with Wilson theorem

Question

I need to prove that $x^2\equiv -1\pmod p$ if $p=4n+1$.

($p$ is prime of course...)

I need to use Wilson theorem.

Answer 1

We have, $p-r\equiv-r\pmod p$

Putting $r=1,2,\cdots,\frac{p-1}2$ and multiplying we get $$\prod_{1\le r\le \frac{p-1}2}(p-r)\equiv(-1)^{\frac{p-1}2}\prod_{1\le r\le \frac{p-1}2} r$$

Multiplying either sides by $\prod_{1\le r\le \frac{p-1}2} r$

$$(p-1)!\equiv(-1)^{\frac{p-1}2}\left(\prod_{1\le r\le \frac{p-1}2} r\right)^2\pmod p$$

Wilson theorem says: $(p-1)!\equiv-1\pmod p$

If $p=1+4n, \frac{p-1}2=2n$ which is even $\implies (-1)^{\frac{p-1}2}=\cdots$

Answer 2

The following argument is closely related to the one given by lab bhattacharjee, but is easier to type. It goes back at least to Dirichlet.

Note that for every $x$ between $1$ and $p-1$, there is a unique $y$ such that $xy\equiv -1\pmod{p}$: for $y$ is just the negative of the inverse of $x$.

Call the $y$ such that $xy\equiv -1\pmod{p}$ the partner of $x$. (Dirichlet did not use the term partner, that is a more modern notion.)

We want to show that there is an $x$ which is its own partner. (There are actually two.) Such an $x$ will satisfy $x^2\equiv -1\pmod{p}$.

Suppose to the contrary that no one is his own partner. Then the numbers $1$ to $p-1$ are divided into $2n$ couples, each of which has product $\equiv -1\pmod{p}$. Thus $(p-1)!\equiv (-1)^{2n}\equiv 1\pmod{p}$. This contradicts Wilson's Theorem, and the result follows.

Remark: The same idea can be used to show that if $p$ is of the form $4n+3$, then the congruence $x^2\equiv -1\pmod{p}$ has no solution. (There are simpler ways to do that.)

For it is easy to see if the congruence $x^2\equiv -1\pmod{p}$ has a solution $s$, then it has exactly two solutions, $s$ and $-s$. Then $(s)(-s)\equiv 1\pmod{p}$. The other $4n$ numbers between $1$ and $p-1$ are divided into $2n$ pairs of partners, each of which has product congruent to $-1$. Thus $(p-1)!\equiv (-1)^{2n}(s)(-s)\equiv 1\pmod{p}$, again contradicting Wilson's Theorem.