Are there infinitely many pairs of $(a, b)$ of relatively prime integers $a > 1$ and $b > 1$ such that $a^b+b^a$ is divisible by $a+b$?
I've spent almost two hours on this question to no avail. The small cases I have tried, such as $(3, 5)$, $(3, 7)$ and $(5, 7)$ all work, so I'm conjecturing that the answer is yes. However, all methods of proof I have tried have failed. Tried modulo arguments but can't really simplify my results.
Any help would be greatly appreciated.
On
Sure, choose for example $a=2k-1,b=2k+1$ for any integer $k$. Clearly these pairs are coprime, and we have
\begin{align} a^b+b^a&=(2k-1)^{2k+1}+(2k+1)^{2k-1}\\ &\equiv -1+(2k+1)2k+1+(2k-1)2k\tag{*}\\ &=8k^2\\ &\equiv 0 \pmod{4k}. \end{align}
where $(*)$ follows from Binomial theorem for example (or see jgon's answer for alternative argument). So $a^b+b^a \equiv 0 \bmod {a+b}$ since $a+b=4k$.
Sil posted a now deleted almost correct answer, so this is based on those ideas. (The answer has since been undeleted and corrected)
Let $a=2k-1$, $b=2k+1$ for any integer $k$. $a,b$ are coprime. $a+b=4k$.
Note that $$ab=4k^2-1 \equiv -1 \pmod{4k},$$ $$a^2 = 4k^2 - 4k +1 \equiv 1 \pmod {4k},$$ $$b^2 = 4k^2 + 4k +1 \equiv 1 \pmod {4k}.$$ Since $ab\equiv -1\pmod{4k}$, $b^{-1} \equiv -a\pmod{4k}$.
Then $$ a^b+b^a =a^{2k+1}+b^{2k-1} \equiv a^1 + b^{-1} \equiv a-a =0\pmod{4k}. $$
Thus $a^b+b^a \equiv 0\pmod{a+b}$, so $a+b\mid a^b+b^a$.
Hence we have found infinitely many such pairs.