21
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 13
    $\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
    Commented Sep 1, 2015 at 15:48
  • $\begingroup$ It may help to look @Distribution of the number of prime factors. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 14, 2016 at 0:05

4 Answers 4

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Indeed :-) Probably more complicated proof for p prime is from the factorization of $2^p-1$. $\endgroup$
    – joro
    Commented Sep 2, 2015 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
    Commented Sep 2, 2015 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
    Commented Sep 3, 2015 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 ♦
    Commented Sep 3, 2015 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
    Commented Sep 3, 2015 at 9:37
19
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 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
    Commented Sep 1, 2015 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
    Commented Sep 1, 2015 at 17:43
  • 8
    $\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
    Commented Sep 1, 2015 at 17:43
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

There are infinitely many probable primes of the form $(n-1)^2+1$.

This generalizes to more polynomial since Fermat numbers satisfy $F_n=(F_{n-1}-1)^2+1$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .