Hello again! :welcomeani:

I know this is a direct application of Zsigmondy's theorem (with base cases exception, of course), but I'd like to present other (instructive) solution.
Any flaws or misstypes that you find you can tell me, I'd like to know. Any kind of constructive feedback is welcomed!

Solution:

Let $a \sim b$ denote that $a$ has the same prime divisors as $b$ and vice versa, that's the same as saying that for a prime $p$ , $p|a \iff p|b$ .

Lemma: $\boxed{a^m+1 \sim a+1}$
First note that if $a^m+1 \sim a+1$ , then writing $a+1=p_1^{\alpha_1} \dots p_k^{\alpha_k}$ and $a^m+1=p_1^{\beta_1} \dots p_k^{\beta_k}$ we just take $n \geq \dfrac{\beta_i}{\alpha_i} \implies \alpha_i n \geq \beta_i \implies a^m+1|(a+1)^n$ (because every prime power in $(a+1)^n$ that is $\alpha_i n$ would be greater than $\beta_i$ due to how we defined $n$ ), so if $(a, m)$ satisfy $a^m+1 \sim a+1$ it tells us there are infinitely many suffuciently large $n$ for which $a^m+1|(a+1)^n$ . So in fact $(a, m)$ such that $a^m+1 \sim a+1$ give us solutions, we just need to prove that all $(a,m)$ solutions are of that form. Let $p$ be any prime divisor of $a^m+1 \implies p|a^m+1|(a+1)^n \implies p|(a+1)^n \implies p|a+1$ , so all prime divisors of $a^m+1$ appear in $a+1$ as well. Suppose $m$ is even, write it as $m=2m_0$ and take a prime divisor $p$ of $a^{2m_0}+1 \implies p|a^{2m_0}+1|(a+1)^n \implies p|a+1 \implies a \equiv -1 \pmod{p} \implies a^{2m_0} \equiv (-1)^{2m_0} \equiv -1 \pmod{p}$ , but $(-1)^{2m_0}=1 \implies 1 \equiv -1 \pmod{p} \implies p|1-(-1)=2 \implies p=2$ . It means that every prime divisor of $a^{2m_0}+1$ is 2, so it's a power of 2 $\implies a^{2m_0}+1 = 2^k$ for some $k \geq 1$ . If $k = 1 \implies a=1$ and in fact $\boxed{(1,m,n)}$ works for all positive integers $m,n$ . Now, suppose $k \geq 2 \implies 4|2^k \implies 4|a^{2m_0}+1 \implies (a^{m_0})^2 \equiv -1 \pmod{4}$ , but -1 isn't a quadratic residue modulo 4! So $m$ is odd $\implies a^m+1=(a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \implies a+1|a^m+1$ , so every prime divisor of $a+1$ must be a prime divisor of $a^m+1$ as well $\square$

Suppose $m > 1$ because $\boxed{(a,1,n)}$ works for $a,n$ positive integers. As we have $a^m+1 \sim a+1$ , that is $p|a^m+1 \iff p|a+1$ , but $p|a+1 \implies p|a^m+1$ , so we will only use that $p|a^m+1 \implies p|a+1$ . Choose $p$ to be a prime divisor of $(a^{m-1}-a^{m-2}+ \dots -a+1)$ , but because $a^m+1=(a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|a^m+1 \implies p|a+1 \implies a \equiv -1 \pmod{p}$ $\implies$ $a^{m-1}-a^{m-2}+ \dots -a+1 \equiv (-1)^{m-1}-(-1)^{m-2}+ \dots -(-1)+1 \equiv \underbrace{1+1+ \dots +1+1}_{m \text{ times}} \pmod{p}$ because $m$ is odd so $m-1$ is even and $m-2$ is odd... But $a^m+1 \equiv 0 \pmod{p} \implies m \equiv 0 \pmod{p}$ for all prime divisors $p$ of $(a^{m-1}-a^{m-2}+ \dots -a+1)$ . Which means that $p|(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|m$ . But notice that $p|(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|a+1$ because $a^m+1 = (a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \sim a+1$ , so by the LTE lemma we have that $V_p(a^{m-1}-a^{m-2}+ \dots -a+1)=V_p(\dfrac{a^m+1}{a+1})=(V_p(a+1)+V_p(m))-V_p(a+1)=V_p(m)$ because $p|a+1$ , so every prime divisor $p$ of $(a^{m-1}-a^{m-2}+ \dots -a+1)=\dfrac{a^m+1}{a+1}$ is in $m$ and $V_p(\dfrac{a^m+1}{a+1})=V_p(m)$ , thus $\dfrac{a^m+1}{a+1}|m$ .

Now we just do case work because $\dfrac{a^m+1}{a+1}|m \implies \dfrac{a^m+1}{a+1} \leq m$ and $\dfrac{a^m+1}{a+1}=(a^{m-1}-a^{m-2}+ \dots -a+1)$ is growing as $a$ grows, so $\dfrac{a^m+1}{a+1} \geq \dfrac{2^m+1}{3} \implies 3m-1 \geq 2^m$ , but $2^m > 3m-1$ for $m \geq 4$ and $m$ is odd, so $m=3$ ( $m=1$ already seen) $\implies n \geq 2$ and in fact $\boxed{(2,3,n)}$ works for all integers $n \geq 2$ . If $a=3 \implies 4m-1 \geq 3^m$ but for $m \geq 2$ we have that $3^m > 4m-1$ and if $a \geq 4$ we get $m \leq 1$ , finishing cases.