My construction: let $d \equiv 1 \pmod 4$, $d > 1$. Let $x = \frac{d^d+2^d}{d+2}$. Then set \[ a = \frac{x+d}{2}, \qquad b = \frac{x-d}{2}. \]To see this works, first check that $b$ is odd and $a$ is even. Let $d = a-b$ be odd. Then: \begin{align*} a+b \mid a^b+b^a &\iff (-b)^b + b^a \equiv 0 \pmod{a+b} \\ &\iff b^{a-b} \equiv 1 \pmod{a+b} \\ &\iff b^d \equiv 1 \pmod{d+2b} \\ &\iff (-2)^d \equiv d^d \pmod{d+2b} \\ &\iff d+2b \mid d^d + 2^d. \end{align*}So it would be enough that \[ d+2b = \frac{d^d+2^d}{d+2} \implies b = \frac{1}{2} \left( \frac{d^d+2^d}{d+2} - d \right) \]which is what we constructed. Also, since $\gcd(x,d) = 1$ it follows $\gcd(a,b) = \gcd(d,b) = 1$. In fact, $(2n-1, 2n+1)$ works for any $n$. Oops.

Consider positive integers $(p,q)$ with $p>q.$ Note that $$(p+q)(p^{q-1}-qp^{q-2}+q^2p^{q-3}-\dots+q^{q-1})=p^q+q^q$$for odd $q$. Thus $$(p+q)(p^{q-1}-qp^{q-2}+q^2p^{q-3}-\dots+q^{q-1}+x)=p^q+q^q+x(p+q).$$Note that this is definitely a solution if $x=\frac{q^p-q^q}{p+q}$ and $x$ is an integer. We see that $$q^p\equiv q^q\pmod{p+q}$$when the order of $q\pmod{p+q}$ divides $p-q,$ which definitely happens if $\phi(p+q)\mid p-q.$ Now suppose $p+q=6r,$ where $r$ is a prime congruent to $2\pmod{3}.$ Then $\phi(p+q)=(p+q)\cdot \frac{r-1}{3r}$. Letting this be equal to $p-q,$ we see that $\frac{p(2r+1)}{3r}=\frac{q(4r-1)}{3r},$ thus generating a solution in relatively prime positive integers of $p=4r-1, q=2r+1.$ Since these sum to $6r, p+q$ has no other prime factors, and $q$ is odd as desired, so this is indeed a solution. Since there are infinitely many primes congruent to $2\pmod{3},$ there are infinitely many solutions.$\blacksquare$

Can you state that it is "well known" that there exist infinitely many primes 3 mod 8? If not, how many points would you lose?

I just did $2^n-1$ and $2^n+1$.

EDIT: Sniped.

@below that should be fine

I said by Dirichlet's Theorem of Arithmetic Progression, there exists infinite p of the form 4k+1. Would this be acceptable?

Simplest is I believe $2x+1$ and $2x-1$.

Let p be odd prime:

should be valid?

Wait crap I forgot to show $2^n+1$ and $2^n-1$ were relatively prime, hopefully that's obvious and I don't get marked down on it

Why so difficult? Let $p=4k+1$ be a prime. Then I claim that $a=2k+1$ and $b=6k+1$ work. Note that $\gcd(a,b)=1$ trivially. Now note that $2|a^b+b^a$ trivially so it suffices to show that $(4k+1)|a^b+b^a$. But note that $a^b+b^a=(2k+1)^(6k+1)+(6k+1)^(2k+1)\equiv (2k+1)^(2k+1)+(6k+1)^(2k+1)\equiv 0 (mod 4k+1)$.

This was trivial literally took me only 25 min got the same answer as post #13, thankfully I fixed that small error when quintuple checking my work

I got the construction $ \frac{(p+1)} {4}, \frac {3p - 1} {4}$ for all primes 3 mod 8.

How many points would this solution get?

Another construction: $a, a^2-a-1$ with $a$ odd

$\left(\frac{3p-1}{2},\frac{p+1}{2}\right)$ where $p\equiv 1 \pmod{4}$ is fine.

