Too lazy to find solutions, here is a sketch which reduces the problem to finite case check. It's clear that $a^n+n$ has only prime divisors which are either $2$ or are a Fermat prime. Let $S$ be the set of these divisors. Then, we have that $$\frac{\phi(a^n + n)}{a^n+n} = \prod_{p \in S} \frac{p-1}{p}. \qquad (1)$$ Note that the RHS of $(1)$ is at least $$\prod_{i = 1}^{\infty} \frac{2^{2^i}}{2^{2^i}+1}.$$ We claim that $\frac{2^{2^i}}{2^{2^i}+1} \ge \left (\frac{2^{2^{i-1}}}{2^{2^{i-1}}+1} \right)^{\frac23}.$ Cubing and expanding, we want: $$2^{3 \cdot 2^i} \cdot (2^{2^{i-1}}+1)^2 \ge 2^{2^i} \cdot (2^{2^i}+1)^3.$$ This is easily verified. Using this estimate, it's clear that the RHS of $(1)$ is at least $\frac18$, and so therefore $\frac{2^n}{a^n+n} \ge \frac18.$ This immediately shows that if $a > 2,$ we get that $n < 6$. From here, we obtain that either $a = 1, a=2$ or $n < 6.$ If $a > 2, n<6$, the problem is trivial case checking. If $a = 1$, we get $n+1 > 2^n$ which is absurd. Hence, we just need to solve $\phi(2^n+n) = 2^n.$ If there is a prime divisor $p | 2^n+n$ which is at most $\sqrt{2^n+n}$, then $\phi(2^n+n) \le (2^n+n) \cdot \frac{\sqrt{2^n+n}-1}{\sqrt{2^n+n}}$. For large enough $n$, this is clearly at most $2^n$, and we win. Otherwise, suppose that $2^n+n$ is prime. Then $\phi(2^n+n) = 2^n+n-1 \Rightarrow n= 1$. $\square$

First it is obvious that we must have $a^n + n = 2^k *(2^{a_1} + 1)(2^{a_2} + 1)\dots (2^{a_t} + 1)$ and $k-1 + a_1 + a_2 +\dots + a_t = n$ or $a^n + n $ has only divisors $2$ and Fermat's primes with $v_p(a^n+n) = 1$. Note that $RHS$ increases when we have as much multipliers as possible, and decreases otherwise. It is easy to prove by induction (or it is clear according to the previous sentence) that $2^s + 1 \le 3^s$ so $LHS \le 3^n$ so $a < 3$ if $a=1$ then $LHS < RHS$ for all $n > 1$. So $a = 2$.If $RHS$ have more than two multipliers than $RHS \ge 3*2^{n - 1}= 2^n + 2^{n-1}$ but it is obvious wrong so $2^n + n = 2^n$ or $2^n + 1$. So the answers is $(2;1)$.

It's obvious that a^n+n=2^k.(2^{a1}+1)...(2^{am}+1) with 2^{ai}+1 is Fermat's prime, also if ai=aj then 2^n has divisor 2^ai+1 absurd so it all distinct. If k=0 then a1+..+an=n, by induction 2^s+1<=3^s so a<3 so a=2. By assumption, k-1+a1+..+an=n. If k>2, similarly 2^s+1<=3^s and 2^k<=3^(k-1) so a^n+n<3^n hence a<3, we have a=2. If k<=2, if exist ai>2 then 2^ai+1<=3^(ai-1) so a=2 too. Otherwise, ai=1,2 so we have 9 case {6,10,30,12,20,60} notice n>=3 so a^3+3<=60 so a={1,2,3}. If a=3 hence n={1,2,3} and we have o(4),o(11),o(30) have (a,n)=(2,1);(3,3) satisfy. Now consider a=2, hence a^n+n>2^(k+..+an)=2^(n+1) so n>2^n false by induction hence q.e.d!

this problem gets so easier using the estimation $\phi(n) > \sqrt{n}$ for all $n > 6$ You can just check the cases when $a^n+n \le 6$ And for the case when $a^n+n > 6$ using the estimation we get $\phi(a^n+n) = 2^n > \sqrt{a^n + n}$ and you can simply see that if $a \ge 4$ the inequality is wrong so you just have to check the cases when $a = 1,2,3$ which makes the work really easier