What is the well-known result used to prove primality of $n=2pq+1$ under certain conditions?

93 Views Asked by At

On Henri Lifchitz's website, we find:

If $n=2pq+1$, $p$ and $q$ primes and $q>2p$, if there is an integer $a$ such $a^{n-1} \equiv 1 \pmod n$ and $\gcd(a^{2p}-1,n)=1$ then $n$ is prime.

It is described as a special case of a "well known" result involving $n=hq^k+1$ with $h=2p$, $p$ and $q$ are prime and $k=1$.

Question: What is the well-known result? Where can we find a proof of it?

Aside from its intrinsic interest, analysis of the proof of this result might be helpful for answering this question Primality Test with some condition, which includes the case $10p+1$.

1

There are 1 best solutions below

1
On BEST ANSWER

If we have $a^{n-1} = a^{2pq} \equiv 1 \pmod{n}$, but $\gcd(a^{2p}-1,n) = 1$, then for any prime $r$ dividing $n$, we have $a^{2p} \not\equiv 1 \pmod{r}$, but $a^{2pq} \equiv 1 \pmod{r}$, thus the order of $a$ modulo $r$ is a multiple of $q$, hence $r \equiv 1 \pmod{q}$, in particular $r \geqslant q+1$. But $(q+1)^2 > n$, so $n$ can have only one prime factor.