Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
    
add comment

4 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.