21
$\begingroup$

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

Improve this question
$\endgroup$
9
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 3:02

1 Answer 1

Reset to default
2
$\begingroup$

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

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

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.