The International Mathematics Olympiad (IMO) was held in Australia in 1988. A total of 268 students participated in IMO 1988. There are 6 problems, each with a score of 7, with a total score of 42. The 6 problem were provided by participating countries and selected by Australia. Among them, the problem 6 became a legendary problem in history.
While Western Germany won IMO in 1982 and 1983, the winner in all subsequent years were Soviet Union or Romania or USA. Therefore, Germans designed a problem and submitted to Australia, hoping that their students can easily solve it and won the competition.
As quoted in the Wikipedia page on Vieta jumping, Arthur Engel wrote the following about the problem's difficulty:
Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.
It became a famous problem because Emanouil Atanassov from Bulgaria easily solved the problem by Vieta jumping in a short paragraph that can be easily understood by middle school students, and received a special prize (the other 10 kids used more standard or cumbersome approaches to solve it).
The IMO 1988 problem #6 is described as follows:
Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$. Show that $\frac{a^2+b^2}{ab+1}$ is the square of an integer.
This solution is copied from Wikipedia (except that I changed to Latex formatting):
Fix some value $k$ that is a non-square positive integer. Assume there exist positive integers $(a, b)$ for which $k = \frac{a^2 + b^2}{ab + 1}$.
Let $(A, B)$ be positive integers for which $k = \frac{A^2 + B^2}{AB + 1}$ and such that $A + B$ is minimized, and without loss of generality assume $A ≥ B$.
Fixing $B$, replace $A$ with the variable $x$ to yield $x^2 – (kB)x + (B^2 – k) = 0$. We know that one root of this equation is $x_1 = A$. By standard properties of quadratic equations, we know that the other root satisfies $x_2 = kB – A$ and $x_2 = \frac{B^2 – k}{A}$.
The first expression for $x_2$ shows that $x_2$ is an integer, while the second expression implies that $x_2 ≠ 0$ since $k$ is not a perfect square. From $\frac{x_2^2 + B^2}{x_2 B + 1} = k > 0$ it further follows that $x_2$ is a positive integer. Finally, $A ≥ B$ implies that $x_2 = \frac{B^2 − k}{A} < A$ and thus $x_2 + B < A + B$, which contradicts the minimality of $A + B$.
However, I doubt that this is the original answer, as it is overly complicated and confusing to describe to middle schoolers. A typical Chinese math teacher will likely criticize it as "farting after pulling down pants".
The Chinese way of using Vieta jumping to solve it can be described as follows:
Rewrite in standard quadratic equation on $b$: $b^2 - ka \times b + (a^2-k) =0$. Assume $k$ is not a square, and $(A, B_1)$ is the smallest integer solution where $A \leq B_1$. Then middle schoolers know there must exist $B_2$ such that $B_1+B_2=kA$ and $B_1*B_2=A^2-k$.
Because $0 < B_2 = (A^2-k)/B_1 < A^2/B_1 < A$ (note that it cannot be $B_2<0$ since $B_1+B_2=kA$, and it cannot be $B_2=0$ since $k$ is not a square), so $(B_2, A)$ is a smaller solution to the quadratic equation than $(A, B_1)$, which contradicts the assumption. So the problem is solved.
It is also interesting to simulate the solutions to the problem and validate whether the prediction is true. If it is true, whether there is special patterns of the solutions
# Solution by computer simulation
for i in range (1, 1000):
for j in range (i, 1000):
if (i*i+j*j) % (i*j+1) == 0:
print ("Found a pair i =", i, " j =", j, " result =", (i*i+j*j)/(i*j+1))
Found a pair i = 1 j = 1 result = 1.0 Found a pair i = 2 j = 8 result = 4.0 Found a pair i = 3 j = 27 result = 9.0 Found a pair i = 4 j = 64 result = 16.0 Found a pair i = 5 j = 125 result = 25.0 Found a pair i = 6 j = 216 result = 36.0 Found a pair i = 7 j = 343 result = 49.0 Found a pair i = 8 j = 30 result = 4.0 Found a pair i = 8 j = 512 result = 64.0 Found a pair i = 9 j = 729 result = 81.0 Found a pair i = 27 j = 240 result = 9.0 Found a pair i = 30 j = 112 result = 4.0 Found a pair i = 112 j = 418 result = 4.0
Several interesting observations can be made. There are a few classes of numerical solutions:
For all the types, we get $\frac{a^2 + b^2}{ab + 1} = n^2$. However, there may be also other numerical solutions beyond these 3 types as shown above. I do not know if there is a generalized numerical solution to this equation. My instinct is that all numerical solutions probably satisfy one of the the three forms, but I really do not know for sure. This is an interesting problem to solve further!!! I hope somebody is interested in finding all analytical solutions for the problem.
I found a Chinese video that teaches math to middle/high school students shows an extension of this particular problem beyond the square of $a$ and $b$:
Given positive integers $a, b, n (n \geq 2)$ such that $a^n+b^n$ divides $ab^{(n+1)}+1$, prove $\frac{a^n+b^n}{ab^{(n+1)}+1} = q^n$ while $q \in N$.
Obviously this is a generalization of the IMO 1988 problem 6 which is a special case of $n=2$.
In reviewing literature online, I discovered that Fermat actually used Vieta jumping to solve a special $n=4$ case for Fermat's conjecture, which states that no three positive integers $a$, $b$, and $c$ satisfy the equation $a^n + b^n = c^n$ for any integer value of $n$ greater than 2. However, this solution cannot be extended to other values of $n$.
Similarly, Euler has applied Vieta jumping to solve a conjecture from Fermat that any prime number that has a remainder of 1 after division by 4 can be expressed as the sum of two squares. That is, if a prime number x and an integer y satisfies $x=4y R 1$, then there exists two positive integer $a$ and $b$ that satisfies $x=a^2+b^2$. This conjecture was proposed by Fermat but he failed to give a solution.