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 :

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

  • $\begingroup$ Thank you for the clarification, I really appreciate it. $\endgroup$ – Peđa Terzić Nov 17 '18 at 16:33

Please let me know if this is way off base.

We know $r\not|n$ and $n^{2} \not \equiv 1\ mod\ r$. Therefore, from the latter part of the statement we know $r\not| n^{2}-1$ which is equivalent to $r\not |(n-1)$ and $r\not|(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 $n\not = 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.


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.