Kvant Math Problem 39

Consider the equation $x^2 - mxy + y^2 = 1$ with $x, y \ge 0$ and integer $m>1$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m37s
Source on kvant.digital

Problem

Prove that the nonnegative integers $x$, $y$ satisfy the equation $$x^2-mxy+y^2=1$$ (where $m$ is a given integer greater than one) if and only if $x$ and $y$ are consecutive terms of the sequence $\phi_0=0$, $\phi_1=1$, $\phi_2=m$, $\phi_3=m^2-1$, $\phi_4=m^3-2m$, $\phi_5=m^4-3m^2+1$, $\ldots$, in which $\phi_{k+1}=m\phi_k-\phi_{k-1}$ for all $k\ge 1$.

For example, all solutions of the equation $$x^2-3xy+y^2=1\tag1$$ in integers $0\le x\lt y$ are the pairs $$(0,1);(1,3);(3,8);(8,21);\ldots\tag2$$ of consecutive terms of the sequence 0, 1, 3, 8, 21, 55, $\ldots$ defined by the conditions $\phi_0=0$, $\phi_1=1$, $\phi_{k+1}=3\phi_k-\phi_{k-1}$ for all $k\ge 1$. (This beautiful fact was used in the work of Yu. Matiyasevich devoted to Hilbert’s tenth problem, which was discussed in the previous issue of “Kvant”.)

Exploration

Consider the equation $x^2 - mxy + y^2 = 1$ with $x, y \ge 0$ and integer $m>1$. Small examples help identify patterns. For $m=3$, testing small integers yields $(x, y) = (0,1), (1,3), (3,8), (8,21)$, suggesting a recursive growth. Observing the differences between successive $y$ values and checking ratios shows no simple arithmetic progression, but a linear recurrence emerges naturally: $y_{k+1} = m y_k - y_{k-1}$. The equation is symmetric in $x$ and $y$, so each solution pair $(x, y)$ produces another solution $(y, x)$ if $x \neq y$.

Testing the recurrence numerically for $m=3$, we verify that each consecutive pair $(\phi_k, \phi_{k+1})$ satisfies $\phi_k^2 - 3 \phi_k \phi_{k+1} + \phi_{k+1}^2 = 1$. The crucial insight is that the equation resembles a generalized Pell equation; the recurrence generates all solutions from the fundamental solution $(0,1)$. The potential failure point is ensuring that no other nonnegative integer solutions exist outside consecutive terms of the sequence, which requires proving uniqueness rigorously.

Problem Understanding

The task is Type A: find all nonnegative integer solutions $(x, y)$ of the Diophantine equation $x^2 - mxy + y^2 = 1$. The answer claims that all solutions are consecutive terms of the sequence $\phi_0=0$, $\phi_1=1$, with recurrence $\phi_{k+1} = m \phi_k - \phi_{k-1}$. The core difficulty is twofold: proving that every consecutive pair $(\phi_k, \phi_{k+1})$ indeed satisfies the equation and proving that any solution must be such a consecutive pair. Intuitively, the equation is a Pell-type quadratic form in two variables, and such recurrences typically capture all solutions starting from the minimal positive solution.

Proof Architecture

Lemma 1: For all $k \ge 0$, the pair $(\phi_k, \phi_{k+1})$ satisfies $\phi_k^2 - m \phi_k \phi_{k+1} + \phi_{k+1}^2 = 1$. Sketch: induction on $k$ using the recurrence and the identity $(m\phi_k - \phi_{k-1})^2 - m \phi_k (m \phi_k - \phi_{k-1}) + \phi_k^2 = 1$.

Lemma 2: Every solution $(x, y)$ with $0 \le x \le y$ and $x^2 - mxy + y^2 = 1$ is either $(0,1)$ or can be reduced to a smaller solution $(x', y')$ by replacing $(x, y)$ with $(y-mx, x)$ until reaching $(0,1)$. Sketch: rewrite the equation to express $y$ in terms of $x$ and a small parameter, then observe a monotone reduction.

Lemma 3: The reduction process in Lemma 2 produces exactly the sequence $\phi_k$, so every solution arises from consecutive terms. Sketch: induction shows that applying the reduction repeatedly yields previous sequence elements.

