Primality test for $N=2^mp^n +1$

Question

This question is related to my previous question.

Can you prove or disprove the following claim:

Let $N=2^mp^n+1$ , $m>0 , n>0$ and $p$ is an odd prime . If there exists an integer $a$ such that $$\displaystyle\sum_{i=0}^{p-1} (-1)^i \cdot a^{i \cdot(N-1)/2p} \equiv 0 \pmod{N}$$ then $N$ is a prime.

You can run this test here. I tried to mimic the proof given in this answer , but I didn't manage to adapt it for this generalization.

EDIT

Test implementation in PARI/GP without directly computing the sum.

Answer 1

I think this is true. Let $b = a^{\frac{N-1}{2p}} = a^{2^{m-1}p^{n-1}}$, and note that we have $\frac{b^{p}+1}{b+1} \equiv 0$ (mod $N$).

Now $a$ and $N$ must be coprime, so that $b$ and $N$ are coprime. We have $b^{2p} \equiv 1$ (mod $N$).

Now $b^{p}-1$ and $b^{p} +1$ have gcd dividing $2$. However $\frac{b^{p}+1}{b+1}$ is always odd, so that $\frac{b^{p}+1}{b+1}$ and $b^{p}-1$ are relatively prime.

If $q$ is a prime divisor of $N$, then $b+1$ is not divisible by $q$, for otherwise $\frac{b^{p}+1}{b+1} \equiv p$ (mod $q$), whereas we should have $\frac{b^{p}+1}{b+1} \equiv 0$ (mod $q$). Also, $b \not \equiv 1$ (mod $q$), since $b^{p}-1$ is coprime to $N.$

Hence $b^{2}-1$ is coprime to $N.$

The multiplicative order of $b$ (mod $N$) is a divisor of $2p$, but is not equal to $1$,$2$ or $p$, since $b^{2}-1$ and $b^{p}-1$ are both coprime to $N$.

Hence $b$ has multiplicative order $2p$ (mod $N$).

Now the multiplicative order of $a$ (mod $N$) is a divisor of $2^{m}p^{n}$, but none of $b = a^{2^{m-1}p^{n-1}}$, $b^{2} = a^{2^{m}p^{n-1}}$ or $b^{p} = a^{2^{m-1}p^{n}}$, are congruent to $1$ (mod $N$).

Thus $a$ has multiplicative order $2^{m}p^{n} = N-1$ in $\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}.$

But the multiplicative order of $a$ (mod $N$) is a divisor of $\phi(N)$, so we must have $\phi(N) = N-1$, and $N$ is prime.

Later edit: I point out that both this and the linked problem are implied by the following general theorem: If $m >1$ is an odd integer, then $m$ is prime if and only if there is an integer h with $\Phi_{m-1}(h) \equiv 0$ (mod $m$).

When $m$ is prime, there is such an integer $h$ since the multiplicative group of $\mathbb{Z}/m\mathbb{Z}$ is cyclic, and we may take $h$ such that $h +m\mathbb{Z}$ is a generator of that group.

For the other direction, assume that such an integer exists. Then $h$ is coprime to $m$ since $\Phi_{m-1}(x)$ has constant term $\pm 1.$

Also, the multiplicative order of $h +m\mathbb{Z}$ in $\mathbb{Z}/m\mathbb{Z}$ is a divisor of $m-1$ as $h^{m-1} \equiv 1$ (mod $m$)- because $h^{m-1}-1$ is divisible by $\Phi_{m-1}(h)$.

I claim that $h^{d}-1$ is coprime to $m$ whenever $d$ is a proper divisor of $m-1$. Let $q$ be a prime divisor of $m$. If $q$ divides $h^{d}-1$, then in $\mathbb{Z}[\omega]$, where $\omega$ is a primitive $m-1$-th root of unity, there is a primitive $m-1$-th root of unity $\alpha$, a $d$-th root of unity $\beta$, and a prime ideal $\pi$ (containing $q$) of $\mathbb{Z}[\omega]$ such that
$h- \alpha \in \pi$ and $h- \beta \in \pi$. Then $\alpha - \beta \in \pi$, so that $0 \neq 1 - \overline{\alpha}\beta \in \pi$.

But $1 - \overline{\alpha}\beta$ = $1- \omega^{k}$ for some $k$ with $0 < k < m-1$, and this is a factor of $m-1 = \prod_{j=1}^{m-2}(1-\omega^{j}) = m-1$ in $\mathbb{Z}[\omega].$ Hence $m-1 \in \pi$, so that $q|m-1$, a contradiction as $q$ is prime and we assumed $q|m$.

Thus $h^{d}-1$ is coprime to $m$ whenever $d$ is a divisor of $m-1$ with $d \neq m-1$.

Hence $h+ m\mathbb{Z}$ has multiplicative order $m-1$ in the group of units of $\mathbb{Z}/m\mathbb{Z}$, a group of order $\phi(m) \leq m-1$. Hence $\phi(m) = m-1$ and $m$ is prime.