22

Well, the title does not tell the whole story; the complete question is:

Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that $$ \binom{2n}{n} \equiv 2\pmod p ? $$

Primes $p=2n(n-1)+1$ are not that rare: say, of all numbers of this form up to $2\cdot10^{10}$, some 12.7% are prime; however, for none of these primes the congruence above holds true.

A simple heuristic is as follows. Let's say that a prime is bad if it satisfies the congruence. If the binomial coefficients $\binom{2n}{n}$ were distributed uniformly modulo $p$, then the probability that a particular prime $p$ is bad would be about $1/p$. Also, the probability that bad primes exist does not exceed the sum of probabilities for all primes $p=2n(n-1)+1>2\cdot10^{10}$ to be "bad". Hence, this probability is at most $$ \sum_{n>10^5} \frac1{2n(n-1)+1} < 5\cdot 10^{-6}. $$

Andrés E. Caicedo
  • 32,193
  • 5
  • 130
  • 233
Seva
  • 22,827
  • Does this have something to do with the number of points on the curve $y^{n-1}=x^{n-1}+1$? – Felipe Voloch Oct 10 '14 at 12:10
  • 1
    @Felipe: having thought for a little while, I don't see any immediate relation. It has to do with $y^{2(n-1)}-x^{2(n-1)}$ being quadratic residues though. – Seva Oct 10 '14 at 14:13
  • What do you see for small n when factoring C-2, where C is the middle binomial coefficient? – The Masked Avenger Oct 10 '14 at 15:39
  • @The Masked Avenger: I've just made the computation - nothing to write home about. (I have troubles fitting the results into this comment, but they are absolutely non-illuminating, anyway.) – Seva Oct 10 '14 at 16:07
  • 2
    Observing that $n(n-1)$ is always even (an interesting fact on its own! cf. http://mathoverflow.net/a/152300/22971), you have a prime of the form $p = 4k+1$. In this light, an earlier answer and link from Lucia (http://mathoverflow.net/a/165441/22971) may be relevant to your question. My hunch is that the information there can be pushed through to answer your question in the negative, but I don't see how to do it. Maybe someone else (or you) will! – Benjamin Dickman Oct 13 '14 at 02:33
  • 1
    @BenjaminDickman: Thanks for reminding me about mathoverflow.net/a/165441/22971; I will check how relevant it is. – Seva Oct 13 '14 at 18:10
  • 4
    Not that it matters, but $~\displaystyle\sum_{n=1}^\infty\frac1{2n(n-1)+1}=\frac\pi2\tanh\frac\pi2$. – Lucian Oct 14 '14 at 03:02
  • What is known (if anything) about arbitrary primes $p$? – Włodzimierz Holsztyński Nov 02 '16 at 05:52
  • @ Włodzimierz Holsztyński: Nothing! – Seva Nov 02 '16 at 07:38

1 Answers1

2

Confirmed up to $n = 1e6$. No example found.

But note that there is probably nothing special about the number $2$. The same holds (also up to $n = 1e6$) with $2$ replaced by $3, 4, 5, 8$.

WhatsUp
  • 21