Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a,b$ be positive integers.

When $$k = \frac{a^2 + b^2}{ab+1}$$ is an integer, it is a square.


Proof 1: (Ngô Bảo Châu): Rearrange to get $a^2-akb+b^2-k=0$, as a quadratic in $a$ this has two values: $a$ and $kb - a = (b^2-k)/a$. (The second root is determined in two different ways from the expansion $(x-r_1)(x-r_2) = x^2 - (r_1 + r_2)x + r_1 r_2$.)

Now suppose we have $a,b$ such that $k$ is an integer but not a square, by the investigation about roots we have that the second root is a nonzero integer since $k,b,a$ are integers and $k \not = b^2$, futhermore it is positive which is easily seen from its defining equation.

WLOG assume $a \ge b$ so that the second root is strictly smaller than $a$. This leads to a decent, replacing $a$ with the second root.


Proof 2 (Don Zagier): Apply reduction theory (specifically, Sätze 1 and 2 of Section 13 of my book on quadratic fields) to the quadratic form $x^2 + kxy + y^2$, which is the unique reduced quadratic form in its equivalence class.


Note that Proof 2 is pretty much the same as Proof 1 when written out in explicit detail, but I could not read Zagier's book because I cannot read German.

I would like to know more approaches to this and other alternative proofs of this result if possible! Thanks in advance.

I would also be interested in related problems (especially easier ones of a similar nature) and texts which cover the reduction theory in English.

share|improve this question
1  
You may see this link: artofproblemsolving.com/Forum/… –  anonymous Mar 22 '11 at 6:01

3 Answers 3

This is, IMHO, one of the most popular (and actually the most beautiful) problems in number theory. It is IMO 1988 Problem 6.

You can find it in these links (most of the solutions are the same as the two you remarked, but you may find some more facts about these problems if you see below):

http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=57282 (master link)

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=192471

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=195433

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=297533

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=271870

This is a cool generalization of this problem (you may see this, too):

Problem. Let $a,b$ be positive integers satisfying $$(ab)^{n-1}+1 \mid a^n +b^n.$$ Then the number $\frac{a^n +b^n}{(ab)^{n-1}+1}$ is a perfect $n^{th}$ power.

Here are some nice problems related to this one:

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=119551

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=345094

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=375674

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=26374

And, for the sake of completeness about this problem, see Vieta Jumping Method. (IMO 1988 is the best example for Vieta Jumping!)

share|improve this answer
19  
"This is, IMHO ... the most beautiful problems in number theory." You haven't seen that much number theory then? –  Eric Naslund May 11 '11 at 20:37
3  
@Eric: I think the answer means within the sphere of olympiad / contest-math problems. –  ShreevatsaR Jun 12 '13 at 11:49
2  
@EricNaslund Your statement is both false and offensive. I know Amir and he is literally a genius and has written several olympiad-level Number Theory articles and problems, so please think before you talk. –  Ahaan Rungta Dec 7 '13 at 22:34

Let us prove the general case: if $a, b, n\in \mathbb{N}$ and $$c:=\frac{a^n+b^n}{(ab)^{n-1}+1}$$ then $c\in\mathbb{N}$ is an $n$th power.

Proof: In order to show, it is clear that we need to express $c$ as $c=t^n$ for some $t\in\mathbb{N}$, isn't it?

So let us consider $a=t^{\alpha}, b=t^{\beta}$. Why? Because unless $a, b$ themselves are power some other $t\in\mathbb{N}$, then statement will not be true in general. This is a crucial observation. We are given that $a, b$ are integers (WOLOG we have chosen as positive integers) and hence if $c$ is supposed to be as $t^n$ then $a, b$ have to be some power of $t$; Otherwise, contradiction will arrive.

So we have $$c=\frac{a^n+b^n}{(ab)^{n-1}+1}$$ $$i.e. c =\frac{(t^\alpha)^n+(t^\beta)^n}{(t^{\alpha+\beta})^{n-1}-1}$$ $$i.e. c =\frac{t^{n\beta}(t^{n\alpha-n\beta})+1}{t^{(\alpha+\beta)(n-1)}+1} $$

Intuition says that we can choose $\beta=1$. But that would be particular stage. So let $\beta=\beta_0$. Now in order to make $c$ as integer, we must have $$t^{(\alpha+\beta)(n-1)}+1 \mid t^{n\alpha-n\beta}+1$$ which is true iff $$(\alpha+\beta_0)(n-1)\mid (n\alpha-n\beta)$$ $$\text{iff}\; (\alpha+\beta_0)(n-1)s=n\alpha-n\beta \; \text{for some}\; s\in\mathbb{N}$$ $$\text{so}\; \alpha=\frac{-\beta_0(2n-1)}{(n-1)s-n}$$

We choose $s$ in such a way that $\alpha$ is in $\mathbb{N}$. For the sake of simplicity we take $s=-1$ then $\alpha=\beta_0(2n-1)$. Thus we have $a=t^{\alpha}=t^{\beta_0 (2n-1)}, b=t^{\beta_0}, \beta_0 \in\mathbb{N}.$ And consequently $c=t^{n\beta_0}$. Since $c$ should be $n$th power, so it follows that $\beta_0=1$ and hence $\alpha=2n-1$ so that $c=t^n$. We are done.

share|improve this answer

Given: $1+ab$ divides $a^2+b^2$.
By long division,we get,
Quotient=$a/b$
Remainder=$b^2-a/b$
Since $1+ab$ divides $a^2+b^2$,
Remainder=$0$
or $a=b^3$
Substituting $a=b^3$ in the expression of quotient, we get
Quotient=$b^2$
Therefore I have proved that quotient is a perfect square, that too without using vieta jumping.

share|improve this answer
1  
-1 It is true that $$a^2+b^2={{a}\over{b}}\,\left(a\,b+1\right)+\left(b^2-{{a}\over{b}}\right)$$ but one cannot conclude that the remainder $b^2-a/b=0$ if one divides $a^2+b^2$ by an arbitrary number. –  miracle173 Feb 2 at 17:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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