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

  • 3
    $\begingroup$ 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$) $\endgroup$ – Hagen von Eitzen Mar 17 '15 at 7:45
  • $\begingroup$ @Hagen, Aha! Thanks! $\endgroup$ – 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.

  • $\begingroup$ See my answer for one way to motivate the solution to the classic contest problem. $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.