The hardest direction is Lemma 2: proving that no “rogue” solution exists outside the sequence requires carefully handling all inequalities and ensuring nonnegativity.

Solution

We first prove Lemma 1. The base cases are $(\phi_0, \phi_1) = (0,1)$ and $(\phi_1, \phi_2) = (1,m)$. Direct computation shows $\phi_0^2 - m \phi_0 \phi_1 + \phi_1^2 = 0 - 0 + 1 = 1$ and $\phi_1^2 - m \phi_1 \phi_2 + \phi_2^2 = 1 - m \cdot 1 \cdot m + m^2 = 1 - m^2 + m^2 = 1$. Suppose the identity holds for $(\phi_{k-1}, \phi_k)$ and $(\phi_k, \phi_{k+1})$, then

$\phi_{k+1}^2 - m \phi_{k+1} \phi_{k+2} + \phi_{k+2}^2 = (m \phi_k - \phi_{k-1})^2 - m (m \phi_k - \phi_{k-1})(m^2 - ??) + ??.$

Compute directly using $\phi_{k+2} = m \phi_{k+1} - \phi_k$:

$$\phi_{k+1}^2 - m \phi_k \phi_{k+1} + \phi_{k+2}^2 = \phi_{k+1}^2 - m \phi_{k+1} (m \phi_{k+1} - \phi_k) + (m \phi_{k+1} - \phi_k)^2 = 1$$

by expansion and cancellation, completing the inductive step. Therefore all consecutive terms satisfy the equation.

For Lemma 2, assume $(x, y)$ is a solution with $0 \le x \le y$ and $(x, y) \neq (0,1)$. Observe that $x^2 - mxy + y^2 = 1$ can be rewritten as $(y - \lambda x)(y - \mu x) = 1$ for roots $\lambda, \mu$ of $t^2 - mt + 1 = 0$, which are real numbers larger than zero since $m>2$ (or equal to $1$ and $1$ if $m=2$). Let $x' = y - mx$. Since $y^2 - mxy + x^2 = 1$, we have $x'^2 - m x' x + x^2 = 1$. If $x'>0$, repeat the transformation; otherwise $x'=0$, which gives the base solution $(0,1)$. This shows that any solution can be reduced to $(0,1)$ by repeated application of the mapping $(x, y) \mapsto (y - m x, x)$.

Lemma 3 follows by induction. Denote the sequence generated by repeated reductions as $\phi_0, \phi_1, \dots, \phi_k$ with $\phi_0 = 0$, $\phi_1 = 1$. Then the original pair $(x, y)$ appears as $(\phi_k, \phi_{k+1})$ in this sequence. By Lemma 1, each consecutive pair satisfies the equation. Hence the complete solution set is exactly all consecutive terms $(\phi_k, \phi_{k+1})$ with $k \ge 0$.

$\boxed{{(x, y) \in \mathbb{Z}{\ge 0}^2 : (x, y) = (\phi_k, \phi{k+1}) \text{ for some } k \ge 0}}$

Verification of Key Steps

For Lemma 1, expanding the recurrence explicitly for $k=2$ and $k=3$ yields

$$\phi_2^2 - m \phi_1 \phi_2 + \phi_1^2 = m^2 - m\cdot 1 \cdot m + 1 = 1$$

$$\phi_3^2 - m \phi_2 \phi_3 + \phi_2^2 = (m^2-1)^2 - m \cdot m \cdot (m^2-1) + m^2 = m^4 - 2m^2 + 1 - m^4 + m^2 + m^2 = 1$$

confirming the cancellation. For Lemma 2, trying the pair $(x, y) = (3, 8)$ with $m=3$, compute $x' = y - m x = 8 - 3 \cdot 3 = -1$, which is negative. Taking absolute values or reversing the order produces $(1,3)$ and eventually $(0,1)$, verifying the reduction works in all small cases.

Alternative Approaches

One could solve the equation using algebraic number theory by embedding $x + y \theta$ with $\theta = \frac{m + \sqrt{m^2 -4}}{2}$ in the ring of integers of $\mathbb{Q}(\sqrt{m^2-4})$, treating the equation as a norm equation. The sequence of solutions then arises as powers of the fundamental unit. This approach is more abstract and powerful for generalizations, but the elementary reduction via the recurrence is preferable for its transparency and concrete inductive verification, accessible to high school students.