Prove that if $n+1$ divides $\binom{2^{n}}{2}$ then $n+1$ is prime

Question

It is a straightforward simple question. Is the following statement true:

If $$n+1\text{ }\Bigg|\text{ } \binom{2^{n}}{2}$$ then $n+1$ is prime.

To see this I write $$\mathfrak a(n) =\binom{2^{n}}{2}$$ then observe that $$5|\mathfrak a(4), 7|\mathfrak a(6),\ldots,19|\mathfrak a(18),\ldots$$

There is no motivation here just curiosity. A counter example would suffice. I would like to think Euler's theorem comes into play but I am not sure how I would apply it.

Answer 1

$3+1$ divides $\binom{2^3}{2}=28$ but $3+1$ is not prime.

For more counterexamples, here is a Sage script:

for n in range(1,1000):
    if(binomial(2^n,2) % (n+1) == 0 and not is_prime(n+1)):
        print n

which prints

3
7
15
27
31
63
111
127
255
340
447
495
511
560
644

Answer 2

For $n$ even, then $n+1\mid 2^{n-1}(2^n-1)$ implies $n+1\mid 2^n-1$. There exists non-primes $q$ so that $q\mid 2^{q-1}-1$.

For example, $2^{340}-1$ is divisible by $341=11\cdot 31$, so $n=340$ is a counterexample with $n$ even.

$341$ is the smallest Euler pseudoprime to base $2$. Any Euler psuedoprime $q$ to base $2$ yields $n=q-1$ as a counterexample. There might be other cases - the property that $2^{q-1}-1$ is divisible by $q$ covers potentially some numbers that are not pseudo.

According to Wikipedia, the first Euler pseudoprimes to base $2$ are:

$341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481$