3
$\begingroup$

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"]];
$\endgroup$
1
  • $\begingroup$ Instead of the $n^2\not\equiv1\mod{r}$ condition, I would write, $r\;\not\vert\;n-1,n,n+1$ $\endgroup$ Commented Sep 10, 2018 at 13:03

1 Answer 1

1
+50
$\begingroup$

This is a partial answer.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .