35
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Kevin Buzzard Feb 23 '10 at 10:28
  • 3
    $\begingroup$ For all p<=250000, p=3 mod 4, we have 5458 +1s and 5589 -1s. $\endgroup$ – Kevin Buzzard Feb 23 '10 at 10:56
35
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's very slick! $\endgroup$ – David E Speyer Feb 23 '10 at 13:02
  • $\begingroup$ 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. $\endgroup$ – Kevin Buzzard Feb 23 '10 at 13:09
  • $\begingroup$ +1. Salut, et bienvenu ! $\endgroup$ – Chandan Singh Dalawat Feb 23 '10 at 13:58
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Victor Miller Feb 23 '10 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$ – David E Speyer Feb 23 '10 at 15:42
26
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Franz Lemmermeyer Feb 23 '10 at 17:07
  • 1
    $\begingroup$ Hecke uses $K(\root l\of\mu;k)$ to denote $k(\root l\of\mu)$ in his Vorlesungen. $\endgroup$ – Chandan Singh Dalawat Feb 24 '10 at 1:06
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Interesting reference. I guess this answers one of my questions: mathoverflow.net/questions/106359/… $\endgroup$ – js21 Nov 27 '17 at 11:32
  • $\begingroup$ @js21, if you haven't already seen it, you may also be interested in the discussion of Karpinski's work in Wells Johnson and Kevin J. Mitchell, "Symmetries for sums of the Legendre symbol," Pacific Journal of Mathematics 69(1) (May 1977): 117-124, available online at msp.org/pjm/1977/69-1/pjm-v69-n1-p11-p.pdf. $\endgroup$ – John Blythe Dobson Dec 3 '17 at 2:10

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.