A strong probable prime is a positive integer $m$ either $2$, or such that when expressed as $m=d\;2^s$ with $d$ odd, it holds that $2^d\equiv1\pmod m$, or that $2^{(d\;2^r)}\equiv-1\pmod m$ for some $r$ with $0\le r<s$. All primes are strong probable primes, and most strong probable primes are prime; exceptions are the strong pseudoprimes (OEIS A001262).

If both $n$ and $m=(n-1)/2$ are strong probable primes, does it follow that $n$ is prime?

If $m$ is a strong probable prime other than $2$, then $m$ is odd, and $n=2m+1$ being a strong probable prime reduces to $2^m\equiv\pm1\pmod n$.

If $m=(n-1)/2$ is prime and $2^m\equiv\pm1\pmod n$, then $n$ is prime (proof by Fedor Petrov).

Therefore, any exception $n$ to the question's proposition has $(n-1)/2$ among strong pseudoprimes (OEIS A001262).

The table of Fermat pseudoprimes below $2^{64}$ compiled by Jan Feitsma and William Galway allows to quickly establish that the proposition holds for the $542622$ values of $n$ less than $2^{65}$ such that $n$ and $(n-1)/2$ are strong probable primes, but $(n-1)/2$ is composite (OEIS A301643, currently under review).

It is not surprising that the above is inconclusive: strong pseudoprimes (OEIS A001262) are a small subset of Euler pseudoprimes (OEIS A006970), and a similar exploration for the $950622$ values of $n$ less than $2^{65}$ such that $n$ and $(n-1)/2$ pass the Euler test, but $(n-1)/2$ is composite, shows there are only two composites $n$: $(2\cdot4^{23}+1)/3=283\cdot P_{12}$ and $(2\cdot4^{29}+1)/3=2833\cdot 37171\cdot P_{10}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.