A partial answer, for the case $t = P(0) \neq 0$. By Kobayashi theorem, there are infinitely many odd primes dividing some term(s) of the sequence $(2^n + t)_{n\geq 1}$. Let $q\mid 2^n + t$ be one of these primes. Then $2^{nq} + P(nq) = 2^n(2^{q-1})^n +nqM + t \equiv 2^n + t \equiv 0 \pmod{q}$.

mavropnevma wrote: A partial answer, for the case $t = P(0) \neq 0$. By Kobayashi theorem, there are infinitely many odd primes dividing some term(s) of the sequence $(2^n + t)_{n\geq 1}$. Let $q\mid 2^n + t$ be one of these primes. Then $2^{nq} + P(nq) = 2^n(2^{q-1})^n +nqM + t \equiv 2^n + t \equiv 0 \pmod{q}$. Now, in the case $P(0)=0$, denote $U_n=2^n+P(n)$, and assume they have only a finite number of prime divisors $p_1, \ldots, p_k$, Take $N=p_1\cdots p_km$, with $m$ a large integer such that $\gcd (m,p_1\cdots p_k)=1$. Then $U_N=2^N+N\frac{P(N)}{N}$. Now, every odd $p_i$ does not divide $U_N$, and $2$ appears at most at the first power in $U_N$, but $|U_N|>2$ for some large enough $m$, at contradiction with our assumption.

I don't understand why you need $\gcd (m,p_1\cdots p_k)=1$. And "$2$ appears at most at the first power in $U_N$" is clearly not necessarily true; why could not $\dfrac {P(N)} {N}$ be divisible by a quite large power of $2$ ? Fortunately, this is irrelevant. For large $m$, $2^{N-1}$ is much larger than $|P(N)| \neq 0$; since $2^N + P(N)$ can have none of the odd prime divisors, it is only left the case it is some power of $2$, so $2^N + P(N) = 2^M$. We cannot have $M=N$, since $P(N) \neq 0$, and we cannot have $M<N$, since then $2^M - P(N) \leq 2^M + |P(N)| < 2^{N-1} + 2^{N-1} = 2^N$. Thus $M>N$, and then we need $P(N) = 2^M - 2^N \geq 2^N$, impossible.

what is Kobayashi theorem?

alibez wrote: what is Kobayashi theorem? It's something like this: If a sequence $(a_n)$ of natural numbers has only a finite number of distinct prime divisors, then for each integer $t\neq 0$, the sequence $(a_n+t)$ has infinitely many prime divisors.

We get $Q(m)=P(m)+1$ and Q is a polynomial(non constant) in $Z[x]$ and by ((Schur lemma)) we have set of prime numbers dividing at least one non-zero number between $Q(1),Q(2),...,Q(n),...$is infinite.so we get $q\mid Q(m)\Rightarrow q\mid Q(m+tq)\Rightarrow q\mid P(m+tq)+1$ .we know $2^{m+tq}\equiv 2^{m+t}mod(q)$ so if $m\equiv -t mod(q)$ then $q\mid P(m+tq)+2^{m+tq}$

A very similar idea to @above I think. The key insight is that $2^n\pmod{q}$ and $P(n)\pmod{q}$ are 'independent' in a sense, since the former is periodic $\pmod{q-1}$, whilst the latter is periodic $\pmod{q}$, and the two are coprime. The rest is then obvious; choose prime $q$ and integer $k$ such that $P(k)\equiv -1\pmod{q}$ (we are guaranteed infinitely many such pairs $q,k$ by Schur). Then choose $n\equiv k\pmod{q}$ and $n\equiv 0\pmod{p-1}$, which must certainly exist by CRT, and we are done.

I think we don't need Schur for this problem. assume $q_1,q_2,...,q_k$ are all prime divisors of this sequence.i want find a n such that number of $q_1$ in $2^{n+lq_1^m q_2^n ... q_k^n}+p(h+lq_1^m q_2^n ... q_k^n)$ remain bounded consider two case: case 1: there exist n such that $q_1|2^{q_2^n ... q_k^n}-1$ then we have $q_1^m|q_1|2^{q_1^m q_2^n ... q_k^n}-1$ so if $s<m$ and $q_1^s||2^h+p(h)$ then $q_1^s||2^{h+lq_1^m q_2^n ... q_k^n}+p(h+lq_1^m q_2^n ... q_k^n)$ for all $l$. case 2:easy now you can do it for every q_i and its contradiction

Let $n=x(q-1)$ for some $x$, and so we want to prove $2^n+P(n)=1+P(x(q-1))\equiv 1+P(-x) \equiv 0\mod q$ for infinitely many $q$. Now, let $A(x)=1+P(-x)$. We need to prove that as $x$ varies, infinitely many primes will divide $A(x)$. Assume otherwise. Then, let $b$ be the product of the primes that divide $A(x)$ for some $x$, and let $A(x)=xB(x)+t$. We have that $A(btx)\equiv t\mod bt$, and since asymptotically A must approach positive or negative infinity (it is a polynomial), for some $x$ we have $A(btx)=kbt+t=t(kb+1)$ for $k$ nonzero, which is not equal to $0\mod b$, contradiction.

Take $$n \equiv 1 ( mod q-1) $$, where $q$ is any add prime dividing $P(n) -2$ , which exist by Schur, in fact number of such primes are infinite, hence we are done. $\blacksquare$

goodar2006 wrote: $P(x)$ is a nonzero polynomial with integer coefficients. Prove that there exists infinitely many prime numbers $q$ such that for some natural number $n$, $q|2^n+P(n)$. Proposed by Mohammad Gharakhani take any prime $p$ such that it divides some term of the sequence $P(n)+2, n \ge 0$. suppose $p | P(x)+2$. Now consider the system of congruences $n \equiv 1 \pmod{p-1}, n \equiv x \pmod{p}$. By CRT, it has a unique solution $\pmod{p(p-1)}$ since $\gcd (p,p-1)=1$. Note that $p | 2^{n}-2$ and $p | P(n)+2$, adding them $p | P(n)+2^n$. Since the number of such primes $p$ is infinite by schur, we are done. $\blacksquare$