It is well known that a polynomial $$f(n)=a_0+a_1n+a_2n^2+\cdots+a_kn^k$$ is composite for some number $n$.

What about the function $f(n)=a^n+b$ ?

Do positive integers $a$ and $b$ exists such that $a^n+b$ is prime for every natural number $n\ge 1$ ?

I searched for long chains in order to find out whether there is an obvious upper bound. For example $4^n+4503$ is prime for $n=1,\ldots,14$.

  • 3
    $\begingroup$ I think there is no known strictly increasing function producing only prime numbers (and hence arbitrary large prime numbers) other than the Eratosthene sieve or the one extracting all the prime numbers from $a n+1$ or those kind of (very hardly computable) functions. So in general you'd like to prove if there are (or not) an infinity of primes in $f(n)$, but not that it outputs only primes. $\endgroup$ – reuns May 9 '16 at 22:03
  • 4
    $\begingroup$ It is known that there exists a real number $a$ such that the integer part of $a^{3^n}$ is prime for all $n\ge 1$. But since $a$ cannot be completely calculated, this formula does not count. $\endgroup$ – Peter May 9 '16 at 22:05
  • $\begingroup$ I guess this statement is general for any sequence of integers such that $f(n) \sim n \ln n$ ? $\endgroup$ – reuns May 9 '16 at 22:20
  • 7
    $\begingroup$ Does $a=1, b=p-1$ work? :-) $\endgroup$ – lhf May 10 '16 at 1:10

The answer to your question is no. For any $a>1,b\geq 1$ there will always exists $n$ such that $a^n+b$ is composite.

Suppose that $a+b$ is prime, (otherwise we are finished) and consider $n=a+b$ and look at $a^{a+b}+b$ modulo $a+b$. Then by Fermat's little theorem, which states that $$a^p\equiv a\pmod{p}$$ for any prime $p$, it follows that $$a^{a+b}+b\equiv a+b\equiv 0\pmod{a+b},$$ and so $a^{a+b}+b$ is divisible by $a+b$ and hence it is composite.

  • 1
    $\begingroup$ So, in short, one or both of $n=1$ or $n=a+b$ will give a composite. $\endgroup$ – Akiva Weinberger May 11 '16 at 13:05

If there were such a function, then we wouldn't be talking about "largest prime yet discovered". We'd have an infinite number of them at our disposal. So no... we have no such closed form function.


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.