Note $(a,b)=(2p-1,2p+1)$ for odd prime $p$ works. We need $4p|(2p-1)^{2p+1}+(2p+1)^{2p-1}$. Considering mod 4 and mod p separately give that both are divisors Since $p$ odd, we have $HCF(4,p)=1$ so solution actually works. Infinitely many odd prime, so infinitely many soln. Full proof here: https://infinityintegral.substack.com/p/usajmo-2017-contest-review

Note that we need, \begin{align*} a^b + b^a \equiv 0 \pmod{a+b}\\ a^b + (-a)^a \equiv 0 \pmod{a+b} \end{align*}Take $a$ odd. Then we wish to find $a,b$ such that, \begin{align*} a^b \equiv a^a \pmod{a+b} \end{align*}Assume that $\gcd(a,b)=1$. Then clearly $\gcd(a, a+b) = 1$. Therefore we wish to find $a,b$ such that, \begin{align*} a^{a-b} \equiv 1 \pmod{a+b} \end{align*}Let $a-b = 2$ and $a+b = 4k$. Then $a = 2k+1$ and $b = 2k-1$. Thus we wish to show, \begin{align*} \left(2k+1\right)^2 \equiv 1 \pmod{4k}\\ 4k^2 + 4k + 1 \equiv 1 \pmod{4k}\\ 0 \equiv 0 \pmod{4k} \end{align*}Thus the curve $(a, b) = (2k+1, 2k-1)$ works.

Call an ordered pair $(a,b)$ working if and only if $a+b \mid a^b+b^a$ and $\gcd(a,b) = 1$. Thus no working pair has both $a,b$ even. Claim: $(a,b)$ works if and only if $a^{b-a} \equiv 1 \pmod {a+b}$. Proof: WLOG let $a$ be the odd term. $(a,b)$ works is equivlent to \[a^b \equiv -b^a \pmod {a+b} \iff a^b \equiv a^a \pmod {a+b}\]The since $\gcd(a,a+b) = \gcd(a,b) = 1$, this is equivlent to \[a^{b-a} \equiv 1 \pmod {a+b}\]$\square$. Now let $p$ be any odd prime and $q$ be a prime that's congruent to $-2 \pmod q$. Let $a = \frac{q-p}{2}$ and $b = \frac{q+p}{2}$. It's easy to check that $\gcd(a,b) = 1$. Thus $(a,b)$ works since \[\left(\frac{q-p}{2}\right)^p \equiv 1 \pmod q \iff -p^p \equiv 2^p \pmod q\]which is true by definition of $q$. Thus there are infinite $(a,b)$ since there are infinite $(p,q)$ by Dirichlet's.

$(a, b) = (2n-1, 2n+1)$ work. I don't even think there's much to say here because this is the first thing you really try anyways. Suffices $$(2n-1)^{2n+1} + (2n+1)^{2n-1} \equiv 2(2n+1)(2n-1)(2n) + (-1) + 1 \equiv 0 \pmod {4n},$$yay.

$(a,b)=(2n-1,2n+1)$ works as, \[(2n-1)^{2n+1}+(2n+1)^{2n-1}\equiv (-2n-1)^{2n+1}+(2n+1)^{2n-1}\equiv (2n+1)^{2n-1}\left(-(2n+1)^2+1\right)\equiv 0 \pmod {4n}\]

$(a,b)=(p+2,5p-2)$ such that $p\equiv 5(mod \ 6)$ holds. We know that there are infinitely many primes $\equiv 5(mod \ 6)$ by Drichlet. $\phi(6p)=2(p-1)$ which gives that $(p+2)^{5p-2}\equiv (p+2)^{p+2}\equiv -(5p-2)^{p+2}(mod \ 6p)\implies 6p|(p+2)^{5p-2}+(5p-2)^{p+2}$ as desired.$\blacksquare$

Consider $(a,b) = \boxed{(2k+1,2k-1)}$ for $k \ge 2$. Notice $\gcd(a,b)=1$, and modulo $(2k+1)+(2k-1) = 4k$ we have \[(2k+1)^{2k-1} + (2k-1)^{2k+1} \equiv \left(2k \tbinom{2k-1}{1} + 1\right) + \left(2k \tbinom{2k+1}{1} - 1\right) \equiv 8k^2 \equiv 0. \quad \blacksquare\]

