# What type of pseudoprime does the largest known pseudoprime tend to be?

It is a well-known fact that the largest known prime number for several decades now has been a Mersenne prime, even though more and more of them have been found over the years and there have also been efforts to find other kinds of primes, like the one that proves that $10223$ is not a Sierpinski number.

But what about pseudoprimes? Does the largest known pseudoprime tend to be a Fermat pseudoprime to say, base $2$? Does the search for large prime numbers help reveal larger pseudoprimes?

• Sorry if this is too basic of a question, but what's a pseudoprime simply? I looked at the info for the tag and looked it up but found a lot of stuff I didn't understand. Thanks! – 米凯乐 Apr 19 '17 at 21:45
• @米凯乐 A pseudoprime is a composite number that has some properties that every prime number has (that is, properties that might be used to test for primality). The simplest example would be a composite number $n$ that passes Fermat Little Theorem for some test value $a$, $1<a<n{-}1$ giving $a^{n-1}\equiv 1 \bmod n$. Then $n$ is a Fermat pseudoprime to base $a$. – Joffan Apr 19 '17 at 22:22
• @Joffan It seems you have given a more general definition than the tag gives. I would like to edit the tag so your definition is the tag definition. – Robert Soupe Apr 20 '17 at 0:31
• On the negative side, Lehmer's Conjecture (D.H. Lehmer,1932) is that there are no Lehmer numbers. A Lehmer number is a composite $n$ such that the totient $\phi (n$) divides $n-1.$ A Lehmer number would necessarily be a Carmichael number. – DanielWainfleet Apr 25 '17 at 13:26
• @DanielWainfleet Hah, sounds like odd perfect numbers. Something we can say a great deal about that probably doesn't exist. – Joffan Apr 27 '17 at 22:14

One can generate arbitrarily large pseudoprimes. For example, if the exponent of a Mersenne number, $$2^x-1$$, is a Fermat probable prime base $$2$$, then so is the Mersenne number itself.
If we take $$x$$ not equal to a prime ($$x$$ a composite pseudoprime), then we can guarantee that $$2^x-1$$ is also a composite pseudoprime. In this manner,
$$2^{2047}-1$$, $$2^{2^{2047}-1}-1$$, $$2^{2^{2^{2047}-1}-1}-1$$, and so on are all composite pseudoprimes base $$2$$.