# Compositeness testing using Jacobi polynomials

Can you prove or disprove the following claim:

Let $$P_n^{(\alpha,\beta)}(x)$$ be Jacobi polynomial . If $$p$$ is a prime number such that $$\alpha , \beta$$ are natural numbers and $$\alpha + \beta , then $$P_p^{(\alpha,\beta)}(a) \equiv a \pmod{p}$$ for all odd integers $$a$$ greater than one .

You can run this test here. I have tested this claim for many random values of $$p$$ , $$\alpha$$ and $$\beta$$ and there were no counterexamples .

• Are you including $0$ in the natural numbers? – Carl Schildkraut Jul 27 '20 at 4:53
• @CarlSchildkraut Yes. – Peđa Terzić Jul 27 '20 at 5:20

We use the identity $$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},$$ and assume that $$p\geq 3$$. For $$s=0$$, the sum is simply $$(x+1)/2$$ modulo $$p$$ (by Fermat's little theorem), and for $$s=p$$, the sum is $$(x-1)/2$$, so those two terms sum to $$x$$. It suffices to show that $$\sum_{s=1}^{p-1} \binom{p+\alpha}{p-s}\binom{p+\beta}{s}\left(\frac{x-1}2\right)^s\left(\frac{x+1}2\right)^{p-s}\equiv 0\bmod p$$ for all integer $$x$$. We claim, in fact, that each of these terms are multiples of $$p$$. By Lucas's theorem, for $$0, $$\binom{p+\alpha}{p-s}\equiv \binom{1}{0}\binom{\alpha}{p-s}\bmod p,$$ and $$\binom{p+\beta}{s}\equiv \binom{1}{0}\binom{\beta}{s}\bmod p.$$ However, since $$\alpha+\beta, either $$\alpha or $$\beta, so one of these is $$0\bmod p$$.