Problem 3

Determine the maximum value of

m^2+n^2

, where

m

and

n

are integers satisfying

m, n \in \{1, 2, \ldots, 1981\}

and

(n^2-mn-m^2)^2 = 1

Step 3 of 6: Descend by the Euclidean algorithm

Previous step Next step

In plain words

Just as the Euclidean algorithm reduces a pair of integers step by step to their gcd, this descent reduces any solution pair down to the base of the Fibonacci sequence.

(m,n) \mapsto (n-m, m) \text{ reverses the recurrence}

Detailed analysis

Running Step 2's relation backwards, from any solution $(m,n)$ with $n>m>1$ we obtain a smaller solution $(n-m,m)$ . Since $m,n$ are positive integers, this descent must terminate; it can only stop at the smallest solutions, which by direct check are $(1,1)$ and $(1,2)$ .