Buscar todos $n \in \mathbb{N}$ tal que ${{2n}\choose{n}} \equiv (-1)^n\pmod{2n+1}$

Question

Buscar todos $n \in \mathbb{N}$ tal que $${{2n}\choose{n}} \equiv (-1)^n\pmod{2n+1}.$$

Sé que si $2n+1$ fueran números primos, entonces

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

Sin embargo, no estoy seguro de si $\{ n \,|\, 2n+1 \text{ are prime}\}$ son las únicas soluciones posibles.

Answer 1

Las soluciones son las siguientes $n \in \mathbb N$ para lo cual $2n+1$ es primo o pseudoprimo catalán.

Decimos que $2n+1$ es un pseudoprimo catalán si es un número compuesto y $$(-1)^n\, C_n \equiv 2 \pmod{2n+1}$$ donde $C_n$ es el $n$ -ésimo número catalán, eso es, $$C_n = \frac 1 {n+1} \binom {2n} n.$$ Reescribiendo la definición, vemos que esto significa $$(-1)^n \frac 1 {n+1} \binom {2n} n \equiv 2 \pmod {2n+1}$$ y multiplicando por $(-1)^n (n+1)$ , $$\binom {2n} n \equiv (-1)^n (2n + 2) \equiv (-1)^n \pmod {2n+1}$$ que es la congruencia original.

Los únicos pseudoprimes catalanes conocidos son $5907$ , $1194649$ y $12327121$ . Así que las únicas otras soluciones a la congruencia que conocemos son $2953$ , $597324$ y $6163560$ .

Answer 2

Considere $N=(2n+1)$ un número impar. Si es un número primo, entonces con el argumento en el OP tenemos la congruencia $\binom {2n}n=(-1)^n$ modulo $N$ .

En caso de que $N$ no es un primo tenemos que dividir primero en el "esquema" anterior. Daré un ejemplo. Para $n=10$ , $N=21=3\cdot 7$ tenemos que calcular el módulo $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}\ . $$ Ahora tenemos que simplificar primero con todos los divisores de $21$ Estos son $3,7$ y en lugar de $\frac{14}7$ obtenemos $\frac 21$ . Esta contribución no es $(-1)$ "como en el patrón" para un número primo. También hay efectos más complicados como $\frac{12}9=\frac 43$ donde no podemos simplificar completamente dentro de esta fracción. Necesitamos la contribución de $18$ para deshacerse del "segundo factor" $3$ . Obsérvese que la realización del cálculo en $R=\Bbb Z/21$ podemos sustituir las fracciones que pertenecen a $R^\times$ con el correspondiente $(-1)$ factores modulo $21$ es decir $$ \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} $$ Pero el no permaneció $(-1)$ factores contribuyen de forma caótica al resultado final. Con una probabilidad $\sim 1/N$ (o $\sim 1/\varphi(N)$ ) podemos conseguir por fortuna el $(-1)$ . He aquí un ejemplo, obtenido con un mínimo salvia código:

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

y mejor paro aquí, ya hay una respuesta mejor.

Código Pari/gp para encontrarlo:

? 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]

(y sigue funcionando ahora mismo...)