If $a$ and $b$ are positive integers such that $a^n+n\mid b^n + n$ for all positive integers $n$, prove that $a=b$. I ran into this problem in a math camp, but I can't seem to solve it via elementary techniques. 
If $a$ and $b$ are positive integers such that $a^n+n\mid b^n + n$ for all positive integers $n$, prove that $a=b$.
 A: Assume the contrary and consider a prime $p$ that does not divide $b-a$, By the Chinese Remainder Theorem we can find a postive integer $n$ such
$$\begin{cases}n\equiv 1\pmod{p-1}\\
n\equiv -a\pmod p
\end{cases}$$
Then by Fermat's little theorem
$$a^n+n\equiv a+n\equiv a-a\equiv 0\pmod p$$
and 
$$b^n+n\equiv b+n\equiv b-a\pmod p$$
It follows that $p$ divides $a^n+n$,But does not divide $b^n+n$.Contradiction.
A: Hint $ $ Little Fermat kills evil powers.  Below is a simple way to discover a proof. $ $ We prove the contrapositive, i.e. assuming $\,a\neq b\,$ we construct a counterexample to the divisibility claim.
To disprove $\,a^n+n\mid b^n+n\,$ we find a prime $\,p\,$ and some $\,n\,$ such that $\,p\mid a^n+n,\,$ $\,p\nmid b^n + n.\,$ To simplify, we can kill the exponents by restricting to $\,\color{#0a0}{n\equiv 1}\pmod{p\!-\!1},\,$ thus, by little Fermat, it follows that $\,a^n\equiv a,\,b^n\equiv b\pmod p,\,$ so our counterexample conditions simplify mod $p\,$ to
$$\begin{align} p\mid a^n+n\iff&\ 0\equiv a^n+n\equiv a+n\iff \color{#c00}{n\,\equiv\, -a}\!\!\pmod p\\ p\nmid b^n+n\iff&\ 0\not\equiv\, b^n+n\equiv b+\color{#c00}n\iff 0\not\equiv \color{}b\!\color{#c00}{-\!a}\!\!\pmod p\end{align}\quad\ $$
Thus we can construct a counterexample by choosing a prime $\,p\nmid \color{#a6f}{b\!-\!a}\,$ and a solution $\,n\,$ to
$$\begin{align} \color{#0a0}{n\ \,\equiv\,\ 1}&\pmod{p\!-\!1}\\ \color{#c00}{n\equiv -a}&\pmod p\end{align}\quad$$
By $\,p,\,p\!-\!1$ coprime, a solution $\,n\,$ exists by CRT = Chinese Remainder Theorem. $ $ QED
Remark $\ $ The following is a "proof without words" summary of the inferences
$$\begin{align}
  p-1  &\mid \color{#0a0}{n-1} \\
  p\,&\mid \color{#c00}{a+n} \\
\end{align} \Rightarrow\,\ 
p\mid \overbrace{a^{\large \color{#0a0}n^{\phantom{I}}}\!\!\!-\!a+\color{#c00}{a\!+\!n}}^{\Large a^n+n}\mid \overbrace{b^{\large \color{#0a0}n^{\phantom{I}}}\!\!\!-\!b+\color{#a6f}{b\!-\!a}+\color{#c00}{a\!+\!n}}^{\Large b^n +n} \ \Rightarrow\,\ p\mid \color{#a6f}{b\!-\!a}\,\Rightarrow\!\Leftarrow\qquad$$