Let $a=2^n-1$ and $b=2^n+1$ Then $a+b=2^n-1+2^n+1=2^n+2^n=2^{n+1}$. Note that $\phi(a+b)=2^n$ $a^b+b^a \equiv (2^n-1)^{2^n+1}+(2^n+1)^{2^n-1} \equiv 2^n-1+\frac{1}{2^n+1} \pmod {2^{n+1}}$ Note that $(2^n+1)^2 \equiv 2^{2n}+2^{n+1}+1 \equiv 1 \pmod {2^{n+1}}$, so $2^n+1 \equiv \frac{1}{2^n+1} \pmod {2^{n+1}}$. So $2^n-1+\frac{1}{2^n+1} \equiv 2^n-1 + 2^n+1 \equiv 2^{n+1} \equiv 0 \pmod {2^{n+1}}$

Sol:- We prove that $(a,b)=(\frac{3q-1}{2},\frac{q+1}{2})$ ,where $q$ is a prime such that $q \equiv 1 \pmod 4$ (it is well known that there are infinitely many such primes) , works. Firstly note that $2a=3q-1 \equiv 2 \pmod 4 \implies a$ is odd. $2b=q+1 \equiv 2 \pmod 4 \implies b$ is also odd. Note that $gcd(a,b)=gcd(\frac{3q-1}{2},\frac{q+1}{2})=gcd(2,\frac{q+1}{2})=1$. By Euler's theorem we have $a^{q-1} \equiv 1 \pmod {2q}$ , we have $q-1=a-b; 2q=a+b$. Thus $a^{a-b} \equiv 1 \pmod {a+b} \implies a^a \equiv a^b \pmod {a+b} \implies a^a \equiv -b^b \pmod {a+b}$. We are done.

My approach since this was not highly marked in Evan Chen's handout just to try "famous" coprime pairs, and went with $(a,b)=(2n-1,2n+1)$ which worked.

Surprised that there existed a construction which allowed one to get away so cheaply. We consider the pairs of the form $(a,b)=(2^n-1,2^n+1)$. We claim that all such pairs work which we will confirm below. Note that, by Lifting the Exponent Lemma, \[v_2((2^n-1)^{2n-1}+(2^n+1)^{2n-1}) = v_2(2^n-1+2^n+1)=v_2(2^{n+1})=n+1\]so, $2^{n+1} \mid (2^n-1)^{2^n-1} + (2^n+1)^{2^n-1}$ and since clearly, $(2^n-1)^2 \equiv 1 \pmod{2^{n+1}}$ for all positive integers $n$, it follows that \[(2^n-1)^{2^n+1}+(2^n+1)^{2^n-1} \equiv (2^n-1)^{2n-1}(2^n-1)^2 + (2^n+1)^{2^n-1} \equiv (2^n-1)^{2n-1}+(2^n+1)^{2n-1} \equiv 0 \pmod 2^{n+1}\]so it is clear that all such pairs indeed work, as desired.

Let $p$ be a prime of the form $8k+3$. Take $a=\frac{p+1}4,b=\frac{3p-1}4$. Then $a+b=p$ and we have $$\left(\frac{p+1}4\right)^{\frac{3p-1}4}+\left(\frac{3p-1}4\right)^{\frac{p+1}4}\equiv 4^{-\frac{3p-1}4}-4^{-\frac{p+1}4}\equiv 2^{-\frac{3p-1}2}-2^{-\frac{p+1}2}\equiv 2^{-\frac{p+1}2-(p-1)}-2^{-\frac{p+1}2}\equiv 0\pmod p.$$

Take the following construction. Let $(a,b) = (2a,4a^{2}-2a-1)$. This can be seen to work, since $$\phi(a+b) = \phi(2a-2) \phi(2a+2),$$and we can see that $a-b \mid \phi(a+b)$ must hold.

Here is how i tackled this problem. One of these numbers is odd. Let a be the odd one. Then our condition is equivalent to $a^b=-b^a=-a^a(mod a+b).$ Which means we just need to find numbers: $a^{a-b}=1(mod (a+b))$. if a-b is divisible by 3, then $a^{a-b}-1$ is divisible by $a^3-1$. Then we just choose $a^3-1=a+b$ which is $b=a^3-a-1$ where $a=1(mod (2))$ and $a=b=2(mod (3))$.