Primes P such that ((P-1)/2)!=1 mod P

Question

I was looking at Wilson's theorem: If $P$ is a prime then $(P-1)!\equiv -1\pmod P$. I realized this implies that for primes $P\equiv 3\pmod 4$, that $\left(\frac{P-1}{2}\right)!\equiv \pm1 \pmod P$.

Question: For which primes $P$ is $\left(\frac{P-1}{2}\right)!\equiv 1\pmod P$?

After convincing myself that it's not a congruence condition for $P,$ I found this sequence in OEIS. I'd appreciate any comments that shed light on the nature of such primes (for example, they appear to be of density 1/2 in all primes that are $3\bmod 4$).

Thanks,

Jacob

Answer 1

I am a newcomer here. If p >3 is congruent to 3 mod 4, there is an answer which involves only $p\pmod 8$ and $h\pmod 4$, where $h$ is the class number of $Q(\sqrt{-p})$ . Namely one has $(\frac{p-1}{2})!\equiv 1 \pmod p$ if an only if either (i) $p\equiv 3 \pmod 8$ and $h\equiv 1 \pmod 4$ or (ii) $p\equiv 7\pmod 8$ and $h\equiv 3\pmod 4$.

The proof may not be original: since $p\equiv 3 \pmod 4$, one has to determine the Legendre symbol

$${{(\frac{p-1}{2})!}\overwithdelims (){p}} =\prod_{x=1}^{(p-1)/2}{x\overwithdelims (){p}}=\prod_{x=1}^{(p-1)/2}(({x\overwithdelims (){p}}-1)+1).$$ It is enough to know this modulo 4 since it is 1 or -1. By developping, one gets $(p+1)/2+S \pmod 4$, where $$S=\sum_{x=1}^{(p-1)/2}\Bigl({x\over p}\Bigr).$$ By the class number formula, one has $(2-(2/p))h=S$ (I just looked up Borevich-Shafarevich, Number Theory), hence the result, since $\Bigl({2\over p}\Bigr)$ depends only on $p \pmod 8$.

Edit: For the correct answer see KConrad's post or Mordell's article.

Answer 2

There is some history to this question. Dirichlet observed (see p. 275 of ``History of the Theory of Numbers,'' Vol. 1) that since we already know $(\frac{p-1}{2})! \equiv \pm 1 \bmod p$, computing modulo squares gives $(\frac{p-1}{2})! \equiv (-1)^{n} \bmod p$, where $n$ is the number of quadratic nonresidues mod $p$ which lie between 1 and $(p-1)/2$.

Jacobi (pp. 275-276 in Dickson's book) determined $n \bmod 2$ in terms of the class number $h_p$ of ${\mathbf Q}(\sqrt{-p})$, for $p \equiv 3 \bmod 4$ and $p \not= 3$. By the class number formula, $$ \left(2-\left(\frac{2}{p}\right)\right)h_p = r-n, $$ where $r$ is the number of quadratic residues from 1 to $(p-1)/2$. Also $r + n = (p-1)/2$, so $$ 2n = \frac{p-1}{2} - \left(2 - \left(\frac{2}{p}\right)\right)h_p. $$ In particular, $h_p$ is odd when $p \equiv 3 \bmod 4$.

Taking cases if $p \equiv 3 \bmod 8$ and $p \equiv 7 \bmod 8$, we find both times that $n \equiv (h_p+1)/2 \bmod 2$, so $$ \left(\frac{p-1}{2}\right)! \equiv (-1)^{(h_p+1)/2} \bmod p. $$

This shows why getting precise statistics on when the congruence has 1 on the right side will be hard.

Answer 3

The following is a relevant classical paper:

Mordell, L. J. The congruence $(p-1/2)!\equiv ±1$ $({\rm mod}$ $p)$. Amer. Math. Monthly 68 1961 145--146.

http://alpha.math.uga.edu/~pete/Mordell61.pdf

Put $((p-1)/2)!\equiv(-1)^a\ (\text{mod}\,p)$, where $p$ is a prime $\equiv 3\ (\text{mod}\,4)$. The author proves the following result. If $p\equiv 3\ (\text{mod}\,4)$ and $p>3$, then $$ a\equiv{\textstyle\frac 1{2}}\{1+h(-p)\}\quad(\text{mod}\,2), \tag1 $$ where $h(-p)$ is the class number of the quadratic field $k(\surd-p)$ [$\mathbb{Q}(\sqrt{-p})$ must be meant here. --PLC]. The author points out that (1) follows easily from a result of Dirichlet; also that Jacobi had conjectured an equivalent result before the class number formula was known. (MathReview by L. Carlitz)

Answer 4

This is an attempt to justify the answer $1/2$ based on the Cohen-Lenstra heuristics. There will be a lot of nonsensical steps, and I am not an expert, so this should be viewed with caution.

As is observed above, this is equivalent to determining $h(p) \mod 4$, where $h(p)$ is the class number of $\mathbb{Q}(\sqrt{-p})$. Since $p$ is odd and $3 \mod 4$, the only ramified prime in $\mathbb{Q}(\sqrt{-p})$ is the principal ideal $(\sqrt{-p})$. Thus, there is no $2$-torsion in the class group and $h(p)$ is odd.

For any odd prime $q$, let $a(q,p)$ be the power of $q$ which divides $h(p)$. We want to compute the average value of $$\prod_{q \equiv 3 \mod 4} (-1)^{a(q,p)}.$$

First nonsensical step: Let's pretend that the CL-heuristics work the same way for the odd part of the class group of $\mathbb{Q}(\sqrt{-p})$, that they do for the odd part of the class group of $\mathbb{Q}(\sqrt{-D})$. We just saw above that the fact that $p$ is prime constrains the $2$-part of the class group; this claim says that it does not effect the distribution of anything else.

Then we are supposed to have: $$P(a(q,p)=0) = \prod_{i=1}^{\infty} (1-q^{-i}) = 1-1/q +O(1/q^2),$$ $$P(a(q,p)=1) = \frac{1}{q-1} \prod_{i=1}^{\infty} (1-q^{-i}) = 1/q +O(1/q^2),$$ and $$P(a(q,p) \geq 2) = O(1/q^2).$$

If you believe all of the above, then the average value of $(-1)^{a(p,q)}$ is $ 1-2/q+O(1/q^2)$.

Second nonsensical step: Let's pretend that $a(q,p)$ and $a(q',p)$ are uncorrelated. Furthermore, let's pretend that everything converges to its average value really fast, to justify the exchange of limits I'm about to do.

