Krdytkyu

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 notequiv 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"]];

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}
\&qquadqquadqquadqquadqquad+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-2equiv 0pmod n$, so it follows that $H_n(x) equiv 2x^n pmod {x^r-1,n}$.

Therefore, $n=161038$ is a counterexample.$qquadblacksquare$

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 0pmod {x^r-1,3}$$

In the following, $n$ is an odd number greater than $3$.

Using the following expression
$$H_{2k+1}(x)=(-1)^kcdot 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}
\&qquadqquadqquadqquad+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}
\&qquadqquadqquadqquadqquad+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}
\&qquadqquadqquadqquad+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}
\&qquadqquadqquadqquad+nsum_{j=1}^{frac{n-3}{2}}frac{(n-2j-2)!binom{n-1}{2j+1}(-1)^{frac{n-1}{2}}cdot 2cdot (-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-2equiv 0pmod n$.

It follows that $$H_n(x)equiv 2x^npmod{x^r-1,n}qquadblacksquare$$

Please let me know if this is way off base.

We know $rnot|n$ and $n^{2} not equiv 1 mod r$. Therefore, from the latter part of the statement we know $rnot| n^{2}-1$ which is equivalent to $rnot |(n-1)$ and $rnot|(n+1)$. So for any $n$ we have two cases. The first being $n-1$ is odd, $n$ is even, and $n+1$ is odd. The second being $n-1$ is even, $n$ is odd, and $n+1$ is even. Since in both circumstances we have an even integer we know $nnot = 2$. Because we have three consecutive integers, that are greater than 2, we must have at least one that is divisible by $3$.

So the fact that we cannot have $3$, but you state that $n$ is a prime number greater than $2$ or pseudo-prime to base $2$ (smallest is $341$?) makes your proof invalid due to a contradiction in your consequent.

Once again, sorry if I am not understanding something.