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$.

Solution 1:

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.

Solution 2:

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$$