Find all $n \in \mathbb{N}$ such that ${{2n}\choose{n}} \equiv (-1)^n\pmod{2n+1}$

Question

Find all $n \in \mathbb{N}$ such that $${{2n}\choose{n}} \equiv (-1)^n\pmod{2n+1}.$$

I know that if $2n+1$ were prime number, then

$${{2n}\choose{n}} = \frac{(2n) (2n-1) \cdots (n+1)}{n!} \equiv \frac{(-1)(-2)\cdots(-n)}{n!} = (-1)^n \pmod{2n+1}.$$

However, I'm not sure whether $\{ n \,|\, 2n+1 \text{ are prime}\}$ are the only possible solutions.

Answer 1

The solutions are those $n \in \mathbb N$ for which $2n+1$ is either prime or a Catalan pseudoprime.

We say that $2n+1$ is a Catalan pseudoprime if it is a composite number and $$(-1)^n\, C_n \equiv 2 \pmod{2n+1}$$ where $C_n$ is the $n$-th Catalan number, that is, $$C_n = \frac 1 {n+1} \binom {2n} n.$$ Rewriting the definition, we see that this means $$(-1)^n \frac 1 {n+1} \binom {2n} n \equiv 2 \pmod {2n+1}$$ and multiplying by $(-1)^n (n+1)$, $$\binom {2n} n \equiv (-1)^n (2n + 2) \equiv (-1)^n \pmod {2n+1}$$ which is the original congruence.

The only known Catalan pseudoprimes are $5907$, $1194649$ and $12327121$. So the only other solutions to the congruence that we know of are $2953$, $597324$ and $6163560$.

Answer 2

Consider $N=(2n+1)$, an odd number. If it is a prime number, then with the argument in the OP we have the congruence $\binom {2n}n=(-1)^n$ modulo $N$.

In case $N$ is not a prime we have to divide first in the above "scheme". I will give an example. For $n=10$, $N=21=3\cdot 7$, we have to compute modulo $21$ $$ \binom{2n}n= \binom{20}{10}= \frac{11}{10}\cdot \frac{12}{ 9}\cdot \frac{13}{ 8}\cdot \frac{14}{ 7}\cdot \frac{15}{ 6}\cdot \frac{16}{ 5}\cdot \frac{17}{ 4}\cdot \frac{18}{ 3}\cdot \frac{19}{ 2}\cdot \frac{20}{ 1}\ . $$ Now we have to simplify first with all the divisors of $21$, these are $3,7$, and instead of $\frac{14}7$ we get $\frac 21$. This contribution is not $(-1)$ "as in the pattern" for a prime number. There are also more complicated effects like $\frac{12}9=\frac 43$ where we cannot fully simplify inside of these fraction. We need the contribution of $18$ to get rid of the "second factor" $3$. Note that performing the calculus in $R=\Bbb Z/21$ we can replace the fractions which belong to $R^\times$ with the corresponding $(-1)$ factors modulo $21$, i.e. $$ \begin{aligned} \binom{20}{10} &= \frac{11}{10}\cdot \frac{12}{ 9}\cdot \frac{13}{ 8}\cdot \frac{14}{ 7}\cdot \frac{15}{ 6}\cdot \frac{16}{ 5}\cdot \frac{17}{ 4}\cdot \frac{18}{ 3}\cdot \frac{19}{ 2}\cdot \frac{20}{ 1} \\ &= (-1)\cdot \frac{12}{ 9}\cdot (-1)\cdot \frac{14}{ 7}\cdot \frac{15}{ 6}\cdot (-1)\cdot (-1)\cdot \frac{18}{ 3}\cdot (-1)\cdot (-1)\ . \end{aligned} $$ But the remained not $(-1)$ factors contribute in a chaotic way to the final result. With a probability $\sim 1/N$ (or $\sim 1/\varphi(N)$) we may get by fortune the $(-1)$. Here is an example, obtained with minimal sage code:

sage: for n in [3..10**6]:
....:     N = 2*n+1
....:     if N.is_prime(): continue
....:     R = Zmod(N)
....:     if R(binomial(2*n,n)) == R((-1)^n):
....:         print n, N
....:         
2953 5907

and i better stop here, there is already a better answer.

Pari/gp code finding it:

? for(n=1, 10^6, N=2*n+1; if( (1-isprime(N)) & binomial(2*n,n) % N == (-1)^n % N, print("n = ", n, " N = ", N, " with factors ", factor(N))))
n = 2953 N = 5907 with factors [3, 1; 11, 1; 179, 1]

(and it still runs right now...)