2
$\begingroup$

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?

Improve this question
$\endgroup$
22
  • 2
    $\begingroup$ How does one get that 2p+1 is prime from your observation? $\endgroup$
    – The Masked Avenger
    Commented 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
    Commented Jun 12, 2015 at 17:39
  • 19
    $\begingroup$ The conjecture is false. Counterexample: $p = 2953$. $\endgroup$
    – Robert Israel
    Commented 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
    Commented 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$
    – The Masked Avenger
    Commented Jun 13, 2015 at 0:50

2 Answers 2

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
14
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you prove $(2953\times 2+1)|\binom{2\cdot 2953}{2953}+1$ by hand? $\endgroup$
    – Destiny freedom
    Commented 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$
    – The Masked Avenger
    Commented Jun 13, 2015 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .