1
$\begingroup$

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.

$\endgroup$

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.