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

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?

• @Ninefingers: I think it is safe to assume that "divides" means "divides with integer quotient", and, since $a^n+n$ and $b^n+n$ will be positive, that quotient will be positive. Sep 3, 2010 at 20:40
• if we knew there was a prime number of the form $b^n+n$ we would be able to conclude. I'm not sure if there always is one of this form?
– anon
Sep 3, 2010 at 20:56
• "5^n+n is never prime" ????? Sep 4, 2010 at 2:29
• Sep 6, 2010 at 6:56
• My claim that 5^n+n is never prime is actually false as n=7954 is a counterexample
– user899
Sep 6, 2010 at 10:21

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

• @Bill: Thanks for the solution.+1
– anonymous
Sep 5, 2010 at 2:36
• @Bill: Didn't understand how $p-1 \mid n-1$
– anonymous
Oct 23, 2010 at 15:15
• @Chandru1: Obviously one may choose n, p > |b-a| to satisfy the LHS, so the RHS implies a = b. You can find detailed motivation for the proof in one of my sci.math posts in said thread, namely groups.google.com/… Oct 23, 2010 at 15:36
• @Bill: the problem in the sci.math is it's not in latex and i finding it intricate to understand. Anyhow thanks
– anonymous
Oct 23, 2010 at 17:23
• @Chandru1: When using Google Groups on sci.math, to get proper layout be sure you choose the option to use a fixed-width font, cf. groups.google.com/support/bin/answer.py?hl=en&answer=46239, or else choose "Show Original". Oct 23, 2010 at 17:32

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.

• So question is asked and answered by the same person and the answer is actually precisely the same as solution to the same question on another forum?? Hmm... Sep 4, 2010 at 23:58
• @n0: He has a long history of quoting from problems and proofs without proper attribution, see meta.math.stackexchange.com/questions/645 He was asked to stop doing this. Alas, he seems to be back to his old ways. Sep 5, 2010 at 0:35
• @Chandru1: See the latest revision of my note in your post for yet another link. Alas, based on your prior history here of posting many problems and solutions without proper attribution it should come as no surprise to you that this raises doubts about your claim that you devised this solution - esp. when you're answering your own questions with answers easily available on the web. Sep 5, 2010 at 17:18
• @Bill Dubuque: Bill, i don't see any point in arguing or discussing things with you. I am honest with myself. Thats what i can tell. As far as i can say, i try my best to get a reference if its possible in net. I didn't get this time. So i did not post. If it still itches you, then i am sorry, the only thing would be tell a moderator to remove me from the site!
– anonymous
Sep 5, 2010 at 18:22
• @Chandru: As has been stressed to you on meta, proper attribution is important. I agree that this is not the place to discuss this so let's move to the prior meta thread to continue the discussion if you wish to do so. Sep 6, 2010 at 17:58

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.

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!

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.

• Typo: Your $b^n$ turned into $b$. Also, you can get from $b^n+n=k(a^n+n)$ to $b^n+n = 0 (\mod k)$ by simply reducing the first equation modulo $k$. Most importantly: Who says that the same $k$ works for all $n$? Finally, your counter-example isn't a counter-example: For a given $n$, there are probably plenty of distinct values for $a$ and $b$ with the stated divisibility property; a counter-example would involve distinct $a$ and $b$ with the divisibility property for all $n$, but $6$ and $13$ fail already with $n=2$.
– Blue
Sep 4, 2010 at 5:51
• Thanks for you comment. I also found that 4 and 2 fail with n=4. My proof has a gap as you said because no one says that the same k works for all n. Sep 4, 2010 at 6:05
• @Mohommad: It's the "for all $n$" thing that makes this a tricky problem, since so much about the problem changes from one $n$ to another. Likewise, a particular pair of values has to pass the divisibility tests for all $n$ before the values can be considered counter-examples.
– Blue
Sep 4, 2010 at 6:16
• I am sorry for this silly mistake, I didn't honor the order of the quantifiers in fact ! Sep 4, 2010 at 6:19