6
$\begingroup$

Cross-post: This very elementary question was first posted to Mathematics Stack Exchange but the response I got there (even after offering a bounty) was not useful.

For the purpose of this question, a pseudoprime is a composite number $n$ satisfying $2^{n-1} \equiv 1 \ (\text{mod}\,n)$, also known as a (composite) odd, weak Fermat pseudoprime to base two.

If we look at $n$ of the form $n=b^2+1$ we find many primes ($b$ in OEIS A005574) and pseudoprimes (A135590).

However, if we move to $n=b^4+1$ we still find many primes (A000068), but the only pseudoprimes we have been able to find are of the form $b=2^{2^k}$ which makes $n=b^4+1$ a Fermat number (which is obviously either prime or pseudoprime).

Question: If $b^4+1$ is composite but we still have $2^{b^4} \equiv 1 \ (\text{mod}\ b^4+1)$, will $b$ necessarily be of the form $2^{2^k}$?

If there is no obvious reason why this should be true, can someone provide some heuristics on the "expected" asymptotic behavior of such numbers $b$? A computer search seems to demonstrate that there are no examples $b \le 2\cdot 10^{10}$. Maybe there is a smarter way to locate an example?

Or maybe this has been asked/answered before in the literature?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ For comparison, there are many base 2 pseudoprimes of the form $n = b^3 + 1$, including $n = 1729$ and $n = 46657$. $\endgroup$
    – Jeremy Rouse
    Commented Mar 23, 2016 at 17:54
  • $\begingroup$ @JeremyRouse Yes, that is cool! Originally, I was mostly motivated by finding actual primes and how often a "probable prime" to base 2 would come out composite, and maybe for that reason I had not really considered $b^3+1=(b+1)(b^2-b+1)$. Now I am about to submit $12, 36, 138, 270, 546, 4800, \ldots$ to Sloane's OEIS. $\endgroup$
    – Jeppe Stig Nielsen
    Commented Mar 24, 2016 at 0:32
  • $\begingroup$ @JeremyRouse Somewhat interestingly, the $46657$ you mention is also the first pseudoprime we find with $b^2+1$ which means of course that we have a sixth power whose successor $n=6^6+1$ is a pseudoprime. If we disregard again Fermat numbers A000215, this appears to be the only case $n=b^a+1$ with exponent $a\ge 4$ one finds "immediately". $\endgroup$
    – Jeppe Stig Nielsen
    Commented Mar 26, 2016 at 20:30

1 Answer 1

Reset to default
10
$\begingroup$

Carl Pomerance conjectured in

On the Distribution of Pseudoprimes, Math. Comput. 37, 587-593 (1981)

that for large $x$, the number of pseudoprimes $\leq x$ is $$ \frac{x}{e^{(1+o(1))\log{x}\frac{\log{\log{\log{x}}}}{\log{\log{x}}}}} $$ If Pomerance's conjecture holds, for sufficiently large $x$ there are more than $x^{\frac{3}{4}}$ pseudoprimes $\leq x$. Now there are also about $x^{\frac{1}{4}}$ integers of the form $n^4+1$ in this range which are not Fermat numbers. Since $\frac{3}{4} + \frac{1}{4} = 1$, common heuristics suggest that for large enough $x$ there are coincidences, i.e. numbers which are both of the form $n^4+1$ (and not Fermat numbers) and pseudoprimes. Here we make the plausible assumption that the properties "$n$ is a pseudoprime" and "$n$ is of the form $b^4+1$, but not a Fermat number" are independent of one another.

The lack of examples for small numbers is easily explained by the $o(1)$ term converging to $0$ only slowly -- in fact there are only $118968378$ pseudoprimes below $x = 2^{64}$, which is just about $x^{0.419} < x^{0.75}$, cf. this table. The probability that two random subsets of $\{1, \dots, 2^{64}\}$ of cardinalities $118968378$ and $2^{16}$ intersect nontrivially is pretty low.

Exact counts of pseudoprimes up to the fourth power of your search limit $2 \cdot 10^{10}$ are not yet known, but it seems likely that $x$ must be considerably larger to push the count of pseudoprimes $\leq x$ above $x^{\frac{3}{4}}$. Thus finding an example of a pseudoprime of the desired form by means of computation may be very hard.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This was the kind of answer I was hoping for. For comparison, with $b^2+1$, looking at the subsets of $\{1,\ldots,2^{64}\}$, this time they have sizes $118968378$ and $2^{32}$, and the intersection turns out (long search completed) to have cardinality $31$ (excluding one Fermat number, $65536^2+1$). And with $b^3+1$ (Jeremy Rouse's comment to the question) subsets of sizes $118968378$ and $2^\frac{64}{3}$ (quick search!) give an intersection of size $11$. Some statistician may tell us if this is compatible (at some level of confidence) with the idea of stochastic independence of these sets. $\endgroup$
    – Jeppe Stig Nielsen
    Commented Mar 26, 2016 at 23:40

You must log in to answer this question.

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