10
$\begingroup$

The complete question is already in the title but we shall provide some motivation as well.

We study generalized Fermat numbers defined by:

$$\mathrm{GF}(n,b) = b^{2^n}+1$$

where $b$ and $n$ are natural numbers and we are interested in cases where $\mathrm{GF}(n,b)$ is prime for high $n$. Be aware of the trivial identity:

$$\mathrm{GF}(n,b) = \mathrm{GF}(i,b^{2^{n-i}})\quad\mathrm{for}\quad i=0,\ldots,n-1$$

The special case $\mathrm{GF}(n,2)$ corresponds to the classical Fermat numbers. Note that these are all (weak) probable primes to base two (see below), but in all cases with $n>4$ that have been resolved is $\mathrm{GF}(n,2)$ composite.

Given a prime candidate $g=\mathrm{GF}(n,b)$ we first check if:

$$2^{g-1} \equiv 1 \pmod{g}$$

in which case $g$ is called a (weak) probable prime (to base two). We then go on to a deterministic primality test (which can be fast because the factorization of $g-1$ is known).

The question is if the last step is even necessary for $n>1$. For $n=1$ it is very easy to find numbers $\mathrm{GF}(1,b)=b^2+1$ that are probable prime but not prime (a situation in which we use the term pseudoprime); it happens for $b=216, 948, 1560, 4872, 8208, \ldots$ (OEIS A135590).

So for $n=2$ (which includes higher $n$ by the trivial identity above), are there any $b$ such that:

$$\mathrm{GF}(2,b)=b^4+1$$

is a pseudoprime (i.e. is a weak probable prime to base two but still composite)? Well, because by the trivial identity this includes the classical ("non-generalized") Fermat numbers $\mathrm{GF}(n,2)=\mathrm{GF}(2,2^{2^{n-2}})$ for $n>4$, the answer is yes. So we except the powers of two, and get:

Open question: If $b$ is even and not a power of two[*], can $b^4+1$ be a pseudoprime?

We have not been able to find any example (currently searched to $b<2.7\cdot 10^9$).

Heuristically, should one expect this to occur infinitely often (and with what asymptotic behavior)? For how long must we search?

Or maybe there is a simple non-existence proof?

This may have been studied before?


[*] Perhaps one should just require $b$ not on the form $2^{2^n}$.


Note: I have now cross-posted this to MathOverflow.

$\endgroup$
  • 4
    $\begingroup$ To be concise, you're asking whether it's possible for $2^{b^4}$ to be congruent to $1$ mod $b^4+1$, despite $b^4+1$ being composite, when $b$ is even but not a power of $2$? $\endgroup$ – Patrick Stevens Mar 7 '16 at 22:48
  • $\begingroup$ @PatrickStevens Yes, exactly, thank you. $\endgroup$ – Jeppe Stig Nielsen Mar 7 '16 at 22:53
  • $\begingroup$ If what @PatrickStevens said is the problem, then the answer is yes. I just wrote a little mathematica code and for b=6, $2^{b^4}=1 \mathrm{mod} b^4+1$ and 6 is even but not a power of 2. Unfortunately I can't offer much insight as to why it's true algebraically, but hopefully knowing this property can be satisfied helps! $\endgroup$ – aaron Mar 9 '16 at 23:39
  • $\begingroup$ If you want to double check, the line of code is Mod[2^(6^4), 6^4 + 1] $\endgroup$ – aaron Mar 9 '16 at 23:41
  • 2
    $\begingroup$ @aaron We already "crunched" a lot before posting this question, as I said below the "open question" box, so I know it is challenging to resolve in that way ;-) $\endgroup$ – Jeppe Stig Nielsen Mar 10 '16 at 0:13

Your Answer

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

Browse other questions tagged or ask your own question.