4
$\begingroup$

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)$

  • 0
    Exact duplicates: http://math.stackexchange.com/questions/4827/why-is-the-square-of-all-odds-less-than-an-odd-prime-p-congruent-to-1p http://math.stackexchange.com/questions/22399/if-p-is-an-odd-prime-prove-that-1232-52-p-22-equiv-1p1-2 http://math.stackexchange.com/questions/147438/32-52-ldots-p-22-equiv-1-fracp12-mathrmmod-p2012-06-12

4 Answers 4

5

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*}$

3

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.

  • 0
    @jmedsy: I have added a few lines to the answer, to deal in somewhat more detail with $p\equiv 3\pmod{4}$.2012-06-11
3

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$

2

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$