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?

  • 2
    $\begingroup$ How does one get that 2p+1 is prime from your observation? $\endgroup$ Jun 12, 2015 at 17:31
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Todd Trimble
    Jun 12, 2015 at 17:39
  • 19
    $\begingroup$ The conjecture is false. Counterexample: $p = 2953$. $\endgroup$ Jun 12, 2015 at 18:51
  • 9
    $\begingroup$ 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. $\endgroup$
    – YCor
    Jun 12, 2015 at 19:29
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 13, 2015 at 0:50

2 Answers 2


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

  • $\begingroup$ can you prove $(2953\times 2+1)|\binom{2\cdot 2953}{2953}+1$ by hand? $\endgroup$ Jun 13, 2015 at 2:43
  • $\begingroup$ 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. $\endgroup$ Jun 13, 2015 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.