Find all $n \in \mathbb{N}$ such that ${{2n}\choose{n}} \equiv (-1)^n\pmod{2n+1}$ 
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. 
 A: 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$.
A: 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...)
