I noticed this problem in a YouTube video and I thought I'd test out Gemini's ability to solve it. I posed this question:
This is a famous problem from the 1988 International Mathematical Olympiad (IMO), often referred to as the "Vieta Jumping" problem. It is considered one of the most beautiful problems in Olympiad history.
Here is the proof using the method of Infinite Descent (specifically, Vieta Jumping).
1. Setup the Equation
Let the given expression equal an integer $m$. We are given that $a$ and $b$ are positive integers and:
$$\frac{a^2 + b^2}{ab + 1} = m$$
We can rewrite this equation as:
$$a^2 - m(ab) - m + b^2 = 0$$
$$a^2 - m(ab) + b^2 - m = 0$$
We want to prove that $m$ is a perfect square.
2. Assumption for Contradiction
Assume, for the sake of contradiction, that $m$ is not a perfect square.
Let $S$ be the set of all pairs of positive integers $(a, b)$ that satisfy the equation for this specific non-square $m$:
$$S = \{ (a, b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \mid \frac{a^2 + b^2}{ab + 1} = m \}$$
Since we assumed solutions exist (the problem states $a, b$ are positive integers), the set $S$ is not empty.
3. Infinite Descent (Minimality)
Among all pairs in $S$, let us choose the pair $(A, B)$ that minimizes the sum $A + B$. Without loss of generality, assume $A \ge B$.
Since $(A, B)$ is a solution, it satisfies the quadratic equation in terms of $A$:
$$A^2 - (mB)A + (B^2 - m) = 0$$
Let’s treat this as a quadratic equation in $x$:
$$x^2 - (mB)x + (B^2 - m) = 0$$
We know one root is $x_1 = A$. By Vieta's formulas, since it is a quadratic, there must be a second root, $x_2$. The properties of the roots are:
Sum of roots: $x_1 + x_2 = mB \implies x_2 = mB - A$
Product of roots: $x_1 x_2 = B^2 - m \implies x_2 = \dfrac{B^2 - m}{A}$
4. Analyzing the Second Root ($x_2$)
We need to determine the nature of $x_2$.
Is $x_2$ an integer?
Yes. From the sum of roots ($x_2 = mB - A$), since $m, B, A$ are integers, $x_2$ is an integer.
Is $x_2$ equal to zero?
If $x_2 = 0$, then the product of roots $x_1 x_2 = 0$.
This implies $B^2 - m = 0$, or $m = B^2$.
This would mean $m$ is a perfect square. However, we assumed at the start that $m$ is not a perfect square. Therefore, $x_2 \neq 0$.
Is $x_2$ negative?
Consider the quadratic equation: $x^2 - mBx + B^2 - m = 0$.
If $x_2 < 0$, let's check the value of the expression for negative $x$.
$$x_2^2 - mB(x_2) + B^2 - m$$
Since $x_2$ is a negative integer (e.g., $-1, -2...$) and $m, B \ge 1$:
$x_2^2 > 0$
$-mBx_2 > 0$ (negative times negative is positive)
$B^2 - m$?
Actually, we can check this simpler: From the product of roots, $x_1 x_2 = B^2 - m$.
Since $x_1 = A > 0$, if $x_2 < 0$, then $B^2 - m < 0$, so $m > B^2$.
However, looking at the sum of roots: $x_2 = mB - A$.
If $x_2 < 0$, then $mB < A$. Thus $A > mB > B^2 \cdot B = B^3$.
However, checking the value of the polynomial $f(x) = x^2 - mBx + B^2 - m$:
If $x_2 \le -1$, then $f(x_2) \ge 1 + mB + B^2 - m = 1 + B^2 + m(B-1)$.
Since $B \ge 1$ and $m \ge 1$, $f(x_2) \ge 1 + 1 + 0 > 0$.
This contradicts $f(x_2) = 0$. Therefore, $x_2$ cannot be negative.
Conclusion: $x_2$ must be a positive integer.
5. Contradiction
Since $x_2$ is a positive integer, the pair $(x_2, B)$ is also a solution in the set $S$ (because the equation is symmetric with respect to $a$ and $b$, and substituting $x_2$ into the quadratic yields 0).
Now, let's look at the size of $x_2$. From the product of roots:
$$x_2 = \frac{B^2 - m}{A}$$
Since $m$ is a positive integer (and we assumed not a square, so usually $m > 1$ unless trivial), we have $B^2 - m < B^2$.
Therefore:
Recall we assumed $A \ge B$. Thus:
$$x_2 < \frac{B^2}{B} = B \le A$$
So, $x_2 < A$.
This creates a new solution $(x_2, B)$ where the sum of the components is $x_2 + B$.
Since $x_2 < A$, it follows that:
This contradicts our initial statement that $(A, B)$ was the solution with the minimal sum.
6. Final Result
The only way to avoid this contradiction is if the case "$x_2$ is a positive integer" never happens.
As shown in step 4, the only alternative is $x_2 = 0$.
If $x_2 = 0$, then $m = B^2$.
Therefore, $m$ must be a perfect square.
I then asked: Where does the terms "Vieta" and "Vieta Jumping" come from?
The terms come from two distinct places: a 16th-century French mathematician and a legendary problem from the 1988 International Mathematical Olympiad.
1. "Vieta" comes from François Viète
The term "Vieta" refers to François Viète (1540–1603), often known by his Latinized name Franciscus Vieta.
Who he was: A French mathematician who is arguably the "father of modern algebra." He was the first to systematically use letters to represent numerical unknowns (like $x$ and $y$) and parameters (like $a$ and $b$) in equations.
The Connection: He is most famous for Vieta's Formulas, which connect the roots of a polynomial to its coefficients.
For a quadratic $ax^2 + bx + c = 0$ with roots $r_1$ and $r_2$, the formulas are:
$$r_1 + r_2 = -\frac{b}{a}$$
$$r_1 \cdot r_2 = \frac{c}{a}$$
This specific relationship (sum and product of roots) is the mechanical "engine" that makes the Vieta Jumping proof work.
2. "Vieta Jumping" comes from IMO 1988
The term "Vieta Jumping" (also called Root Flipping) is a relatively modern colloquialism invented by the math competition community. It was coined to describe the specific technique used to solve Problem 6 of the 1988 International Mathematical Olympiad (IMO).
The Legend of Problem 6
The problem you just saw ($ab+1 \mid a^2+b^2$) is legendary in the history of mathematics competitions.
The Difficulty: When the problem was submitted to the IMO jury in 1988 (held in Australia), the problem selection committee—which included famous number theorists—could not solve it within the allotted 6 hours. They actually considered rejecting it because they thought it was too hard for high school students.
The Surprise: Despite the judges' struggle, 11 students found the correct solution during the actual competition.
The Technique: The students solved it using the method of Infinite Descent combined with Vieta's Formulas.
They viewed the expression as a quadratic equation.
They used Vieta's formulas to "swap" (or jump) one root for another smaller root
($x_2 = mB - A$).
This "jump" creates a smaller integer solution, eventually leading to a contradiction.
Because this specific "root swapping" move was the key to cracking the hardest problem in IMO history, the community began calling the technique "Vieta Jumping."
Summary Table
| Term | Origin |
| Vieta | Latin name of François Viète (1540–1603), the creator of the root formulas. |
| Vieta Jumping | A nickname given to the descent method popularized by the solution to IMO 1988 Problem 6. |
Would you like me to show you another famous problem that can be solved using this technique?
The Vieta Jumping Trick That Solves an Impossible Olympiad Problem
This video provides a visual walkthrough of the exact technique discussed, breaking down the 1988 IMO problem step-by-step.
