# Another Congruence Proof

I've been asked to attempt a proof of the following congruence. It is found in a section of my textbook with Wilson's theorem and Fermat's Little theorem. I've pondered the problem for a while and nothing interesting has occurred to me.

$1^23^2\cdot\cdot\cdot(p-4)^2(p-2)^2\equiv (-1)^{(p+1)/2} (\text{mod} p)$

-
Start from Wilson's theorem. Half of the terms look right... see what you can do with the other half. –  Qiaochu Yuan Jun 11 '12 at 5:11
–  Zander Jun 12 '12 at 12:25

HINT: For $p=11$:

\begin{align*} 10!&=(1\cdot10)(2\cdot9)(3\cdot8)(4\cdot7)(5\cdot6)\\ &=\Big(1\cdot(-1)\Big)\Big(-9\cdot9\Big)\Big(3\cdot(-3)\Big)\Big(-7\cdot7\Big)\Big(5\cdot(-5)\Big)\\ &=(-1^2)(-9^2)(-3^2)(-7^2)(-5^2)\\ &=(-1)^5\cdot1^2\cdot3^2\cdot5^2\cdot7^2\cdot9^2 \end{align*}

-

To Prove : $1^2.2^2.3^2....(p-1)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$

We know that
$$k \equiv -(p-k) \pmod p$$ Applying this repeatedly we will get $$2.4.6.......(p-1) \equiv (-1)^{\frac{p-1}{2}} 1.3.5.......(p-2) \pmod p$$ $$\implies 1.3.5.......(p-2) \equiv (-1)^{\frac{p-1}{2}} 2.4.6.......(p-1) \pmod p$$ $$\implies 1^2.3^2.5^2.......(p-2)^2 \equiv (-1)^{\frac{p-1}{2}} 1.2.3.4.5.6.......(p-1) \pmod p$$ $$\implies 1^2.3^2.5^2.......(p-2)^2 \equiv (-1)^{\frac{p-1}{2}} (p-1)! \pmod p$$ By Wilson's Theorem $$\implies 1^2.3^2.5^2.......(p-2)^2 \equiv (-1)^{\frac{p-1}{2}} (-1) \pmod p$$ $$\implies 1^2.3^2.5^2.......(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$$

-

Here $p$ must be an odd prime.

There are two cases to consider, $p\equiv 1 \pmod 4$ and $p\equiv 3 \pmod{4}$. We deal with the first case.

We know that $(p-1)!\equiv -1\pmod{p}$. Rearrange the numbers from $1$ to $p-1$, so that we get the odd numbers from $1$ on going up, interleaved with the even numbers from $p-1$ going down. For example, if $p=13$, we arrange the numbers from $1$ to $12$ in the order $1$, $12$, $3$, $10$, $5$, $8$, $7$, $6$, $9$, $4$, $11$, $2$.

In general the listing is $1$, $p-2$, $3$, $p-3$, $5$, $p-5$, and so on until at the end we get to $p-2$, followed by $p-(p-2)$. Now take the product, in that order, noting that $p-k\equiv -k \pmod{p}$.

We get that $$(p-1)!\equiv (1)(-1)(3)(-3)(5)(-5)\cdots (p-2)(-(p-2))\equiv -1\pmod{p}.\tag{1}$$ The number of even numbered entries in the product is $(p-1)/2$. These have minus signs in front of them. Gather the minus signs together. We get $$(-1)^{(p-1)/2} 1^23^25^2\cdots (p-2)^2 \equiv -1\pmod{p}.$$ Note that $(p-1)/2$ is even. So we get that
$$1^23^25^2\cdots (p-2)^2 \equiv -1\pmod{p}.$$ Now we are finished, since $-1=(-)^{(p+1)/2}$.

The argument for $p\equiv 3\pmod{4}$ is essentially the same. In fact the two arguments could be gathered into one. The main difference is that in $(1)$, the number of minus signs, which is $(p-1)/2$, now turns out to be odd. So we get $$-1^23^25^2\cdots (p-2)^2 \equiv -1\pmod{p}.$$ or equivalently $$1^23^25^2\cdots (p-2)^2 \equiv 1\pmod{p}.$$ Since in this case we have $(-1){(p+1)/2}=1$, again the result follows.

Remark: The above shows the useful result that if $p\equiv 1\pmod{4}$, then there is an $x$ such that $x^2\equiv -1\pmod{p}$. Indeed it gives an explicit expression for such an $x$. Regrettably, the expression is not computationally useful if $p$ is large.

-
p≡1(mod4) and p≡3(mod4), where is the mod 4 coming from? –  jmedsy Jun 11 '12 at 5:57
We have $(-1)^{(p+1)/2}=-1$ if $p$ is of the form $4k+1$, and $(-1)^{(p+1)/2}=1$ if $p$ is of the form $4k+3$, so $1$ versus $3$ is sort of built into the statement of the problem. If $p\equiv 1\pmod{4}$, we had an even number of $-1$'s after we had done our rearranging and replacing. If $p\equiv 3\pmod{4}$ we end up with an odd number of minus signs. –  André Nicolas Jun 11 '12 at 6:24
Note that (p−1)/2 is even. What if p = 7, for example? –  jmedsy Jun 11 '12 at 21:13
@jmedsy: I have added a few lines to the answer, to deal in somewhat more detail with $p\equiv 3\pmod{4}$. –  André Nicolas Jun 11 '12 at 21:24

An idea that, perhaps, will appeal to you besides the ones already given above:$$1^23^2\cdot\ldots\cdot (p-1)^2=\frac{\left(1\cdot 2\cdot\ldots\cdot (p-1)\right)^2}{\left(2\cdot 4\cdot\ldots\cdot (p-1)\right)^2}\,\,(**)$$Now we use Wilson's theorem, Fermat's Little Theorem and arithmetic modulo $p$: $$(**)\,\,=\frac{(-1)^2}{\left(2^{\frac{p-1}{2}}\right)^2\left(1\cdot 2\cdot\ldots\cdot\frac{p-1}{2}\right)^2}=\frac{1}{1\cdot\left(1\cdot 2\cdot\ldots\cdot\frac{p-1}{2}\right)^2} \,\,\,(***)$$

Let us now check more closely Wilson's theorem (again, arithmetic modulo $p$):$$-1=1\cdot 2\cdot\ldots\cdot\frac{p-1}{2}\cdot\frac{p+1}{2}\cdot\ldots\cdot (p-1)=$$$$=1\cdot 2\cdot\ldots\cdot\frac{p-1}{2}\left(-\frac{p-1}{2}\right)\cdot\ldots\cdots (-2)(-1)=$$$$=\left(-1\right)^{\frac{p-1}{2}}\left(1\cdot 2\cdot\ldots\cdot\frac{p-1}{2}\right)^2$$So: $$(1)\,\,p=3\pmod 4\Longrightarrow \frac{p-1}{2}\text{ is odd}\Longrightarrow (-1)^\frac{p-1}{2}=-1\Longrightarrow$$$$\Longrightarrow\,\,(***)=1$$$$(2)\,\,p=1\pmod 4\Longrightarrow \frac{p-1}{2}\text {is even}\,\Longrightarrow (-1)^{\frac{p-1}{2}}=1\Longrightarrow$$$$\Longrightarrow (***) =-1$$

-