There are several solutions. The \(1^{st}\) solution is based on positive construction. The other one is a hard-core solution. $\underline{\textbf{Solution 1}}$ Let $a = 2n-1$ and $b = 2n+1$ where $n$ is any integer. We can show that such $(a, b)$ is a qualified solution. Then, $$(2n \pm 1)^2 = 4n^2\pm4n+1 \equiv 1 \pmod{4n}$$ It follows that $$(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1 = 4n \equiv 0 \pmod{4n}$$ which is equivalent to $$a^b + b^a \equiv 0 \pmod{a+b}\quad\text{or}\quad (a+b)|(a^b + b^a)$$ $\underline{\textbf{Solution 2}}$ Let $n=a+b$. Because $a$ and $b$ are co-prime, then $a$ and $n$ are relatively prime too. Additionally, $a$ and $b$ cannot be both even. Without loss of generality, let's assume $a$ is odd. Therefore $$a^{n-a}+(n-a)^a \equiv 0 \pmod{n}\implies a^{n-a}+(-a)^a\equiv 0\pmod{n}$$ Because $a$ is odd, the above relation is equivalent to $$a^{n-a}\equiv a^a\pmod{n}\implies a^{n-2a}\equiv 1\pmod{n}$$ By Euler's theorem, we have $$a^{\varphi(n)}\equiv 1\pmod{n}$$ where $\varphi(n)$ is the totient function. Therefore, if we can show that $$n-2a=\varphi(n)$$ where $a$ is an odd integer has infinitely many solution, the problem will be solved. The previous equation is equivalent to $$a=\frac{n+\varphi(n)}{2}$$ Let $n=2p$ where $p$ is a prime and $p\equiv 1\pmod{4}$. Then $$\varphi(n) = 2p\left(1-\frac{1}{2}\right)\left(1-\frac{1}{p}\right) = p-1\implies a=\frac{n+\varphi(n)}{2}=\frac{2p+p-1}{2}=\frac{3p-1}{2}$$, Because $p\equiv 1\pmod{4}$, therefore $3p-1 \equiv 2\pmod{4}$ which means $a$ is odd. This means that $$b=n-a=\frac{p+1}{2}$$ What is left is to show that $a$ and $b$ are relatively prime. It is indeed the case by Euclidean algorithm $$\gcd\left(\frac{3p-1}{2},\frac{p+1}2\right)=\frac{\gcd(3p-1,p+1)}{2}=\frac{\gcd(p+1,4)}{2}=\frac22=1$$ Therefore, for all primes $p \equiv 1\pmod{4}$, the pair $\left(\frac{3p-1}{2},\frac{p+1}{2}\right)$ satisfies the criteria. Because there exist infinite many prime $p\equiv 1\pmod{4}$ (see %%HREF%%3871%%), therefore the original claim holds.