Define "probable prime" (PP) to be natural $n>1$ satisfying $2^{n-1} \equiv 1 \pmod{n}$ or $n=2$.

Probable primes are the union of the primes and base two pseudoprimes.

This definition is much simpler than the definition for primes and the primes are sufficiently large subset of probable primes.

Are there open problems for primes which are known for probable primes?

Positive answer doesn't necessarily mean the problem is solved for the primes (e.g. infinitely many twin PP hypothetically might mean finitely many twin primes and infinitely many twin base 2 pseudoprimes).

  • 9
    $\begingroup$ This is no longer an open problem, but "PRIMES are in P" was only solved in 2002, whereas "PROBABLE_PRIMES are in P" is more or less trivial ($2^{n-1} \hbox{ mod } n$ can be computed in time $O( \log^{O(1)} n )$ through repeated squaring). $\endgroup$ – Terry Tao Sep 1 '15 at 15:48
  • $\begingroup$ It may help to look @Distribution of the number of prime factors. $\endgroup$ – Joseph O'Rourke Feb 14 '16 at 0:05

There are infinitely many Mersenne probable primes. Let $p$ be a prime (or even a probable prime). Then I claim that $2^p-1$ is a probable prime.

Proof: $2^k \equiv 1 \pmod{2^p-1}$ if and only if $k \equiv 0 \pmod p$, so it suffices to check that $2^p-1-1 \equiv 0 \pmod p$, and this follows from $p$ being a probable prime.

  • $\begingroup$ Indeed :-) Probably more complicated proof for p prime is from the factorization of $2^p-1$. $\endgroup$ – joro Sep 2 '15 at 5:48
  • 2
    $\begingroup$ One consequence of this is that one can rapidly and deterministically generate arbitrarily large (albeit quite sparse) probable primes via iterating the map $p \mapsto 2^{p-1}$. This is in contrast to genuine primes, for which a fast deterministic algorithm to generate large primes is still not known, see michaelnielsen.org/polymath1/index.php?title=Finding_primes $\endgroup$ – Terry Tao Sep 2 '15 at 21:59
  • $\begingroup$ @TerryTao Actually there is conjecture that starting from $2$ your map is genuine prime: primes.utm.edu/mersenne see "Let C0 = 2, then let C1 = 2^C0-1, C2 = 2^C1-1...Are these all prime?" $\endgroup$ – joro Sep 3 '15 at 5:18
  • $\begingroup$ @TerryTao I had been a bit hesitant to post this answer because it seemed rather trivial, but your observation makes it look much more interesting. $\endgroup$ – S. Carnahan Sep 3 '15 at 7:57
  • $\begingroup$ Your answer isn't rocket science, but for me this is positive result, which might be counterexample to the other answer. $\endgroup$ – joro Sep 3 '15 at 9:37

It is of course dangerous to say something cannot be done (and difficult to prove!), but one may be skeptical that such a (natural) problem exists. The number of ``probable primes" that are composite (these are usually called "pseudoprimes") up to $x$ is at most $$ \ll x \exp \Big( - c \frac{\log x \log \log \log x}{\log \log x}\Big), $$ by a result of Pomerance. Thus the set of probable primes is essentially just the set of primes together with a much smaller set of pseudoprimes, and I don't think we understand enough about this small set to use it meaningfully (in contrast for example with almost primes which are at least as numerous as the primes and have a more tractable distribution).

  • 1
    $\begingroup$ Thank you, but how "a small set" is answer to the question? As Tao pointed out in comment, the decision problem about membership is much easier. $\endgroup$ – joro Sep 1 '15 at 17:24
  • 2
    $\begingroup$ By the way, $c=1/2$ in Pomerance's paper. This value of $c$ is considered as current barrier of our knowledge. $\endgroup$ – Sungjin Kim Sep 1 '15 at 17:43
  • 7
    $\begingroup$ I thought you had in mind questions that "are entirely different" from the membership question: e.g. twin primes, Goldbach etc. For these questions, usually we have guesses for the answer (e.g. number of solutions to a, a+2 with a in some set) based on the size of the sets in question. My point is that the set of pseudoprimes is so small that this wouldn't affect such heuristics (and indeed it would be much harder for some such property to hold with one pseudoprime involved). $\endgroup$ – Lucia Sep 1 '15 at 17:43

The question of existence of large prime Fermat numbers $2^{2^n}+1$ is open, but the corresponding question for probable primes is straightforward to solve. $2^{2^n} \equiv -1 \mod 2^{2^n}+1$, so by squaring, we see that $2^{2^j}\equiv 1 \mod 2^{2^n}+1$ for all $j>n$. In particular, $2^n > n$, so we get a positive answer for all non-negative integers $n$.

This gives another way to deterministically generate probable primes, and as opposed to the iterated Mersenne method, we get a sequence that grows only doubly exponentially instead of by a "tower of exponentials".


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.