Set of primes dividing $2^n+3^n$. Consider the set $$A=\{2^n+3^n\mid n\in \mathbb Z^+\}$$
Prove that the set of primes (call it $P$) dividing $A$ is infinite. (A prime is in $P$ iff it divides at least one element of $A$).
The "natural" way to do this is to assume the set $P=\{p_1,...,p_k\}$ is finite, and then construct an $n_o$ such that $2^{n_o}+3^{n_o}$ is divisible by a new prime not in $P$. But I tried a lot of things like $p_1p_2...p_k$ but they don't work. How am I supposed to approach this?
By the way this is just a special case of a more general problem. It replaces $2^n+3^n$ by $ab^n+cd^n$. But I think that solving the special case is enough to get an idea how to solve the general one.
 A: For the special case, here is a beautiful construction given by @achille hui in the comments.
Assume the set $P=\{p_1,...,p_r\}$ is finite (Note that $P$ doesn't contain $2$ and $3$). Consider $$N=\prod_{i=1}^r(p_i-1)$$
By the assumption there exists a prime $p_k\in P$ such that $p_k\mid 2^N+3^N$. But $$2^N+3^N\equiv (2^{\frac{N}{p_k-1}})^{p_k-1}+(3^{\frac{N}{p_k-1}})^{p_k-1}\equiv 2\pmod{p_k}$$
Therefore $p_k=2$ which is a contradicition.
A: Regarding the general case of
$$g(n) = ab^n+cd^n \tag{1}\label{eq1A}$$
for a bit simpler handling, assume that $a$, $b$, $c$ and $d$ are all positive integers. Also, as Peter's comment indicates, it doesn't work with $b = d$, but we don't require $\gcd(b,d) = 1$. Next, define
$$\gcd(a,c) = e, \; \; a = ea_1, \; \; c = ec_1, \; \; \gcd(a_1,c_1)=1 \tag{2}\label{eq2A}$$
$$\gcd(b,d) = f, \; \; b = fb_1, \; \; d = fd_1, \; \; \gcd(b_1,d_1)=1 \tag{3}\label{eq3A}$$
Thus, we get
$$ab^n+cd^n = ef^n(a_{1}b_{1}^{n}+c_{1}d_{1}^{\,n}) \tag{4}\label{eq4A}$$
We therefore just need to prove there's infinitely many distinct prime divisors of $a_{1}b_{1}^{n}+c_{1}d_{1}^{n}$. Have $\gcd(a_1,d_1)=\gcd(b_1,c_1)=1$ and $\gcd(b_1,a_1+c_1)=\gcd(d_1,a_1+c_1)=1$ (however, my other answer shows these additional coprimality conditions are not required). Note your specific case of $g(n) = 2^n+3^n$ is handled within these restrictions.
Assume there's only a finite number of such prime divisors, and let $P$ be the set of all such primes that do not divide $a_1 + c_1$ (note this means these primes divide $g(n)$ for some $n \ge 1$ so, by the coprime conditions given earlier, none of these primes divide $b_1$ or $d_1$). Then using the Euler's totient function, define
$$n = \varphi\left((a_1+c_1)^2\prod_{p\in P}p\right) \tag{5}\label{eq5A}$$
We then get
$$g(n) \equiv a_1 + c_1 \pmod{(a_1+c_1)^2\prod_{p\in P}p} \tag{6}\label{eq6A}$$
This shows that no $p \in P$ divides $g(n)$. Also, using the $p$-adic valuation function (e.g., where $\nu_{p}(z)$ is the exponent of $p$ in the prime factorization of $z$), then for any prime $p \mid a_1+c_1$, we have $\nu_p(g(n))=\nu_p(a_1+c_1)$. Thus, $g(n) = a_1+c_1$, but $g(n) \gt a_1+c_1$. This contradiction shows the original assumption is incorrect, so there's actually an infinitely many prime factors which divide some $g(n)$.
A: Regarding the general case of
$$f(n) = ab^n + cd^n \tag{1}\label{eq1B}$$
then with $a$, $b$, $c$ and $d$ being positive integers, the only requirement for the set of primes which divide $f(n)$ for at least one positive integer $n$ to be infinite in size is that $b \neq d$. As your comment indicates, the AoPS thread Exponential function with finitely many primes deals with this problem. However, most of the solutions there have various mistakes, in particular inappropriately assuming certain coprime conditions.
The following is a rearrangement, with some more details and other changes, of what's in post #6. First, as it states, and I've explained in more detail in my earlier answer, we can WLOG assume
$$\gcd(a,c) = \gcd(b,d) = 1 \tag{2}\label{eq2B}$$
Next, let $P$ be the set of primes which divide at least one of the values of the sequence $f(n)$ in \eqref{eq1B}. Assume $P$ has a finite number of elements, with $Q$ being the product of those primes which don't divide either $b$ or $d$. Note that $Q \gt 1$ since for any primes $p \in P$ which divide either $b$ or $d$, then the coprime conditions mean they divide $a$ (if $p \mid d$) or $c$ (if $p \mid b$). However, say for $p \mid d$ so $p \mid a$, then for large enough $n$ we have $\nu_p(ab^n +cd^n) = \nu_p(a)$, i.e., it's bounded above. This is also true for the other case. However, since $f(n)$ is unbounded, then it must have other prime factors, i.e., those used in producing the product $Q$.
Thus, for some integer $k \ge 1$, primes $q_i \in P$, any integer $j \ge 1$, and using Euler's totient function, we have
$$Q = \prod_{i=1}^{k}q_i, \;\; M = Q^{a+c}, \;\; s_{j} = j\varphi(M) \tag{3}\label{eq3B}$$
Thus, we also get
$$f(s_j) = ab^{s_j}+cd^{s_j} \equiv a + c \pmod{M} \tag{4}\label{eq4B}$$
This means there's an integer $r$ where $f(s_j) = a + c + rM$. The $a+c$ exponent used for $M$ in \eqref{eq3B} means, for any $q_i$ prime factor of $Q$, that $\nu_{q_i}(rM) \ge a + c$. Since $\nu_{q_i}(a+c) \lt a + c$, then $\nu_{q_i}(a+c) \lt \nu_{q_i}(rM)$, we get
$$\nu_{q_i}(f(s_j)) = \nu_{q_i}(a+c) \tag{5}\label{eq5B}$$
which means its bounded. This, along with the explanation earlier that the value of $\nu_p(f(n))$ for any prime $p \in P$ and $p \mid bd$ is also bounded, means the possible values of $f(s_j)$ are bounded, contradicting that $f(s_j)$ actually grows without bound. This contradiction means the finite assumption is incorrect, i.e., there are infinitely many elements in the set of primes $P$.
A: Here's a solution to the special case quite similar in spirit to the strategy posed in the question body.
Suppose $p\mid 2^n+3^n$. We claim that, for any positive integer $k$, $p\nmid 2^{2kn}+3^{2kn}$. Indeed,
$$2^{2kn}+3^{2kn}\equiv 2^{2kn}+(-2^n)^{2k}=2^{2kn}+2^{2kn}\equiv 2^{2kn+1}\pmod p$$
is not zero. So, suppose $\{p_1,\dots,p_s\}$ is a finite set of primes for which $p_i\mid 2^{n_i}+3^{n_i}$ for some integers $n_1,\dots,n_s$, and let $N=2n_1\cdots n_s$. We then have
$$p_i\nmid 2^N+3^N$$
for each $1\leq i\leq s$. This means that the set of primes which divide numbers of the form $2^n+3^n$ cannot be finite.
A: Comment : We can construct such n, for example take $p=13$ we may write:
$2^{12}\equiv 1\bmod 13\Rightarrow 2^{60}\equiv 1  \bmod 13$
Also:
$2^5\equiv 6\bmod 13 \Rightarrow 2^{10}\equiv -3\bmod 13$
Multiplying these relations we get:
$2^{70}\equiv -3\bmod 13$
Also we may write:
$3^3\equiv 1\bmod 13\Rightarrow 3^{69}\equiv 1 \bmod 13\Rightarrow 3^{70}\equiv 3\bmod 13$
summing these we get :
$2^{70}+3^{70}\equiv 0\bmod 13$
that is 13 is a prime factor of $2^{70}+3^{70}$
Another example; we use this question:
Find smallest composite n such that $2^n-2$ and $3^n-3$ be divisible by n.
The smallest n is 561 and next one is 1105, take this one; we may write:
$2^{1105}-2+3^{1105}-3 \equiv -5\bmod 1105\equiv 0\bmod 1105$
$1105=5\times 13\times 17$, So primes 5, 13 and 17 are factors of $2^{1105}+3^{1105}$
It is not known that these types of number are infinite but there are certainly more such number which can be found.
I do not think there is a limit for these numbers.