Then $$E \left( \prod_{q \equiv 3 \mod 4} (-1)^{a(q,p)} \right) = \prod_{q \equiv 3 \mod 4} \left( 1- 2/q + O(1/q^2) \right)$$.`

The right hand side is zero, just as if $h(p)$ were equally like to be $1$ or $3 \mod 4$.

Answer 5

Apologies for repeating some information in my reply to question 121678, which I came across before seeing this one.

Several previous answers already explain the connection to the class number. It can be added that the value of $h(-p)$ was investigated by Louis C. Karpinski in his doctoral dissertation (Mathematischen und Naturwissenschaftlichen Facultät der Kaiser Wilhelms-Universität zu Strassburg, 1903), published as “Über die Verteilung der quadratischen Reste,” Journal für die Reine und Angewandte Mathematik 127 (1904): 1–19. Karpinski proved a collection of formulae (all of which assume $p > 3$) involving sums over Legendre symbols, and showed that the most concise sums possible contain only $\lfloor p/6 \rfloor$ terms:

\begin{equation} \left\{ 2 - \left( \frac{2}{p} \right) \right\} h(-p) = \sum_{k=1}^{(p-1)/2} \left( \frac{k}{p} \right) \quad (p \equiv 3 \bmod{4}); \end{equation}

\begin{equation} \left\{ 3 - \left( \frac{3}{p} \right) \right\} h(-p) = 2 \sum_{k=1}^{\lfloor p/3 \rfloor} \left( \frac{k}{p} \right) \quad (p \equiv 3 \bmod{4}); \end{equation}

\begin{equation} \left\{ 2 - \left( \frac{2}{p} \right) \right\} h(-p) = \sum_{k=\lfloor p/4 \rfloor +1}^{(p-1)/2} \left( \frac{k}{p} \right) (p \equiv 3 \bmod{8}); \end{equation}

\begin{equation} \left\{ 2 - \left( \frac{2}{p} \right) \right\} h(-p) = \quad \sum_{k=1}^{\lfloor p/4 \rfloor} \quad \left( \frac{k}{p} \right) (p \equiv 7 \bmod{8}); \end{equation}

\begin{equation} \left\{ 1 + \left( \frac{2}{p} \right) + \left( \frac{3}{p} \right) - \left( \frac{6}{p} \right) \right\} h(-p) = 2 \sum_{k=1}^{\lfloor p/6 \rfloor} \left( \frac{k}{p} \right) \quad (p \equiv 7, 11, 23 \bmod{24}); \end{equation}

\begin{equation} \left\{ 1 + \left( \frac{2}{p} \right) + \left( \frac{3}{p} \right) - \left( \frac{6}{p} \right) \right\} h(-p) = -2p + 2 \sum_{k=1}^{\lfloor p/6 \rfloor} \left( \frac{k}{p} \right) \quad (p \equiv 19 \bmod{24}). \end{equation}