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

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.

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.

• Although I am not challenging the mathematics, I wonder about the utility. If m is not prime (but we don't know that yet), we also want a guarantee that there is no h with P(h) a multiple of m, where P() is the polynomial we would use to test (and would equal Phi_m() if m were prime, but doesn't because m is not prime). Can you give us a theorem using P()? Gerhard "Wants To Cover His Bases" Paseman, 2020.08.05. – Gerhard Paseman Aug 5 at 17:51
• If the question is addressed to me, I agree that this criterion seems likely to have no "practical" use. I partly wanted to point out that there is a whole family of examples of problems of this kind that could be posed of the same nature. These problems would not strictly be "duplicates" of each other, but are close to being duplicates. – Geoff Robinson Aug 5 at 18:06
• Nevertheless, in theory the method does give a test for primality of $m$, knowing only the prime factorization of $m-1$. While calculating the polynomial $\Phi_{m-1}(x)$ may be unwieldy, it does not know or care whether or not $m$ is prime. Also, we may note that $(h+1)^{\phi(m-1) } \geq \Phi_{m-1}(h) \geq (h-1)^{\phi(m-1)}.$ – Geoff Robinson Aug 5 at 18:15
• It is addressed to you Geoff. I think my point is now that the problems have to do with a given P(), while your theorem does not talk about P(), but about something that is computationally harder to obtain (what is Phi_m when you know that m is not prime but also do not know the factors of m) (sorry, I need to use m-1 in some places)? I like the later edit, but in my view it has relevance more to general theory than to the proposed series of problems. Gerhard "Wants Theorems Talking About P()" Paseman, 2020.08.05. – Gerhard Paseman Aug 5 at 18:15
• Perhaps. For even better bounds, check out mathoverflow.net/q/221357 .Thanks for reminding me about Phi_{m-1}. Gerhard "Maybe Phi Is Good Enough" Paseman, 2020.08.05. – Gerhard Paseman Aug 5 at 18:31