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?

$\endgroup$
  • 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 Mar 23 '16 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 Mar 24 '16 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 Mar 26 '16 at 20:30
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.

$\endgroup$
  • 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 Mar 26 '16 at 23:40

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.