Prove prime test conjecture.

[RLBrown]

I was examining the AKS and discovered this conjecture.

Please prove the following true or false.
Let n be an odd integer >2

then n is prime IFF
$\left(
\begin{array}{c}
n-1 \\
\frac{n-1}{2} \\
\end{array}
\right)

\text{ $\equiv $ }
\pm 1$ mod n

 

[Opalg]

I was examining the AKS and discovered this conjecture.

Please prove the following true or false.
Let n be an odd integer >2

then n is prime IFF
$\left(
\begin{array}{c}
n-1 \\
\frac{n-1}{2} \\
\end{array}
\right)

\text{ $\equiv $ }
\pm 1$ mod n

A quick internet search indicates that this result is false, but only just! In fact, the condition \(\displaystyle {n-1 \choose \frac{n-1}2} \equiv \pm1\!\!\! \pmod n\) holds whenever $n$ is prime. However, it also holds for the numbers $5907$, $1194649$ and $12327121$, which are not prime. It is not known whether there are any other non-prime odd numbers that satisfy the condition.

For more information, search for "Catalan pseudoprimes".