# Jacobi polynomials and primality testing

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

Inspired by Agrawal's conjecture in this paper I have formulated the following claim :

Let $$n$$ be an odd natural number greater than one . Let $$r$$ be the smallest odd prime number such that $$r \nmid n$$ and $$n^2 \not\equiv 1 \pmod r$$ . Let $$P_n^{(\alpha,\beta)}(x)$$ be Jacobi polynomial such that $$\alpha$$ , $$\beta$$ are natural numbers and $$\alpha +\beta < n$$ , then $$n$$ is a prime number if and only if $$P_n^{(\alpha,\beta)}(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$$ , $$\alpha$$ and $$\beta$$ and there were no counterexamples .

Mathematica implementation of test :

(* n>a+b *)
n=139;
a=14;b=22;
r=3;
While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
If[PolynomialMod[PolynomialRemainder[JacobiP[n,a,b,x],x^r-1,x],n]-PolynomialRemainder[x^n,x^r-1,x]===0,Print["prime"],Print["composite"]];

• Instead of the $n^2\not\equiv1\mod{r}$ condition, I would write, $r\;\not\vert\;n-1,n,n+1$ – Don Thousand Sep 10 '18 at 13:03

This answer proves that if $n$ is a prime number, then $P_n^{(\alpha,\beta)}(x) \equiv x^n \pmod {x^r-1,n}$.

Proof :

Assuming that $x$ is real and using the following expression $$P_n^{(\alpha,\beta)}(x)=\sum_{s=0}^{n}\binom{n+\alpha}{n-s}\binom{n+\beta}{s}\left(\frac{x-1}{2}\right)^s\left(\frac{x+1}{2}\right)^{n-s}$$ we have \begin{align}&2^n\left(P_n^{(\alpha,\beta)}(x)-x^n\right) \\\\&=-2^nx^n+\sum_{s=0}^{n}\binom{n+\alpha}{n-s}\binom{n+\beta}{s}(x-1)^s(x+1)^{n-s} \\\\&=-2^nx^n+\binom{n+\alpha}{n}(x+1)^{n}+\binom{n+\beta}{n}(x-1)^n \\&\qquad \qquad+\sum_{s=1}^{n-1}\binom{n+\alpha}{n-s}\binom{n+\beta}{s}(x-1)^s(x+1)^{n-s} \\\\&=-2^nx^n+\binom{n+\alpha}{n}\sum_{k=0}^{n}\binom{n}{k}x^{n-k}+\binom{n+\beta}{n}\sum_{k=0}^{n}\binom nk(-1)^{k}\cdot x^{n-k} \\&\qquad \qquad+\sum_{s=1}^{n-1}\binom{n+\alpha}{n-s}\binom{n+\beta}{s}(x-1)^s(x+1)^{n-s} \\\\&=\left(-2^n+\binom{n+\alpha}{n}+\binom{n+\beta}{n}\right)x^n+\left(\binom{n+\alpha}{n}-\binom{n+\beta}{n}\right) \\&\qquad\qquad +\binom{n+\alpha}{n}\sum_{k=1}^{n-1}\binom{n}{k}x^{n-k}+\binom{n+\beta}{n}\sum_{k=1}^{n-1}\binom nk(-1)^{k}\cdot x^{n-k} \\&\qquad \qquad+\sum_{s=1}^{n-1}\binom{n+\alpha}{n-s}\binom{n+\beta}{s}(x-1)^s(x+1)^{n-s}\end{align}

Here, we use the following facts :

• By Fermat's little theorem, $2^n\equiv 2\pmod n$.
Also, since $(n+\alpha)(n+\alpha-1)\cdots (n+1)\equiv \alpha !\pmod n$, we get $\binom{n+\alpha}{n}=\binom{n+\alpha}{\alpha}=\frac{(n+\alpha)(n+\alpha-1)\cdots (n+1)}{\alpha !}\equiv 1\pmod n$. Similarly, we get $\binom{n+\beta}{n}\equiv 1\pmod n$.
Therefore, we have $-2^n+\binom{n+\alpha}{n}+\binom{n+\beta}{n}\equiv -2+1+1\equiv 0\pmod n$.

• Since $\binom{n+\alpha}{n}\equiv 1\pmod n$ and $\binom{n+\beta}{n}\equiv 1\pmod n$, we get $\binom{n+\alpha}{n}-\binom{n+\beta}{n}\equiv 1-1\equiv 0\pmod n$.

• $\binom{n}{k}\equiv 0\pmod n$ for each $k$ such that $1\le k\le n-1$.

• Suppose that $\alpha\ge n-s$ and $\beta\ge s$. Then, we get $\alpha+\beta\ge n$ which contradicts $\alpha+\beta\lt n$. So, we have $\alpha\lt n-s$ or $\beta\lt s$.
If $\alpha\lt n-s$ with $1\le s\le n-1$, then the numerator of $\left(\binom{n+\alpha}{n-s}=\right)\frac{(n+\alpha)(n+\alpha-1)\cdots (\alpha+s+1)}{(n-s)!}$ is divisible by $n$, but the denominator isn't. So, $\binom{n+\alpha}{n-s}$ is divisible by $n$.
Similarly, if $\beta\lt s$, then $\binom{n+\beta}{s}$ is divisible by $n$.
As a result, we see that, for each $s$ such that $1\le s\le n-1$, $\binom{n+\alpha}{n-s}\binom{n+\beta}{s}$ is divisible by $n$.

Therefore, we see that there is a polynomial $f$ with integer coefficients such that $$2^n\left(P_n^{(\alpha,\beta)}(x)-x^n\right)=nf$$ from which $$P_n^{(\alpha,\beta)}(x)=x^n+(x^r-1)\times 0+n\times \frac{1}{2^n}f,$$ follows.

It follows from this and $\gcd(n,2^n)=1$ that $$P_n^{(\alpha,\beta)}(x) \equiv x^n \pmod {x^r-1,n}$$