Suppose $p<q$ are odd prime numbers. I only know the following easy to verify sufficient condition that $N=pq$ is a fermat-pseudoprime to base $2$, in other words that $$2^{N-1}\equiv 1\mod N$$ holds :

If $p$ is of the form $4k+1$ and $q=2p-1$, then we have $$2^{pq-1}\equiv 1\mod pq$$ A sufficient and necessary conidition is that $$2^{q-1}\equiv 1\mod p$$ and $$2^{p-1}\equiv 1\mod q$$ both hold.

Are there sufficient conditions covering more cases besides of the mentioned necessary and sufficient condition ? I think the orders of $2$ modulo $p$ and modulo $q$ could give us nice conditions.


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.