1
$\begingroup$

My attempt:

$p \equiv 1 ( \operatorname{mod} 4) \iff (p-1)/2$ is even $\Rightarrow (-1)^{(p-1)/4} = ((-1)^{(p-1)/2}) ^{1/2} = 1.$

So we have to prove that $2 \cdot 4 \cdot 6 \cdot \dots \cdot (p-1) \equiv (\frac{p-1}{2})! \pmod p$ for $p \equiv 1 ( \operatorname{mod} 4)$.

RHS: $1 \cdot 2 \cdot 3 \cdot \dots \cdot \frac{p-1}2$; LHS: $2^{(p-1)/2}(1 \cdot 2 \cdot 3 \cdot \dots \cdot \frac{p-1}2)$. We just have to prove that $2^{(p-1)/2}\equiv 1$ mod $p$ ($p \equiv 1$ mod $4$). $p$ is prime, and thus we can say $ 2^{p-1} \equiv 1$ mod $p$ (Fermat's Little Theorem). So, $2^{(p-1)/2}\equiv \pm 1 \pmod p$.

What can I do now?

$\endgroup$
  • $\begingroup$ Your first line at least is not quite correct. For example, if $p = 5$, then $\left(-1\right)^{\left(p-1\right)/4} = \left(-1\right)^1 = -1$. The $1/2$ power result can be either the positive or negative root. Note, however, I haven't checked the rest of your question yet to see whether or not this is of any particular importance. $\endgroup$ – John Omielan Jan 28 '19 at 20:44
  • $\begingroup$ So, $ (-1)^{(p-1)/4} = \pm 1$, and at the end I find that $ 2^{(p-1)/2} = \pm 1$. Does that complete the proof? $\endgroup$ – Zachary Jan 28 '19 at 20:55
  • $\begingroup$ To complete the proof, you need to show that $\left(-1\right)^{\left(p-1\right)/4} \equiv 2^{\left(p-1\right)/2} \pmod p$. Thus, if $\left(-1\right)^{\left(p-1\right)/4} = 1$, then you need to prove that $2^{\left(p-1\right)/2} \equiv 1 \pmod p$. You need to also similarly handle the case where $\left(-1\right)^{\left(p-1\right)/4} = -1$. Although this seems to always be true, I haven't yet figured out a way to prove it. $\endgroup$ – John Omielan Jan 28 '19 at 21:45
1
$\begingroup$

We are given that

$$p \equiv 1 \pmod 4 \tag{1}\label{eq1}$$

The question doesn't state it explicitly, but it seems to assume that $p$ is a prime, e.g., for this to always work, plus as it also mentions using Fermat's Little Theorem. As the question basically already starts, we have that

$$2 \cdot 4 \cdot 6 \cdots \left(p - 1\right) = 2^{\left(p - 1\right)/2}\left(1 \cdot 2 \cdot 3 \cdots \cfrac{p - 1}{2}\right) = 2^{\left(p - 1\right)/2} \left(\cfrac{p - 1}{2}\right)! \tag{2}\label{eq2}$$

Thus, to prove

$$2 \cdot 4 \cdot 6 \cdots \left(p - 1\right) \equiv \left(-1\right)^{\left(p - 1\right)/4} \left(\cfrac{p - 1}{2}\right)! \pmod p \tag{3}\label{eq3}$$

we just need to prove that

$$\left(-1\right)^{\left(p - 1\right)/4} \equiv 2^{\left(p - 1\right)/2} \pmod p \tag{4}\label{eq4}$$

To do this, note that the second supplement to the law of quadratic reciprocity, such as stated in Legendre symbol and proven in Law of Quadratic Reciprocity, gives that

$$\left(\cfrac{2}{p}\right) = \left(-1\right)^{\frac{p^2 - 1}{8}} = \begin{cases} 1 & p \equiv 1 \text{ or } 7 \pmod 8 \\ -1 & p \equiv 3 \text{ or } 5 \pmod 8 \end{cases} \tag{5}\label{eq5}$$

Also, Legendre's original definition was by means of an explicit formula, where for $2$ it is that

$$\left(\cfrac{2}{p}\right) \equiv 2^{\left(p - 1\right)/2} \pmod p \tag{6}\label{eq6}$$

As such, consider $p \equiv 1 \pmod 4$ means $p \equiv 1 \text{ or } 5 \pmod 8$. In the first case, i.e, $p \equiv 1 \pmod 8$, from \eqref{eq5} and \eqref{eq6}, we have

$$2^{\left(p - 1\right)/2} \equiv 1 \pmod p \tag{7}\label{eq7}$$

Also, $p = 8k + 1$ for some integer $k$, so $\left(p - 1\right) / 4 = 2k$. Thus,

$$\left(-1\right)^{\left(p - 1\right)/4} = \left(-1\right)^{2k} = \left(\left(-1\right)^{2}\right)^k = 1^k \equiv 1 \pmod p \tag{8}\label{eq8}$$

Thus, \eqref{eq4} holds when $p \equiv 1 \pmod 8$. For the second case of $p \equiv 5 \pmod 8$, from \eqref{eq5} and \eqref{eq6}, we have

$$2^{\left(p - 1\right)/2} \equiv -1 \pmod p \tag{9}\label{eq9}$$

Also, $p = 8k + 5$ for some integer $k$, so $\left(p - 1\right) / 4 = 2k + 1$. Thus,

$$\left(-1\right)^{\left(p - 1\right)/4} = \left(-1\right)^{2k + 1} = \left(-1\right)^{2k}\left(-1\right) \equiv -1 \pmod p \tag{10}\label{eq10}$$

Thus, \eqref{eq4} also holds when $p \equiv 5 \pmod 8$. As both possible cases have been checked, we can conclude that \eqref{eq3} is true.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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