Let's nail this. I claim all such $f$ are (a) $f(x)=1$ for all $x\in\mathbb{N}\setminus\{1,2\}$ and $f(1),f(2)\in\{1,2\}$ (all such four functions work). Note that taking $(a,b)=(1,2)$, we find $f(f(1)+2)\mid 1$, that is $f(f(1)+2)=1$. Now, $(a,b)=(1,3)$ implies $f(f(1)+3)\mid 2$. Claim. $f(f(1)+3)=1$. Proof of Claim. Suppose $f(f(1)+3) = 2$. Take $(a,b)=(f(1)+3,f(1)+1)$ to obtain \[ f(f(a)+b) = f(f(1)+3) = 2 \mid (f(1)+1)^{f(1)+3} - 1 \implies f(1)\equiv 0\pmod{2}. \]Now, take $(a,b)=(f(1)+2,f(1)+2)$ to obtain \[ f(f(a)+b) = f(f(f(1)+2) +f(1)+2) = f(f(1)+3) = 2 \mid (f(1)+2)^{f(1)+2} -1 \implies f(1)\equiv 1\pmod{2}. \]A contradiction is reached. Consequently, $f(f(1)+3)=1$. Having shown the claim, we now compare (i) with $(a,b)=(f(1)+2,b)$ and $(a,b)=(f(1)+3,b)$, while we keep in mind $f(a)=1$ for $a\in\{f(1)+2,f(1)+3\}$. This yields, \[ f(b+1)\mid b^{f(1)+2}-1 \qquad\text{and}\qquad f(b+1)\mid b^{f(1)+3}-1 \implies f(b+1)\mid b-1, \]for all $b\in\mathbb{N}$. In particular, using $ f(b+1)\mid b-1$ for $b\ge 2$, we find $f(n)\le n-2$ for all $n\ge 3$. Now, if there is an $a$ such that $f(a)\ge 3$, then $f(f(a)) \le f(a)-2$ whereas $f(f(a))\ge f(a)-1$, a contradiction. Hence, $f(n)\in \{1,2\}$ for all $n$. Now, $f\equiv 1$ clearly works; whereas $f\equiv 2$ clearly fails (by taking $b$ even). Assume, henceforth, that $f(k)=1$ for some $k$ and $f(k')=2$ for some $k'$. Take $a=k$. We have $f(b+1)\mid b^k-1$. In particular, if $b\ge 2$ is such that $f(b)=2$, then $b$ must be even. Now, take $a=k'$ to have $f(b+2)\mid b^{k'}-1$. In particular, if $b\ge 3$ is such that $f(b)=2$, then $b$ must be odd. Hence, there is no $b\ge 3$ such that $f(b)=2$. That is, $f(b)=1$ for all $b\ge 3$. In particular, there are now four candidate solutions: $f(x)=1$ for all $x\ge 3$, whereas $f(1),f(2)\in\{1,2\}$. It is seen easily all four functions enjoy the condition. This concludes the problem.

If $f(x)>f(1)$ and $f(x) \ge f(1)+2$, $P(1,f(x)-f(1)) \implies f(x)-1\le f(f(x))|f(x)-f(1)-1 \implies $ contradiction. Thus $f(x)\le f(1)+1$ which shows $f(x)$ has an upperbound. We have $f(f(1)+p+1)\in \{1,p\}$. For prime numbers $p$ big enough we have $f(f(1)+p+1)=1$. $1)$ If there exists $t$ such that $f(t)=f(1)+1$: From the second condition $f(f(t)) \in \{f(1),f(1)+1\}$. $i)$ $f(f(t))=f(1)$: $P(1,f(t)-f(f(1)+p+1))\implies f(1)=1$. If there exists $x$ such that $f(x)\ge 3$, $P(1,f(x)-1) \implies f(f(x))|f(x)-2$ which contradicts with the second condition. Thus $f(x)\in \{1,2\}$. $P(1,2k) \implies f(2k+1)=1$ for $k \ge 1$. If there exists $c$ such that $f(c)=2, P(c,2k) \implies f(2k+2)=1$ for $k\ge 1$. Thus $t=2$ from $f(t)=f(1)+1$, this gives contradiction because $f(f(t))=f(1)$. If there is no such $c$, $f(t)=1$. Contradiction. $ii)$ $f(f(t))=f(1)+1$: $P(t,b)$ and $P(1,b+1) \implies f(b+f(1)+1)=1$. $P(N,b)$ for $N \ge b+f(1)+1 \implies f(b+1)|b-1$. If there exists $x$ such that $f(x) \ge 3$ plugging $b=f(x)-1$ in the last equation gives $f(f(x)) \le f(x)-2$ which is a contradiction from the second condition. Thus $f(x)\in \{1,2\}$. Plugging $b=2k$ in $f(b+1)|b-1$ gives $f(2k+1)=1$ for $k\ge 1$. If there exists $c$ such that $f(c)=2, P(c,2k) \implies f(2k+2)=1$ for $k\ge 1$. We have $f(t)=2 \implies t=2$. Function: $f(2)=2$ and $f(x)=1$ otherwise. $2)$ $f(x) \le f(1)$: $f(f(1)) \in \{f(1),f(1)-1\}$ If $f(x)=f(1)$ for all $x$, $f(f(1)+p+1)=1 \implies f(x)=1$. Otherwise: Plugging $b=f(1)-f(a) \implies f(f(1))|(f(1)-f(a))^a-1$__* $i)$ $f(f(1))=f(1)-1:$ Plugging $a=f(1)+p+1$ in $f(f(1))|(f(1)-f(a))^a-1 \implies f(f(1))=1$, $f(1)=2$, $f(2)=1$. $P(1,b)$, $P(2,b) \implies f(x)=1$ when $x\neq 3k$ and $f(3k)|3$. If there exists $3c>3$ such that $f(3c)=3$ then $f(3)=3$ from the second condition. $P(3,3c-3)$ shows only $f(3) \in \{1,3\}$ and $f(x)=1$ for $x> 3$. $P(5,2) \implies f(3)=1$. Function: $f(1)=2,f(x)=1$ otherwise. $ii)$ $f(f(1))=f(1):$ $P(1,b) \implies f(f(1)+b)|b-1 \implies f(b) \le b-f(1)-1$ for $b \neq f(1)+1$. Plug $f(b)$ into $b$. We have $f(b)-1 \le f(f(b)) \le f(1)+1-f(b)$__** for all $b$. Assume $f(1) \neq 1,2$. Plug $t=(\phi(f(1))+1)$ in *. We have $f(t)=f(1)-1$. Thus combining this with ** for $b=t$ gives $f(1) \le 4$. If $f(1)=4$, $f(t)=3$, $f(4)=4$.$P(t,b)$, $P(4,b)$ gives $f(x)$ is odd for $x \ge 5$. We have $f(f(1)+3)=1,2 \implies f(7)=1$. P(7,3) gives a contradiction. For $f(1)=3$ we have $f(x)$ is odd for $x \ge 4$ thus $t=2$. $P(2,1)$ gives a contradiction. If $f(1)=2, f(2)=2$. We have $f(x) \le f(1)$. $P(1,2k) \implies f(2k+2)=1$. If there exists odd $c$ such that $f(c)=1$, $P(c,2k) \implies f(2k+1)=1$. Otherwise we have $f(x)=2$ which gives a contradiction. Function $f(1),f(2)=2,f(x)=1$ otherwise. If $f(1)=1$ we have $f(x) \le f(1)$ Function: $f(x)=1$

