Counterexample to the primality test

Question

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

Answer 1

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$