Vieta Jumping

Idea · Advanced

Number Theory

Vieta Jumping is a method used in number theory to study integer solutions of quadratic Diophantine equations.

The main idea is to treat an equation as a quadratic in one variable. If one root is an integer, Vieta's formulas often show that the other root is also an integer.

We then replace the original root with the other root to obtain a new integer solution. If this new solution is smaller, we can repeat the process to obtain an infinite descent, which is impossible for positive integers.

Find all positive integer solutions of

a^2+b^2+1=3ab.

Without loss of generality, assume $a\le b$ .

Case 1: $a=1$ .

1+b^2+1=3b

b^2-3b+2=0

(b-1)(b-2)=0

b=1\text{ or }2.

Case 2: $a>1$ .

If $a=b$ , then

2a^2+1=3a^2

1=a^2

a=1.\qquad\times

So $a<b$ .

(a,b)\longleftrightarrow(a,3a-b)

0<b'=3a-b=\frac{a^2+1}{b}\le\frac{a^2+1}{a+1}<a.

Thus we can descend to $(1,1)$ or $(1,2)$ , and reverse the jumps to generate all possible solutions.

(1,1)\longrightarrow(1,2)\longrightarrow\left(\underset{F_3}{2},\underset{F_5}{5}\right)\longrightarrow\left(\underset{F_5}{5},\underset{F_7}{13}\right)\longrightarrow\cdots

Let $F_1=F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ be the Fibonacci sequence. We want to prove that, starting from $(1,2)$ , all pairs are of the form

(F_{2n-1},F_{2n+1}).

Under a reverse jump, such a pair becomes

(F_{2n-1},F_{2n+1})\longrightarrow(3F_{2n-1}-F_{2n+1},F_{2n-1})

or, in the increasing direction,

(F_{2n-1},F_{2n+1})\longrightarrow(F_{2n+1},3F_{2n+1}-F_{2n-1}).

Using the Fibonacci recurrence,

3F_{2n-1}-F_{2n+1}=3F_{2n-1}-(F_{2n}+F_{2n-1})

=2F_{2n-1}-F_{2n}

=F_{2n-1}-(F_{2n}-F_{2n-1})

=F_{2n-1}-F_{2n-2}=F_{2n-3}.

Similarly,

3F_{2n+1}-F_{2n-1}=2F_{2n+1}+F_{2n+1}-F_{2n-1}

=2F_{2n+1}+(F_{2n}+F_{2n-1})-F_{2n-1}

=2F_{2n+1}+F_{2n}=F_{2n+1}+(F_{2n+1}+F_{2n})

=F_{2n+1}+F_{2n+2}=F_{2n+3}.

So the neighboring solutions are

(F_{2n-1},F_{2n+1})\longrightarrow(F_{2n-3},F_{2n-1})\quad\text{or}\quad(F_{2n+1},F_{2n+3})

Consequently, all positive integer solutions are

\boxed{(a,b)=(F_{2n-1},F_{2n+1})\text{ or }(F_{2n+1},F_{2n-1}),\quad n\ge1.}