SerdarBozdag wrote: $1)$ If there exists odd $t$ such that $f(t)=1$: $P(t,a-1)\implies f(a)\in \{1,2\}$ for $a\ge 2$. $P(t,2k) \implies f(1+2k)=1 \implies f(x)=1$ for odd $x\ge 3$. @above I couldn't see how we obtained this could you elaborate? Let $P(a,b)$ denote the assertion $f(f(a) + b) \mid b^a - 1$. For convenience, set $f(1) = c$. $P(1,b) \implies f(b + c) \mid b - 1$. So we have $f(b) \mid b - c - 1$ for all $b > f(1)$. If there exist $n$ such that $f(n) > f(1)$, then interchanging $b$ with $f(n)$ we get $f(f(n)) \mid f(n) - c - 1$. But that is clearly a contradiction since $f(n) - 1 \leq f(f(n)) \leq f(n) - c - 1 \implies c\leq 0$. So $f(n) \leq f(1)$ for all positive integers $n$. Now for all primes $p > f(1)$, we have $f(f(1) + p + 1) = 1$. $P(1,2) \implies f(f(1) + 2) \mid 1 \implies f(f(1) + 2) = 1$. P.S (Wrong after here since we are not guaranteed to have a prime satisfying $\gcd{(c+2 , p-1)} = 1$. ) $P(f(1) + 2, b) \implies f(b+1) \mid b^{c+2} - 1$. Now choose a prime $p > f(1)$ such that $\gcd{(c+2 , p-1)} = 1$. $P(f(1) + p + 1,b) \implies f(b+1) \mid b^{c+p+1} - 1$. So, $f(b+1) \mid b^{\gcd{(c+p+1,c+2)}} - 1 = b - 1$ for all $b$. In particular, $f(b+1) \leq b-1$ for all $b\geq 2$. Now if there exist $m\geq 3$ such that $f(m) \geq 2$, then interchanging $b$ with $f(m) - 1$, we have $f(m) - 1 \leq f(f(m)) \leq f(m) - 2 \implies 1\leq 0$, contradiction. So, $f(n) = 1$ for all $n\geq 3$. Now if $f(1) \geq 3$, we have $1 = f(f(1)) \geq f(1) - 1 \geq 2$, contradiction. Same argument works for $f(2)$. So we have $f(1) , f(2) \in \{1,2\}$. It is easy to see that all such functions work. We are done.