# 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 simple first step: If $p\mid a$ then $p\mid b$ (try $n=p$). And if $p\nmid a$ then $p\nmid b$ (try $n=p-1$) – Hagen von Eitzen Mar 17 '15 at 7:45
• @Hagen, Aha! Thanks! – mursalin Mar 17 '15 at 7:55

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.

• See my answer for one way to motivate the solution to the classic contest problem. – Bill Dubuque Mar 17 '15 at 18:28

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