Counterexample to the primality test This is a generalization of this claim .
Can you provide a counterexample to the following claim?

Let $n$ be a natural number greater than two .  Let $r$ be the smallest odd prime number such that $r \nmid n$ and $n^2 \not\equiv 1 \pmod r$ . Let $P_n^{(a)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)$ , where $a$ is a nonzero integer coprime to $n$ . Then $n$ is a prime number if and only if $P_n^{(a)}(x) \equiv x^n \pmod {x^r-1,n}$ .

You can run this test here. 
I have tested this claim for many random values of $n$ and $a$ and there were no counterexamples .
EDIT
Algorithm implementation in PARI/GP without directly computing $P_n^{(a)}(x)$.
I have verified this claim for $n \in [3,100000]$ with $a \in [-100,100]$  .
 A: The claim is true.

It is true that if $n$ is a prime number, then $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$.
Proof : 
We have, by the binomial theorem,
$$\begin{align}P_n^{(a)}(x)&=\frac 12\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)
\\\\&=\frac 12\sum_{i=0}^{n}\binom nix^{n-i}\bigg(\bigg(-\sqrt{x^2+a}\bigg)^i+\bigg(\sqrt{x^2+a}\bigg)^i\bigg)
\\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j
\\\\&=x^n+\sum_{j=1}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j\end{align}$$
Since $\binom nm\equiv 0\pmod n$ for $1\le m\le n-1$, there exists a polynomial $f$ with integer coefficients such that 
$$P_n^{(a)}(x)=x^n+0\times (x^r-1)+nf$$
from which
$$P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$$
follows.$\quad\blacksquare$

It is true that if $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$, then $n$ is a prime number.
Proof : 
Suppose that $n$ is an even number. Then, there exist a polynomial $f$ with integer coefficients and an integer $s$ such that$$P_n^{(a)}(x)=\sum_{i=0}^{n/2}\binom{n}{2i}x^{n-2i}(x^2+a)^i=x^n+s(x^r-1)+nf$$
Considering $[x^{n}]$ where $[x^k]$ denotes the coefficient of $x^k$ in $P_n^{(a)}(x)$, we get
$$\sum_{i=0}^{n/2}\binom{n}{2i}\equiv 1\pmod n,$$
i.e.
$$2^{n-1}\equiv 1\pmod n$$which is impossible.
So, $n$ has to be an odd number.
There exist a polynomial $\displaystyle g=\sum_{i=0}^{n}a_ix^i$ where $a_i$ are integers and an integer $t$ such that
$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+t(x^r-1)+ng$$
Considering $[x^0]$, we have
$$0=-t+na_0\implies t=na_0$$
So, we see that there exists a polynomial $h$ with integer coefficients such that
$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+nh\tag1$$
It follows that $[x^k]\equiv 0\pmod n$ for all $k$ such that $0\le k\le n-1$.
Now, $(1)$ can be written as
$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\sum_{k=0}^{j}\binom n{2j}\binom jkx^{n-2(j-k)}a^{j-k}=x^n+nh$$
So, we see that 
$$\begin{align}&[x^3]\equiv 0\pmod n
\\\\&\implies \left(\binom n{n-3}\binom {(n-3)/2}0+\binom n{n-1}\binom {(n-1)/2}1\right)a^{(n-3)/2}\equiv 0\pmod n
\\\\&\implies \binom n{n-3}\equiv 0\pmod n\end{align}$$
since $\gcd(a,n)=1$.
Also, we have
$$\begin{align}&[x^5]\equiv 0\pmod n
\\\\&\implies \bigg(\binom n{n-5}\binom {(n-5)/2}0+\binom n{n-3}\binom {(n-3)/2}1
\\&\qquad\qquad+\binom n{n-1}\binom {(n-1)/2}2\bigg)a^{(n-5)/2}\equiv 0\pmod n
\\\\&\implies \binom n{n-5}\equiv 0\pmod n\end{align}$$
So, we can get (one can prove by induction)
$$\begin{align}&[x^3]\equiv [x^5]\equiv [x^7]\equiv\cdots\equiv [x^{n-2}]\equiv 0\pmod n
\\\\&\implies\binom n{n-3}\equiv\binom n{n-5}\equiv\binom n{n-7}\equiv\cdots\equiv\binom{n}{2}\equiv 0\pmod n
\\\\&\implies\binom{n}{2}\equiv \binom{n}{3}\equiv \binom n4\cdots \equiv\binom n{n-2}\equiv 0\pmod n\tag2\end{align}$$
Suppose here that $\displaystyle n=\prod_{i=1}^mp_i^{b_i}$ is a composite number where $p_1\lt p_2\lt\cdots\lt p_m$ are primes and $b_i$ are positive integers.
Let $[[N]]$ be the number of prime factor $p_i$ in $N$.
Then, we have the followings :


*

*$[[1!]]=[[2!]]=\cdots =[[(p_i-1)!]]=0$

*$[[p_i!]]=1$

*$[[(n-1)!]]=[[(n-2)!]]=\cdots =[[(n-p_i)!]]$
Using these, we see that
$$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_i-1}=\frac{n!}{(p_i-1)!(n-(p_i-1))!}$$
are divisible by $p_i^{b_i}$, and that 
$$\binom n{p_i}=\frac{n!}{p_i!(n-p_i)!}$$
is not divisible by $p_i^{b_i}$.
Therefore, we see that $$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_1-1}=\frac{n!}{(p_1-1)!(n-(p_1-1))!}$$
are divisible by $n$, and that $$\binom{n}{p_1}=\frac{n}{p_1!(n-p_1)!}$$ is not divisible by $n$, which contradicts $(2)$.
It follows that $n$ is a prime number.$\quad\blacksquare$
