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 *)
While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
  • $\begingroup$ Instead of the $n^2\not\equiv1\mod{r}$ condition, I would write, $r\;\not\vert\;n-1,n,n+1$ $\endgroup$ – Don Thousand Sep 10 '18 at 13:03

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.