第3题

求

m^2+n^2

的最大值，其中

m

和

n

是满足

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

且

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

的整数。

第 3/6 步：用欧几里得算法下降

通俗地说

正如欧几里得算法逐步把一对整数化简到它们的最大公约数，这一下降过程把任意解对化简到斐波那契数列的起点。

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

详细分析

反向运行第 2 步中的关系，从任意满足 $n>m>1$ 的解 $(m,n)$ 可得到更小的解 $(n-m,m)$ 。由于 $m,n$ 是正整数，此下降过程必然终止；直接检验可知它只能停在最小的解 $(1,1)$ 与 $(1,2)$ 处。