If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $ a=b$

Question

I happened to receive this from my friend.

Let $a,b \in \mathbb{N}$, such that $a^{n}+n \: \bigl|\: b^{n}+n$ for all $n \in \mathbb{N}$. Prove that $a=b$. How do we proceed?

Answer 1

Hint $ $ excerpted from my $ $ sci.math post $ $ 2006/4/4 $ $ here or here (see there for much motivation), we can choose $\rm\,\color{#c00} n\,$ and $\rm\, p > |\color{blue}{b-a}|\,$ satisfying the LHS below, so the RHS $\rm\Rightarrow \color{blue}{b = a}$

$$\rm\quad\begin{align} \rm p-1 &\mid\rm \color{#c00}{n-1} \\ \rm p &\mid\rm \color{#0a0}{a+n} \\ \end{align}\! \Rightarrow\,\ p\mid \overbrace{a^{\large \color{#c00}n^{\phantom{I}}}\!\!\!-\!a+\color{#0a0}{a\!+\!n}}^{\Large a^n+n}\mid \overbrace{b^{\large \color{#c00}n^{\phantom{I}}}\!\!\!-\!b+\color{blue}{b\!-\!a}+\color{#0a0}{a\!+\!n}}^{\Large b^n +n} \ \,\Rightarrow\,\ p\mid \color{blue}{b-a}\qquad\qquad\quad $$

Answer 2

Claim if our hypothesis holds, $a \equiv b \ (\text{mod}\ p)$ for any prime $p$.

Proof:

Find $n$ so that $n \equiv -a \ (\text{mod}\ p)$ and $n \equiv 1 (\text{mod}\ p-1)$ ( we can do this by Chinese Remainder Theorem). Then

$$a^{n} + n \equiv a^1 + n = a - a = 0 (\text{mod} \ p)$$

Therefore since $a^n + n \mid b^n + n$, $b^n + n \equiv 0 (\text{mod}\ p)$

But

$$b^n + n \equiv b^1 + n \equiv b - a (\text{mod}\ p)$$

therefore $b \equiv a \pmod p$.

Our result now follows by picking any $p > b$.

NOTE by BD $\;$ This solution has been posted before in at least a few well-known math forums, e.g. see my sci.math post on April 4,2006, and see Rust's post on AoPS, July 19, 2009. It also appeared in at least one other forum much more recently (alas, I can't recall which one). Almost surely, by now the problem and solution is listed in various problem collections, so it should be considered somewhat well-known.

Answer 3

Chandru1 asks how we might proceed, so in that spirit let me offer an idea that provides partial results and connects this problem to a long-standing one recently characterized as a "frustrating question."

Let's aim to show that under the conditions assumed of $a$ and $b$, $a$ necessarily divides $b$. This additional relation suffices to show that $a = b$. (There does not seem to be a simple demonstration of this, but it is much easier than the original problem so I'll let it go for now as an "exercise.")

Suppose $b < a^2$. Then

$\left( \frac{b}{a} \right) ^n - \frac{b^n + n}{a^n+n} = \frac{n (b^n - a^n)}{a^n (a^n+n)}$.

The right hand side, in the limit of large $n$, approaches zero from above. The left hand side is the difference between $\left( \frac{b}{a} \right) ^n$ and an integer. We conclude that eventually the fractional part of $\left( \frac{b}{a} \right) ^n$ approaches zero. Results of Pisot, Vijayaraghavan and Andre Weil then imply that $\frac{b}{a}$ must be integral. (See Akayama et al., Powers of rationals modulo 1 and rational base number systems, http://perso.telecom-paristech.fr/~jsaka/PUB/Files/RBNS-rev.pdf .) The intuition is that the fractional parts of powers of non-integers ought to fill the interval [0, 1) in a fairly "random" way. Indeed, numerical experiments verify this for rational numbers (but not for all irrationals!): see http://mathworld.wolfram.com/PowerFractionalParts.html . So, convergence of the fractional part to zero--which is assured by the sequence of divisibility conditions in the problem--implies the ratio $b / a$ is not behaving like a proper fraction: it must actually be an integer. That gives us enough leverage to show the equality $a = b$.

I suspect a similar approach should work for $b \ge a^2$, but I haven't found it. Indeed some of the papers in the literature note changes in the behavior of powers of $b / a$ when $b$ exceeds $a^2$, so we should be cautious.

Finally, note that elementary methods of number theory show that all primes dividing $a$ must also divide $b$. That, however, doesn't seem to get us very far.

Answer 4

OK, after some days of struggling hard with this problem, i think i have found one more solution.

By Fermats little theorem, we have $$a^{p} + p \equiv a ( \text{mod} \ p)$$ and $$b^{p}+p \equiv b (\text{mod} \ p)$$

Next, $$\frac{b^{p}+p}{a^{p}+p}=\frac{k_{2}p+b}{k_{1}p+a} = C(\text{an integer})$$

Choose a prime $p$ such that $p \mid a$, then by the above we can see that $p \mid b$.

Similarly, we choose a prime such that $p \mid a$, then we have, $$\frac{k_{2}p+b}{k_{1}p+a}=\frac{k_{4}p}{k_{1}p+a} \Longrightarrow p\mid a \ \text{or} \ p=c$$

Now if $p=c$, then we will have $$\frac{b+1}{a+1}=p \Longrightarrow p\mid (p-1)$$ a contradiction. So $p \mid a$.

So we have concluded:

• Whenever $p \mid a \Longrightarrow p \mid b$

• Whenever $p \mid b \Longrightarrow p \mid a$.

Does this help!

Answer 5

UPDATE: the proof seems incorrect as b=4, a=2, fail when n=4 (check the comments below).

First, there is a counter example when n=1, where a=6 and b=13 (as $ (6+1) | (13+1) $ ). However I shall continue for all n>1.

If $(a^n+n) | (b^n+n)$ then there is a natural number k $\geq 1$ such that $b^n+n=k(a^n+n)$. Clearly $a=b \mbox{ iff } k=1$. We shall proceed to prove that k is always 1 for all n>1.

Continuing from $b^n+n=k(a^n+n)$,

$b^n+n \equiv 0 \quad (\mbox{mod } k)$

If we allow n to vary for the same a and b, then the only value for k that will make that equation hold for all n>1 is k=1, which implies that a=b.