Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a>1$ and $b>1$ such that $a^b+b^a$ is divisible by $a+b$.
So I have a solution involving mod-bashing, Euler's theorem and the Euclidean Algorithm, but it's quite disgusting. Can anybody help me find a better solution? Thanks.
Take $a=2n-1, b=2n+1, n\geq 2$. It is obvious that $\gcd(a,b)=1$, and that $a,b>1$.
Note that
$$a^2 = 4n^2-4n+1 \equiv 1 (\bmod 4n)$$ $$b^2 = 4n^2+4n+1 \equiv 1 (\bmod 4n)$$ So
$$a^b+b^a = a(a^2)^n+b(b^2)^{n-1} \equiv $$ $$a\cdot 1^n + b\cdot 1^{n-1} \equiv a+b = 4n \equiv 0 (\bmod 4n)$$
Since $a+b=4n$, all such pairs work, and we are done.
There you go, no Euclidean stuff now.