Alternative proof that $(a^2+b^2)/(ab+1)$ is a square when it's an integer

Question

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.

Answer 1

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):

1st (master link)

2nd

3rd

4th

5th

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:

1st

2nd

3rd

4th

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

Answer 2

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}$. 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} $$

So let $\beta=\beta_0$. Now in order to make $c$ as integer, we must have $$t^{(\alpha+\beta_0)(n-1)}+1 \mid t^{n\alpha-n\beta_0}+1$$ which is true iff $$(\alpha+\beta_0)(n-1)\mid (n\alpha-n\beta_0)$$ $$\text{iff}\; (\alpha+\beta_0)(n-1)s=n\alpha-n\beta_0 \; \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}=(t^{\beta_0})^n$. We are done.

Answer 3

Let $$a^2+b^2=q(ab+1).\tag1$$

It is given that $q$ is a positive integer. $a$ and $b$ are integers, but, for the moment, do not restrict them to be positive.

Denote the solution $a=a_0, b=b_0$ by $(a_0, b_0)$.[1] Then, by symmetry, $(a_0, b_0)$ is a solution iff $(b_0, a_0)$ is.

If $(a_0, a_0)$ is a solution, $2a_0^2=q(a_0^2+1)$, so $q<2$, so $q=1$, so $a_0^2=1$, so $a_0=\pm 1$, so $a_0=1$ (as $a, b>0$). In the rest of this discussion, let $a\ne b$.

Now fix $q>1$. Then equation 1 can be cast as a quadratic in $a$: \begin{align} a^2+b^2 &= q(ab+1)\\ \implies a^2-qab+b^2-q &= 0\tag2 \end{align}

Further, fix $b=s(1)$. Then the quadratic equation 2 has two solutions $a=s(0)$, $a=s(2)$ where \begin{align} s(0)+s(2) &= qs(1)\tag3\\ s(0)s(2) &= s(1)^2-q\tag4 \end{align} As $q\geqslant 2$, equation 3 implies that one of $s(0)$ and $s(2)$ is greater than $s(1)$; wlog $s(0)>s(1)$. Equation 4 implies \begin{align*} s(1)s(2) &< s(0)s(2)=s(1)^2-q<s(1)^2\\ \implies s(2) &< s(1) \end{align*}

That is, if the value of one of the variables $a$ and $b$ is fixed at an integer $s(1)$, the other variable may take on either of two values, one greater and one less than $s(1)$.[2] The values fixed for $q$ and $s(1)$ determine a descending sequence $s(0), s(1), s(2),\dots$ where $(s(i), s(i+1))$ and $(s(i+1), s(i))$ are solutions.

If for some $i$, $s(i)=0$, then, in the solution $(s(i-1), s(i))$, $q=a^2=s(i-1)^2$ and so $q$ is a square.

Otherwise, there must be some $i$ where $s(i-1)>0>s(i)$. Thus, in the solution $(s(i-1), s(i))$, $a>0>b$, so $0<a^2+b^2=q(ab+1)$ and $q>0$, so $ab+1>0$, which is impossible.

This proof is based on the proof here, with symbols for the variables changed from $x$ and $y$ to $a$ and $b$ to suit the OP.

[1] One problem with some people's attempts to explain is that they fail to distinguish between the variables ($a$ and $b$ here) and quantities which might be values of those variables.

[2] One deficiency in some proofs is that they fix the value of, say, $b$, and argue from symmetry that of the two possible values of $a$, one is greater and one is less than $b$. This is invalid. Suppose the solutions to a set of equations were that $a$ and $b$ are, in either order, $k^2$ and $k^2-1$. Then we may validly note symmetry and then say "wlog $a>b$". However, if you fix $b=9$ and then say $a>b$ you won't locate the solution $(8, 9)$.

Answer 4

I tried to formulate an accessible one for anyone who has minimal confidence with the equations of the second degree. Let's put the above problem in a different but equivalent way:

think of $ n_ {i} $ and $ n_ {i + 1} $ not as positive integers but as solutions of the following equation:

$$ \frac{n_{i}^2+n_{i+1}^2}{1+n_{i} n_{i+1}}=s \tag{2}$$

Show that $ n_ {i} $ and $ n_ {i+ 1} $ can be integers only if $ s $ is a perfect square.

Let $ n_ {i} $ be a known solution, let's look for the other solution $ x $ through the famous solution formula of the second degree equations: $$ a x^{2}+b x+c=0 \\ x_{1,2}=\frac{-b \pm \sqrt{b^2 - 4 ac}}{2a} $$

So

$$ \frac{n_{i}^2+x^2}{1+n_{i} x}=s \tag{3}$$

$ \ $

$$n_{i}^2+x^2=s(1+n_{i} x) \\ x^2 + (-s n_{i})x+(n_{i}^2-s)=0 \\ x_{1,2}=\frac{1}{2}\bigg(n_{i} s\pm \sqrt{n_{i}^2 s^2+4(s-n_{i}^2)}\bigg) $$

if $(n_{i}s) \neq 0$

