# If $\binom{2p}{p}$ is $(-1)^{p-1} \bmod 2p+1$ is then $2p+1$ prime?

Let $p$ be a positive integer; if $2p+1$ is prime then it is easily checked that $$(2p+1)\mid\left(\binom{2p}{p}+(-1)^{p-1}\right);$$

conversely I conjecture that if the above divisibility assumption holds, then $2p+1$ is a prime number. Is this true?

• How does one get that 2p+1 is prime from your observation? – The Masked Avenger Jun 12 '15 at 17:31
• @GHfromMO The trouble is that some of the factors of $p!$ will be zero divisors mod $2p+1$, so you can't do the division by $p!$. For example, it's not true in the case where $p = 4$. – Todd Trimble Jun 12 '15 at 17:39
• The conjecture is false. Counterexample: $p = 2953$. – Robert Israel Jun 12 '15 at 18:51
• Sloane could recognize the sequence with the single term 5907 ($=2.2953+1$): the keyword seems to be "Catalan pseudoprime" or "Wilson spoilers":), see oeis.org/A163209; only 3 such primes are known (5907 and the squares of the two known Wieferich primes), see en.wikipedia.org/wiki/Catalan_pseudoprime. – YCor Jun 12 '15 at 19:29
• @GHfromMO, that might have been your reading of the original post. Mine (and I imagine Todd's) is that the idea "2p+1 is prime" is a conjectured consequence. Of course, if 2p+1 is an assumption, then your observation holds, and Wilson is not needed to get the congruence. Then again, Robert Israel's example shows Wilson is of little use here. – The Masked Avenger Jun 13 '15 at 0:50

(Also from my comment, when the question was closed)

From Robert Israel's single example $2p+1=5907$ I found in Sloane Encyclopaedia the general picture:

A Catalan pseudoprime is an odd non-prime $2q+1$ satisfying $$2q+1\;\big|\;(-1)^qC_q-2,$$ where $C_m$ is the Catalan number $\frac1{m+1}\begin{pmatrix}2m \\ m\end{pmatrix}$.

Using that $q+1$ and $2q+1$ are coprime and $2(q+1)\equiv 1[2q+1]$, we see that the above divisibility condition is equivalent to the initial condition $(2q+1)\mid\binom{2q}{q}+(-1)^{q-1}$. So the Catalan pseudoprimes are precisely those odd non-primes $2q+1$ satisfying $(2q+1)\mid\binom{2q}{q}+(-1)^{q-1}$.

There are only 3 known Catalan pseudoprimes; they form Sloane's sequence A163209; here are their prime factorization

• $5907=3\times 11\times 179$
• $1194649=1093^2$
• $12327121=3511^2$

The latter two are the squares of the two known Wieferich primes.

(Posting my earlier comment as an answer) The conjecture is false. Counterexample: $p=2953$.

• can you prove $(2953\times 2+1)|\binom{2\cdot 2953}{2953}+1$ by hand? – Destiny freedom Jun 13 '15 at 2:43
• You can do it by hand, but it would take a while. Factor 2*2953 + 1 as 3 * 11 * 179, and consider those terms which are multiples of 3 or 11 or 179 separately. Or as Robert Israel commented, work modulo each prime. – The Masked Avenger Jun 13 '15 at 4:56