12
$\begingroup$

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?

  • 0
    What does ∣ mean here? I'm guessing it's representing divisibility? Might help to specify, not everyone might know what it means.2010-09-03
  • 0
    @Noldorin Divides I assume. @Chandru1 are there any constraints on the result of said division i.e. divides such that the result is in N?2010-09-03
  • 0
    @Ninefingers: No constraints!2010-09-03
  • 1
    @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.2010-09-03
  • 3
    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?2010-09-03
  • 0
    This is a lot trickier to prove than I originally thought. I believe it's actually true. Perhaps modular arithmetic can help?2010-09-03
  • 1
    Chandru1: I guess you mean by "No constraints!" in the comment to @Noldorin that $(a^n +n)c =b^n +n$ for som $c\in\mathbb{N}$. (We don't talk of $c\in \mathbb{R}$ I hope!)2010-09-03
  • 1
    @muad 5^n+n is never prime2010-09-03
  • 0
    I'm not entirely sure how helpful this may be, but have you tried to prove the contrapositive?2010-09-04
  • 2
    "5^n+n is never prime" ?????2010-09-04
  • 2
    @Jason: http://math.stackexchange.com/questions/4125/5nn-is-never-prime2010-09-06
  • 2
    My claim that 5^n+n is never prime is actually false as n=7954 is a counterexample2010-09-06

5 Answers 5

13

Hint$\;$ from my $ $ sci.math post $ $ 2006/4/4 $ $ here or here (see there for much motivation)

$$\rm\quad\begin{eqnarray} p-1 \!\!\! &&\mid\rm \color{#c00}{n-1} \\ \rm p\!\!\! &&\mid\rm \color{#0a0}{a+n} && \\ \end{eqnarray}\! \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 $$

  • 0
    @Bill: Thanks for the solution.+12010-09-05
  • 0
    @Bill: Didn't understand how $p-1 \mid n-1$2010-10-23
  • 0
    @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 http://groups.google.com/groups?selm=y8z64lu25dv.fsf%40nestle.csail.mit.edu2010-10-23
  • 0
    @Bill: the problem in the sci.math is it's not in latex and i finding it intricate to understand. Anyhow thanks2010-10-23
  • 0
    @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. http://groups.google.com/support/bin/answer.py?hl=en&answer=46239, or else choose "Show Original".2010-10-23
  • 0
    @Bill: I did manage to get a solution. But not quite sure whether its correct or not. Please check and tell me if i can improve upon it. Thanks2010-10-27
  • 0
    Could you please explain in some detail how could we choose $p>|b-a|$ and $n$ to satisfy $p-1|n-1 , p|a+n$ ?2015-01-23
  • 0
    @user123733 If the above links don't work, see [here](http://mathforum.org/kb/plaintext.jspa?messageID=4601987) or [here](https://groups.google.com/forum/#!original/sci.math/sE0EWdtMLLU/chfQc1UEKDQJ) for extended discussion, including explanation of the motivation behind the proof.2015-01-23
5

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.

  • 0
    @Chandru: Could you please tell me the source of this solution.2010-09-04
  • 0
    @Chandru: I ask because **precisely this solution was posted recently to another forum**. Do you claim that you devised this solution yourself?2010-09-04
  • 6
    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...2010-09-04
  • 5
    @n0: He has a long history of quoting from problems and proofs without proper attribution, see http://meta.math.stackexchange.com/questions/645 He was asked to stop doing this. Alas, he seems to be back to his old ways.2010-09-05
  • 0
    @Bill Dubuque: Hey Bill, if i knew the answer to that question then i would have posted it instantly. As, i still say that i am unaware of the source.2010-09-05
  • 0
    Did you come up with this solution by yourself? Or did you read it somewhere?2010-09-05
  • 0
    @ShreevatsaR: Yes! I did it myself!2010-09-05
  • 0
    @Bill: The same solution was posted not long ago in a couple other well-known forums! Could you site some of them!2010-09-05
  • 0
    Ok, good then. :P2010-09-05
  • 2
    @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.2010-09-05
  • 2
    @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!2010-09-05
  • 0
    @Chandru: Why not simply try to be more explicit about the source of your problems and solutions? You will earn more respect that way, both numerically and otherwise. Perhaps here you may have seen the solution a few years ago on a site and not recalled its source. If so simply say something to that effect. You should expect that there will be heightened awareness of such matters after your prior posting of well-known answers that seemed to imply that they were your creation (e.g. Zagier's one-sentence proof on primes that are sums of squares). Except for above you've been doing much better.2010-09-06
  • 0
    @Bill Dubuque: Oh! Bill, what should i do to convince you. As, i say and keep saying, there are somethings, for which i get a reference, and i make sure that i notify it. Sometimes, when i don't get its not possible for me to say the reference. This is what exactly happened in this case!2010-09-06
  • 0
    @Chandru: That would be much easier to believe were it not for the Zagier proof and a couple others - which surely you did not discover on your own. In any case, this post seems to be an exception so I'm willing to forget about it in light of the fact that is seems you are sincerely attempting to make improvements. If you need any advice on such matters please do feel free to ask for assistance on meta. Best of luck.2010-09-06
  • 2
    @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.2010-09-06
  • 1
    @Chandru: the value of sources (even if they are "from my friend/professor/book-i-read-three-years-ago") is that they help users understand (1) whether the problem statement is correct, (2) how difficult or advanced the problem might be, (3) are solutions available, and where can they be found. That is completely separate from matters of whether the problem is original, whether posted answers are a result of genius or of web-searching, or other more "meta" questions. *Whatever information is available* about sources is valuable to readers of the question, and should be provided.2010-09-07
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.

0

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!

-2

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.

  • 0
    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$.2010-09-04
  • 0
    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.2010-09-04
  • 1
    @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.2010-09-04
  • 0
    I am sorry for this silly mistake, I didn't honor the order of the quantifiers in fact !2010-09-04