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

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

-
Given that there are no comments of any note on the sequence in the OEIS, there's a fair chance that little is known about your question. –  Kevin Buzzard Feb 23 '10 at 10:28
For all p<=250000, p=3 mod 4, we have 5458 +1s and 5589 -1s. –  Kevin Buzzard Feb 23 '10 at 10:56

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

-
That's very slick! –  David Speyer Feb 23 '10 at 13:02
Yes, very nice! My interpretation of the question is "do the primes for which the square root is 1 give a set of density 1/2?" and this at least gives some way of attacking the problem. –  Kevin Buzzard Feb 23 '10 at 13:09
+1. Salut, et bienvenu ! –  Chandan Singh Dalawat Feb 23 '10 at 13:58
In the paper emis.de/journals/EM/expmath/volumes/12/12.1/pp99_113.pdf they mention that Cohen proved modulo CL a conjecture of Hooley about a sum over $h(p)$. –  Victor Miller Feb 23 '10 at 15:14
Interesting. In particular, that paper claims that the odd part of h(p), as p runs through primes, seems to have the same distribution as the odd part of h(D), as D runs through square free integers. That's something I didn't know. I point out, however, that this paper deals with real quadratic fields. –  David Speyer Feb 23 '10 at 15:42

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.

-

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://www.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)

-
The notation k(\sqrt{-p}) for our Q(\sqrt{-p}) is "classical" and was used e.g. by Hilbert in his Bericht. The idea was that k(\sqrt{-p}) is the field k you get by adjoining a square root of -p to the rationals. –  Franz Lemmermeyer Feb 23 '10 at 17:07
Hecke uses $K(\root l\of\mu;k)$ to denote $k(\root l\of\mu)$ in his Vorlesungen. –  Chandan Singh Dalawat Feb 24 '10 at 1:06

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

-
Most of the latex formulas don't parse on my browser (Firefox 3.5.8) (though some do). Does any one know why? –  Anonymous Feb 23 '10 at 17:33
Might you be missing the jsmath fonts? math.union.edu/~dpvc/jsMath/users/fonts.html –  David Speyer Feb 23 '10 at 17:50
It works! Great. Thanks! –  Anonymous Feb 23 '10 at 17:56