Primality testing with binomial coefficients Here is what I observed :
Let $n$ be a natural number greater than 2.
Let $A = 2\cdot\binom{3n+1}{n}-\binom{3n}{n-1}+\binom{3n-1}{n-2}$
Let $p=2n+1$
$p$ is prime iff $A \equiv 2 \pmod{p}$
You can run this test here.
I tried with some prime and composite numbers below 350000 and I didn't find any counterexample.
Is there a way to prove it ? I think this is related to Wilson's theorem but I'm not sure.
 A: Peter’s keen observation and idea is a Credit to the following partial answer.
I agree with what Peter said that the prime case is not difficult to prove using an interesting lemma below.
Lemma:
For any prime number $p$ and natural number $k$ satisfying $p<k<2p,$
$$
\left(\begin{array}{c}
k \\
p
\end{array}\right) \equiv 1 \quad  (\bmod p)
$$
Proof:
By definition, $$
\left(\begin{array}{l}
k \\
p
\end{array}\right)=\frac{k(k-1)\cdots(p+2)(p+1)}{(k-p)!}
$$
Rearranging gives $$
(k-p)!\left(\begin{array}{l}
k \\
p
\end{array}\right)=k(k-1) \cdots(p+2)(p+1)
$$
As $p\not |k,$ taking both sides in modulo $p,$ yields $$
\begin{aligned}
(k-p) !\left(\begin{array}{c}
k \\
p
\end{array}\right) & \equiv (k-p) !\quad (\bmod p) \\
\left(\begin{array}{l}
k \\
p
\end{array}\right) & \equiv 1 \quad (\bmod p)
\end{aligned}
$$
Rewriting $A$ gives $$
\begin{aligned}
A &=2\left(\begin{array}{c}
3 n+1 \\
2 n+1
\end{array}\right)-\left(\begin{array}{c}
3 n \\
2 n+1
\end{array}\right)+\left(\begin{array}{c}
3 n-1 \\
2 n+1
\end{array}\right) \\
&=2\left(\begin{array}{c}
3 n+1 \\
p
\end{array}\right)-\left(\begin{array}{c}
3 n \\
p
\end{array}\right)+\left(\begin{array}{c}
3 n-1 \\
p
\end{array}\right)
\end{aligned}
$$
If $p=2n+1$ is prime, then using the lemma yields $$
A \equiv 2-1+1 \equiv 2 \quad  \pmod p
$$
Wish someone can help solve the converse!
