Finding a sufficient condition for primes to be of the form $a^n+b$ with some fixed $n$

Question

Let $n\in\mathbb{N}$ be fixed. Given a prime $p$ and integers $a,b$ a necessary condition for $p=a+b^n$ is: $$p-a\equiv 0 \pmod{b^i}$$ for all $i\le n$. What must one add to these $i$-different conditions to find a sufficienct statement? We can assume $b\ne1$ as $a+1^n$ yields nothing of interest.

Also the statement need not to be computable in finite time (like checking countably many congruences for all naturals greater than $n$)

Any ideas? I'm very much stuck.

Addendum:

To clear things up where I'm coming from consider the following:

Let $n\in\mathbb{N}$ be fixed and $a,b$ integers such that $\gcd(a,b)=1$.

For a $X\subset\mathbb{N}$ we define the characteristic function \begin{align*} \Phi_{n,a,b}[X]:X&\longrightarrow \{0;1\}\\ x&\longmapsto \begin{cases}1&x=a+b^n\\0&\text{else}\end{cases} \end{align*} If we denote the set of primes by $\mathbb{P}$ my goal is to express $\Phi_{n,a,b}[\mathbb{P}]$ in terms of a (possibly infinite) collection of functions \begin{align*} \phi_{m,M}:\mathbb{N}&\longrightarrow \{0;1\}\\ k&\longmapsto \begin{cases}1&k\equiv m \pmod M\\0&\text{else}\end{cases} \end{align*} for some $m,M\in\mathbb{N}$ (for simplicity we can choose $0\le m<M$).

It would also be sufficient to find such an expression for $\Phi_{n,a,b}[\mathbb{N}]$, as $\Phi_{n,a,b}[\mathbb{N}]\Big\vert_\mathbb{P}=\Phi_{n,a,b}[\mathbb{P}]$.

Answer 1

I very much doubt anyone knows of a singular sufficient condition, that isn't something like the LLR (Lucas-Lehmer-Riesel test, Fermat primes and Mersenne primes would be among the beneficiaries) , Here are a few more necessary conditions you missed:

• $a$ and $b$ must be coprime, otherwise $b^n+a$ is divisible by their gcd.
• $a$ must not be congruent to $-1$ mod any of divisors of $b-1$ . Otherwise, by polynomial remainder theorem, the number $p$ is divisible by the divisors $a$ is congruent to $-1$ in mod.
• $a$ must not be congruent to $(-1)^{n-1}$ mod any divisors of $b+1$
• $a$ if negative, must not be in absolute value, a power, with exponent a divisor of $n$, unless in doing so, all but one of the algebraic factors turns out to be 1.
• In general $a$ and $b^n$ must not turn out to be additive inverses mod any prime not equal to $p$

There are more, but mostly repeating in a different way.

Addendum:

You can do the divisor conditions from $a$ onto $b^n$ as well.