Primality criterion

Question

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 .

Answer 1

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. }$$

Answer 2

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$.