$$x_{1,2}=\frac{n_{i} s}{2}\bigg(1\pm \sqrt{1+4 \bigg( \frac{s-n_{i}^2}{n_{i}^2 s^2} \bigg)} \bigg) \tag{4} $$

Note that the element under the square root looks a lot like the square of a binomial:

$$ 1+4 \bigg( \frac{s-n_{i}^2}{n_{i}^2 s^2}\bigg)=\bigg(1-2 \frac{ q}{n_{i} s} \bigg)^2=1+4 \frac{q^2}{n_{i}^2 s^2}-4\frac{q}{n_{i} s} \tag{5} $$

So we can rewrite $(4)$ as:

$$ x_{1} =\frac{n_{i} s}{2} \Bigg(1 - \bigg(1-\frac{2 q}{n_{i} s} \bigg) \Bigg)=q \\ x_{2} =\frac{n_{i} s}{2} \Bigg(1 + \bigg(1-\frac{2 q}{n_{i} s} \bigg) \Bigg)= n_{i} s -q $$

We have the beautiful result that $ q = x_ {1} $ this allows us in one fell swoop to: determine the value of $ q $, and make sure that the two solutions of $(3)$ are linked by the following relation:

$$ x_{2}=n_{i} s -x_{1} \tag{6} $$

But what is $ n_ {i} $? $ n_ {i} $ is also a solution! so if we know two solutions $ n_ {i} $ and $ x_ {1} $ we can automatically get a third one!

This is so amazing because we now have a formula to generate all the solutions $n_{i}$ for $ (2) $ (when $n_{i} s \neq 0$) as long as we know at least two of them.

Since the equation $(2)$ is symmetric for $n_{i}$ and $n_{i+1}$, the procedure done in $ (3) $ to get $ x $ can be used equivalently to get $ n_ {i} $ and vice versa, we can write $ (6) $ as: $$ n_{i+1}=n_{i} s -n_{i-1} \tag{7} $$

Now we will use the case $ n_ {i} s = 0 $ to get the first two solutions:

$$n_ {i} s=0\begin{cases} \text{if $n_{i}=0, n_{i} \neq s \tag{a}$} \\ \text{if $s=0, n_{i} \neq s \tag{b}$} \\ \text{if $s=0=n_{i} \tag{c} $ } \end{cases} $$

We have that $(c)$ implies $n_{i}=n_{i+1}=0$ is a solution, and the case $ (b) $ can never be verified:

$$ \frac{n_{i}^2+n_{i+1}^2}{1+n_{i} n_{i+1}}=0 \Leftarrow\Rightarrow n_{i}=n_{i+1}=0 $$

Since if we use $ n_ {i} = n_ {i + 1} = 0 $ in $ (7) $ we don't get new solutions, so we use the case $ (a) $ to get a solution $ n_ {i + 1} \neq n_ {i} $:

$$ \frac{0^2+n_{i+1}^2}{1+0 n_{i+1}} =n_{i+1}^2=s \Leftarrow\Rightarrow n_{i+1}=\sqrt{s} $$

The solutions $ n_ {i} $ must be positive so the solution $ n_ {i} = 0 $ will surely be the smallest that can be found therefore we call it $ n_ {0} = 0 $ we will then have $ n_ {1 } = \sqrt {s} $. We have found two solutions, which if compared with all the others, with the same $ s $ take smaller values:

$$ \forall i , s>1 : 0=n_{0}< \sqrt{s}=n_{1}<n_{i}. $$

Known the first two solutions we can find the third and so on:

$$n_{0}=(0 )\sqrt{s} \\ n_{1}=(1) \sqrt{s} \\ n_{2}=s n_{1}-n_{0}=(s) \sqrt{s}\\ n_{3}=(s^{5}-1)\sqrt{s} \\ \vdots$$

Looking at the equation $ (7) $ we notice that if $ (s) $ is integer and $ n_ {i} $ and $ n_ {i-1} $ can be written as $ \alpha, \beta, \gamma \in \mathbb{Z}$: $$ n_ {i-1} = \alpha \sqrt {s}, \ \ n_ {i} = \beta \ \sqrt {s}$$

Then we have that all solutions can be written as:

$$n_ {i + 1} = s \beta \sqrt {s} - \alpha \sqrt {s} = (\beta s - \alpha) \sqrt {s} = \gamma \sqrt {s} $$

And this is our case! so we have that $n_ {i}$ can be integer if and only if $ s $ is the square of an integer!

$$ \square $$

Equation $(7)$ has the following solution:

$$ n_{i}=\frac{\sqrt{s}\bigg( \big(s+\sqrt{s^2-4}\big)^i - \big(s-\sqrt{s^2-4}\big)^i \bigg)}{2^{i} \sqrt{s^2-4}} $$

which for $ i> 1 $ has the following series representation: $$ n_{i}=\sum_{k=0}^{\frac{1}{4}(2i+i-(-1)^i)} (-1)^k \binom{i-k-1}{k} s^{\frac{1}{2} (2i-1-4k)} $$