2
$\begingroup$

I have conjectured that $$\binom{2n}{n}\equiv (-1)^n \pmod{(2n+1)}$$ if and only if $2n+1$ is a prime number, based on a short program that I wrote verifying this up to $n=100$.

I know that by Wilson's Theorem, $(2n)!\equiv -1 \pmod{(2n+1)}$ if and only if $(2n+1)$ is a prime number, which is as close as I can get. Any hints on how to proceed with either direction of the proof would be appreciated as I am rather stuck.

Edit: Never mind. The "only if" part is actually false. $n=2953$ is a counterexample

$\endgroup$
  • 1
    $\begingroup$ It's surprising that such a specific statement doesn't have a counterexample until $n = 2953$! $\endgroup$ – Mees de Vries Jul 20 '18 at 18:06
  • $\begingroup$ @MeesdeVries Indeed. I have (so far) checked up to $n=500\,000$ and can find no other counterexample... $\endgroup$ – user544680 Jul 20 '18 at 20:40
  • $\begingroup$ I suppose that if the remainder appears to be uniformly randomly distributed over the values $0,\ldots,2n$, then as $n$ grows it would be rare to find it on just one of two values. (Perhaps you could conjecture that the only counterexample is $n = 2953$?) $\endgroup$ – Mees de Vries Jul 20 '18 at 20:58
  • 1
    $\begingroup$ @MeesdeVries There are more. They (the 2n+1) are known as Catalan Pseudoprimes. en.wikipedia.org/wiki/Catalan_pseudoprime oeis.org/A163209 $\endgroup$ – user544680 Jul 22 '18 at 18:01
0
$\begingroup$

If $(2n + 1)$ is indeed prime, we are working in a field and can consider $(n!)^2$ directly, since it is invertible. Note that, mod $(2n + 1)$, we have $$ n! = n \times \cdots \times 1 = (-1)^n \times -n \times \cdots \times -1 = (-1)^n \times (n+1) \times \cdots \times 2n, $$ and so $$ (n!)^2 = (-1)^n\times (2n!), $$ which is precisely what you wanted to prove.

$\endgroup$
0
$\begingroup$

To do the "if" part, use Wilson's theorem together with the fact that $2n\times(2n-1)\times\cdots(n+1)\equiv (-1)\times(-2)\times\cdots(-n)\equiv (-1)^nn!$ mod $2n+1$. I'll carry on thinking about the "only if" :)

$\endgroup$
  • $\begingroup$ Ah, thanks. I'm not sure Wilson's theorem is even necessary to prove the if direction then, if I have used your idea correctly. $\endgroup$ – user544680 Jul 19 '18 at 15:02
  • $\begingroup$ @user1488 yes, I think you're right, you just need that $2n!$ is coprime to $2n+1$. $\endgroup$ – Especially Lime Jul 19 '18 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy