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 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 $H_n(x)$ be Hermite polynomial , then $n$ is either a prime number or Fermat pseudoprime to base $2$ if and only if $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$ .
You can run this test here .
Mathematica implementation of test :
n=31;
r=3;
While[Mod[n,r]==0 || PowerMod[n,2,r]==1,r=NextPrime[r]];
If[PolynomialMod[PolynomialRemainder[HermiteH[n,x],x^r-1,x],n]-PolynomialRemainder[2*x^n,x^r-1,x]===0,Print["probably prime"],Print["composite"]];
Best Answer
The claim is not true.
It is not true that if $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$, then $n$ is either a prime number or Fermat pseudoprime to base $2$.
Proof :
Let us consider the case where $n$ is an even number greater than $2$.
So, $n$ is neither a prime number nor Fermat pseudoprime to base $2$.
Using the following expression $$H_{2k}=(-1)^k2^k(2k-1)!!\left(1+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j)!}x^{2j}\right)$$ we have, using $(n-1)!!\cdot 2^{\frac n2}(\frac n2)!=n!$, $$\begin{align}H_{n}&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\left(1+\sum_{j=1}^{\frac n2}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\right) \\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-2n)(-2n+4)\cdots (-4)}{n!}x^{n} \\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac n2-1}\frac{(-2n)(-2n+4)\cdots (-2n+4j-4)}{(2j)!}x^{2j}\bigg) \\\\&=(-1)^{\frac n2}2^{\frac n2}(n-1)!!\bigg(1+\frac{(-4)^{\frac n2}(\frac n2)!}{n!}x^{n}+\sum_{j=1}^{\frac n2-1}\frac{(-4)^j(\frac n2)!}{(\frac{n-2j}{2})!(2j)!}x^{2j}\bigg) \\\\&=2x^n+(2^n-2)x^n+\frac{(-1)^{\frac n2}n!}{(\frac n2)!}+n(-1)^{\frac n2}\sum_{j=1}^{\frac n2-1}\frac{(n-2j-1)!}{(\frac{n-2j}{2})!}\binom{n-1}{2j}(-4)^j \end{align}$$
So, there is a polynomial $f$ with integer coefficients such that $$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+nf$$ Now, if $n$ is an even pseudoprime to base 2, then we get $2^n-2\equiv 0\pmod n$, so it follows that $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$.
Therefore, $n=161038$ is a counterexample.$\qquad\blacksquare$
It is true that if $n$ is either a prime number or Fermat pseudoprime to base $2$, then $H_n(x) \equiv 2x^n \pmod {x^r-1,n}$.
Proof :
For $n=3$, we have $$H_3(x)=2x^3+(x^r-1)\times 0+3(2x^3-4x)\equiv 0\pmod {x^r-1,3}$$
In the following, $n$ is an odd number greater than $3$.
Using the following expression $$H_{2k+1}(x)=(-1)^k\cdot 2^{k+1}(2k+1)!!\bigg(x+\sum_{j=1}^{k}\frac{(-4k)(-4k+4)\cdots (-4k+4j-4)}{(2j+1)!}x^{2j+1}\bigg)$$ we have, using $n!!\cdot 2^{\frac{n-1}{2}}(\frac{n-1}{2})!=n!$,
$$\begin{align}H_{n}(x)&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\sum_{j=1}^{\frac{n-1}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-2n+2)(-2n+6)\cdots (-4)}{n!}x^{n} \\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-2n+2)(-2n+6)\cdots (-2n+4j-2)}{(2j+1)!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!\bigg(x+\frac{(-4)^{\frac{n-1}{2}}(\frac{n-1}{2})!}{n!}x^{n} \\&\qquad\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{(-4)^j(\frac{n-1}{2})!}{(2j+1)!(\frac{n-2j-1}{2})!}x^{2j+1}\bigg) \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n} \\&\qquad\qquad\qquad\qquad+\sum_{j=1}^{\frac{n-3}{2}}\frac{n!\cdot(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}(-4)^{j}}{(2j+1)!\left(\frac{n-2j-1}{2}\right)!\cdot 2^{\frac{n-1}{2}}}x^{2j+1} \\\\&=(-1)^{\frac{n-1}{2}}\cdot 2^{\frac{n+1}{2}}n!!x+2^nx^{n} \\&\qquad\qquad\qquad\qquad+n\sum_{j=1}^{\frac{n-3}{2}}\frac{(n-2j-2)!\binom{n-1}{2j+1}(-1)^{\frac{n-1}{2}}\cdot 2\cdot (-4)^{j}}{\left(\frac{n-2j-1}{2}\right)!}x^{2j+1} \\\\&=2x^n+(2^n-2)x^{n}+2n(-1)^{\frac{n-1}{2}}\sum_{j=\color{red}{0}}^{\frac{n-3}{2}}\frac{(n-2j-2)!}{\left(\frac{n-2j-1}{2}\right)!}\binom{n-1}{2j+1}(-4)^{j}x^{2j+1} \end{align}$$
So, there is a polynomial $g$ with integer coefficients such that $$H_n(x)=2x^n+(2^n-2)x^n+(x^r-1)\times 0+ng$$
Since $n$ is either a prime number or Fermat pseudoprime to base $2$, we get $2^n-2\equiv 0\pmod n$.
It follows that $$H_n(x)\equiv 2x^n\pmod{x^r-1,n}\qquad\blacksquare$$