# 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?

-
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 '10 at 20:56
@BlueRaja - Danny Pflughoeft, this may not be a good comment. –  anon Sep 3 '10 at 22:22
"5^n+n is never prime" ????? –  Jason S Sep 4 '10 at 2:29
–  Aryabhata Sep 6 '10 at 6:56
My claim that 5^n+n is never prime is actually false as n=7954 is a counterexample –  yjj Sep 6 '10 at 10:21

PROOF$\;$ from my sci.math post of April 4, 2006

$\rm\quad\begin{array}{} p-1\:|\:n-1 \\ \quad\quad\;\rm p\:|\:a+n \\ \end{array} \;\; \Rightarrow\;\; p\;\;|\;\;a^n-a\;+\;a+n\;\;|\;\;b^n-b\;+\;b-a\;+\;a+n \;\;\Rightarrow\;\; p\:|\:b-a$

-
@Bill: Thanks for the solution.+1 –  anonymous Sep 5 '10 at 2:36
@Bill: Didn't understand how $p-1 \mid n-1$ –  anonymous Oct 23 '10 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/… –  Bill Dubuque Oct 23 '10 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 '10 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". –  Bill Dubuque Oct 23 '10 at 17:32
show 1 more comment

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... –  n0vakovic Sep 4 '10 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. –  Bill Dubuque Sep 5 '10 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. –  Bill Dubuque Sep 5 '10 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 '10 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. –  Bill Dubuque Sep 6 '10 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.

-
+1: This is eerie! I had exactly the same thoughts! –  Aryabhata Sep 4 '10 at 18:36

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 '10 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. –  M. Alaggan Sep 4 '10 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 '10 at 6:16
@All: Let's not downvote for this answer. Its good that Mohammed has tried his level best! Mistakes are created by everyone! –  anonymous Sep 4 '10 at 15:49
@Chandru1: I think downvotes for "wrong" answers are neccesary. Otherwise somebody who looks for a answer to this question might believe it was correct. –  Jens Sep 5 '10 at 19:31