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.

Let $p$ be a prime, $p \equiv 3 \pmod 4$. Prove that $\frac{p-1}{2}! \equiv \pm 1 \pmod p$.

This is an exercise in one of my lecture notes. I couldn't seem to figure out how to do it. We've just covered Wilson's Theorem, Euler's phi function, and the set of least-modulus residues.

Would appreciate a solution. Lecturer doesn't provide answers unless I arrange a consultation session.

share|improve this question
add comment

5 Answers 5

up vote 3 down vote accepted

I will give a concrete example, and you can do the rest. Let $p=19$.

Note that $18\equiv -1\pmod{19}$. Also, $17\equiv -2\pmod{19}$, and $16\equiv -3\pmod{19}$, and so on. Finally, $10\equiv -9\pmod{19}$.

Thus $$18!\equiv \left[(1)(2)(3)\cdots(9)\right]\left[(-9)(-8)(-7)\cdots (-1)\right]\pmod{19}.$$ It follows that $(9!)^2 (-1)^9 \equiv 18!\pmod{19}$.

By Wilson's Theorem, we have $18!\equiv -1\pmod {19}$. Also, $(-1)^9=-1$. We conclude that $$(9!)^2 \equiv 1\pmod{19}.$$ It follows that $9!\equiv \pm 1\pmod{19}$.

The general case is essentially the same. The key fact is that $\dfrac{p-1}{2}$ is odd, so we get an odd number of $-1$.

share|improve this answer
    
In the general case, $\frac{p-1}{2}$ isn't odd though? e.g. p = 17 –  confused Sep 18 '12 at 1:15
    
Oh! but it is, when p $\equiv$ 3(mod 4). I see! –  confused Sep 18 '12 at 1:17
    
Yes, the condition that $p$ is of the form $4k+3$ is necessary for the argument to go through. The result is simply falso if $p\equiv \pmod{4}$. –  André Nicolas Sep 18 '12 at 1:20
add comment

Since $p$ is odd, $p-1$ is even. Note that $\frac{p-1}{2}$ is odd. Now the product of the numbers $1$ through $p-1$ (mod $p$) is congruent to

\begin{equation} 1 \times 2 \times \cdots \times \frac{p-1}{2} \times -1 \times -2 \times \cdots \times -\frac{p-1}{2} = - [(\frac{p-1}{2})!]^2 \end{equation}

Pairing each $i \in \{2, \cdots, p-2\}$ with its inverse mod $p$, we get $1 \times \cdots \times p-1 \equiv -1$ (mod $p$). Thus, $[(\frac{p-1}{2})!]^2 \equiv 1$ (mod $p$), and so $(\frac{p-1}{2})! \equiv \pm 1$ (mod $p$).

share|improve this answer
add comment

$\begin{eqnarray} {\bf Hint}\ \ \mod\ 7\!:\ -1 \,\equiv\, 6! \,&\equiv&\, 1\cdot 2\cdot 3\cdot\ \ \: 4&\cdot&\ \ \: 5&\cdot&\ \ \: 6\\ &\equiv&\, 1\cdot 2\cdot 3\cdot -3&\cdot& -2&\cdot& -1\\ &\equiv&\, -\, 3!^2\end{eqnarray}$

Hence $\rm\:3!^2\equiv1\:\Rightarrow\:3!\,\equiv\, \pm1,\:$ since, in a field, $\rm\:x^2 = 1 \iff (x\!-\!1)(x\!+\!1)=0\iff x = \pm 1.$

Remark $\ $ The above method of pairing up each factor with its negation (additive inverse) is a prototypical example of exploiting reflection (involution) symmetry.

share|improve this answer
add comment

Suppose that $\varpi=\frac{1}{2}(p-1).$ By $$(p-1)!=1\cdot2\cdots\frac{1}{2}(p-1)\{p-\frac{1}{2}(p-1)\}\{p-\frac{1}{2}(p-3)\}\cdots(p-1)\equiv(-1)^\varpi(\varpi!)^2(\bmod p),$$ it follows, by Wilson's theorem, that $$(\varpi)^2\equiv(-1)^{\varpi-1}(\bmod p).$$ Now we need to distinguish the two cases $p=4n+1$ and $p=4n+3$.

If $p=4n+3$ as in your question, then $$(\varpi!)^2\equiv1(\bmod p),$$ $$\varpi!\equiv\pm1(\bmod p).$$ Since $-1$ is anon-residue of $p$, thr sign in the above conruence ispositive or negative according as $\varpi!$ is a residue or non-residue of $p$.

As we knew it, a product of two residues or non-residues of $p$ is also a residue, while the product of one residue and a non-residue of $p$ is no longer a residue. Therefore, the sign is positive or negative according as the number of non-residues of $p$ less than $\frac{1}{2}p$ is even or odd.

The case $p=4n+1$ remains nearly the same argument.

share|improve this answer
add comment

Since $x\equiv-1\cdot(p-x)\pmod{p}$, we have $$ \color{#C00000}{1}\cdot\color{#00A000}{2}\cdot\color{#0000FF}{3}\cdots\color{#E07C00}{\frac{p-1}{2}}\equiv(-1)^{(p-1)/2}\color{#E07C00}{\frac{p+1}{2}}\cdots\color{#0000FF}{(p-3)}\cdot\color{#00A000}{(p-2)}\cdot\color{#C00000}{(p-1)}\tag{1} $$ multiply both sides of $(1)$ by the left side of $(1)$, then use Wilson's Theorem $$ \begin{align} {\large\left(\tfrac{p-1}{2}!\right)^2} &\equiv(-1)^{(p-1)/2}(p-1)!\\ &\equiv-1\cdot-1\\ &\equiv1\pmod{p}\tag{2} \end{align} $$ and since $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, $(2)$, which is $\left(\tfrac{p-1}{2}!-1\right)\left(\tfrac{p-1}{2}!+1\right)\equiv0\pmod{p}$, implies $$ {\large\tfrac{p-1}{2}!}\equiv\pm1\pmod{p}\tag{3} $$

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.