6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – 米凯乐 Apr 19 '17 at 21:45
  • 2
    $\begingroup$ @米凯乐 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$. $\endgroup$ – Joffan Apr 19 '17 at 22:22
  • $\begingroup$ @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. $\endgroup$ – Robert Soupe Apr 20 '17 at 0:31
  • 2
    $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 25 '17 at 13:26
  • 1
    $\begingroup$ @DanielWainfleet Hah, sounds like odd perfect numbers. Something we can say a great deal about that probably doesn't exist. $\endgroup$ – Joffan Apr 27 '17 at 22:14
6
$\begingroup$

There are some enormous Carmichael numbers (eg. 16+ million digits), pseudoprime to any coprime base, which can be generated by Löh & Niebuhr's method.


Update: this 2011 Hayman & Shallue poster reports the construction of a Carmichael number with more than 10 billion factors and around 295 billion decimal digits.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.