Primes P such that ((P-1)/2)!=1 mod P - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:36:50Z http://mathoverflow.net/feeds/question/16141 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16141/primes-p-such-that-p-1-21-mod-p Primes P such that ((P-1)/2)!=1 mod P jacob 2010-02-23T09:19:51Z 2010-02-24T18:56:13Z <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$. </p> <p>Question: For which primes $P$ is $\left(\frac{P-1}{2}\right)!\equiv 1\pmod P$?</p> <p>After convincing myself that it's not a congruence condition for $P,$ I found <a href="http://www.research.att.com/~njas/sequences/A058302" rel="nofollow">this sequence in OEIS</a>. 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$).</p> <p>Thanks,</p> <p>Jacob</p> http://mathoverflow.net/questions/16141/primes-p-such-that-p-1-21-mod-p/16154#16154 Answer by lmerel for Primes P such that ((P-1)/2)!=1 mod P lmerel 2010-02-23T12:55:45Z 2010-02-24T18:56:13Z <p>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$.</p> <p>The proof may not be original: since $p\equiv 3 \pmod 4$, one has to determine the Legendre symbol</p> <p>$${{(\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$.</p> <p>Edit: For the correct answer see KConrad's post or Mordell's article. </p> http://mathoverflow.net/questions/16141/primes-p-such-that-p-1-21-mod-p/16164#16164 Answer by KConrad for Primes P such that ((P-1)/2)!=1 mod P KConrad 2010-02-23T14:44:41Z 2010-02-23T14:44:41Z <p>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$. </p> <p>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$.</p> <p>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.$$</p> <p>This shows why getting precise statistics on when the congruence has 1 on the right side will be hard.</p> http://mathoverflow.net/questions/16141/primes-p-such-that-p-1-21-mod-p/16167#16167 Answer by Pete L. Clark for Primes P such that ((P-1)/2)!=1 mod P Pete L. Clark 2010-02-23T14:58:27Z 2010-02-23T23:35:58Z <p>The following is a relevant classical paper:</p> <blockquote> <p>Mordell, L. J. The congruence $(p-1/2)!\equiv ±1$ $({\rm mod}$ $p)$. Amer. Math. Monthly 68 1961 145--146.</p> </blockquote> <p><a href="http://www.math.uga.edu/~pete/Mordell61.pdf" rel="nofollow">http://www.math.uga.edu/~pete/Mordell61.pdf</a></p> <blockquote> <p>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)</p> </blockquote> http://mathoverflow.net/questions/16141/primes-p-such-that-p-1-21-mod-p/16172#16172 Answer by David Speyer for Primes P such that ((P-1)/2)!=1 mod P David Speyer 2010-02-23T16:01:03Z 2010-02-23T16:01:03Z <p>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.</p> <p>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.</p> <p>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 <code>$$\prod_{q \equiv 3 \mod 4} (-1)^{a(q,p)}.$$</code></p> <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. </p> <p>Then we are supposed to have: <code>$$P(a(q,p)=0) = \prod_{i=1}^{\infty} (1-q^{-i}) = 1-1/q +O(1/q^2),$$</code> <code>$$P(a(q,p)=1) = \frac{1}{q-1} \prod_{i=1}^{\infty} (1-q^{-i}) = 1/q +O(1/q^2),$$</code> and <code>$$P(a(q,p) \geq 2) = O(1/q^2).$$</code></p> <p>If you believe all of the above, then the average value of $(-1)^{a(p,q)}$ is $1-2/q+O(1/q^2)$. </p> <p>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.</p> <p>Then <code>$$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)$$.</code></p> <p>The right hand side is zero, just as if $h(p)$ were equally like to be $1$ or $3 \mod 4$.</p>