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?

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

$\endgroup$
14
$\begingroup$

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

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

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.