# Prove that $\binom{2n}{n}\equiv (-1)^n \pmod{(2n+1)}$ if and only if $2n+1$ is a prime number.

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

• It's surprising that such a specific statement doesn't have a counterexample until $n = 2953$! – Mees de Vries Jul 20 '18 at 18:06
• @MeesdeVries Indeed. I have (so far) checked up to $n=500\,000$ and can find no other counterexample... – user544680 Jul 20 '18 at 20:40
• 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$?) – Mees de Vries Jul 20 '18 at 20:58
• @MeesdeVries There are more. They (the 2n+1) are known as Catalan Pseudoprimes. en.wikipedia.org/wiki/Catalan_pseudoprime oeis.org/A163209 – user544680 Jul 22 '18 at 18:01

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.
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" :)
• @user1488 yes, I think you're right, you just need that $2n!$ is coprime to $2n+1$. – Especially Lime Jul 19 '18 at 15:04