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

  • $\begingroup$ Does this have something to do with the number of points on the curve $y^{n-1}=x^{n-1}+1$? $\endgroup$ – Felipe Voloch Oct 10 '14 at 12:10
  • 1
    $\begingroup$ @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. $\endgroup$ – Seva Oct 10 '14 at 14:13
  • 2
    $\begingroup$ Observing that $n(n-1)$ is always even (an interesting fact on its own! cf. 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 (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! $\endgroup$ – Benjamin Dickman Oct 13 '14 at 2:33
  • 1
    $\begingroup$ @BenjaminDickman: Thanks for reminding me about mathoverflow.net/a/165441/22971; I will check how relevant it is. $\endgroup$ – Seva Oct 13 '14 at 18:10
  • 4
    $\begingroup$ Not that it matters, but $~\displaystyle\sum_{n=1}^\infty\frac1{2n(n-1)+1}=\frac\pi2\tanh\frac\pi2$. $\endgroup$ – Lucian Oct 14 '14 at 3:02

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

  • 3
    $\begingroup$ Is it Hexadecimal system or $10^6$? $\endgroup$ – Alexey Ustinov Aug 22 '16 at 7:49
  • $\begingroup$ It is $10^6$, not hexadecimal. $\endgroup$ – WhatsUp Aug 22 '16 at 10:58

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.