# Primality criterion

Can you provide a proof or a counterexample for the claim given below ?

Inspired by Theorem 4 in this paper I have formulated the following claim :

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)$ . Given an odd integer $n$ ($\geq 3$) and integer $a$ coprime to $n$ , $n$ is prime if and only if $P_n^{(a)}(x) \equiv x^n \pmod{n}$ holds .

You can run this test here .

• Apparently, you are looking for many primality tests. A motivation to prove or disprove them woule be to show that they would be efficient in practice. – Peter Mar 31 '18 at 11:04

It holds true. The proof is much the same, with minor changes due to $$P_n^{(a)}(x) = \frac{n}{2} \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \frac{a^k(2x)^{n-2k}}{n-k}.$$ For odd prime $n$, we see that the coefficient of $x^n$ is $2^{n-1}$, and others are divisible by $n$. For odd composite $n$, we take a prime $p$ dividing $n$ and show that $n$ doesn't divide the coefficient of $x^p$.
I fear this is not true.$$P_n^{(5)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+5}\right)^9+\left(x+\sqrt{x^2+5}\right)^9\right)$$One has $$P_n^{(5)}(4)=126336484=9(14037387)+1\\4^9=262144=9(29127)+1$$Therefore $$P_n^{(5)}(4)\equiv 4^9\pmod9\space\space\text{but 9 is not prime. }$$