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

• The question above indicates $a$ is an integer coprime to $n$, whereas the Sage code uses $a=1$, so is $a=1$ sufficient? The question above indicates $n^2\not\equiv 1\,(mod\, r)$, whereas the Sage code uses "lift(Mod(n,r)^2)==1" as a condition for continuing the search for a suitable value of $r$. I'm not familary with Sage, but is the lift function really necessary? Commented Jun 23, 2019 at 15:22
• @StevenClark You can use any other value of $a$ which is coprime to $n$ . I put $a=1$ because condition $\operatorname{gcd}(a,n)=1$ is always fulfilled for that value of $a$. In PARI/GP powermod is implemented via lift function, i.e. powermod(n,2,r)=lift(Mod(n,r)^2) . Commented Jun 23, 2019 at 16:23
• @PeđaTerzić Congrats on coming up with a practical test! How is the progress on the primality test? Thanks for the code too, I plan to use it on some of my multi-thousand digit probable primes. Commented Mar 3, 2020 at 6:00
• @PeđaTerzić also wanted to ask what is the running time of the code you produced (a 4000-digit input took 2 minutes for me). Commented Mar 4, 2020 at 1:14
• @J.Linne $O(\log^3 n)$ Commented Mar 4, 2020 at 6:02

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

• If the proof you gave were correct that would be a significant breakthrough in theory of primality testing. Commented Jun 30, 2019 at 12:55
• In $P_n^{(a)}(x)=x^n+s(x^r-1)+nf$, why is $s$ necessarily an integer and not a polynomial of higher degree? Commented Sep 12, 2019 at 13:24