Berkeley Math Circle: Monthly Contest 1

Solution:
The solutions are $(N, n)=\left(F_{i+1}, F_{i}\right)$.

If $N>n$, $N^{2}-n(N+n)=N(N-n)-n^{2}$, so $(N, n)$ works if and only if $(n, N-n)$ works.

If $N \leq n$, $n(N+n)-N^{2} \geq n^{2} \geq 1$, so the only solution is $(N, n)=(1,1)$.

Thus, all solutions eventually become $(1,1)$ after repeatedly applying the operation $(N, n) \mapsto(n, N-n)$, so reversing this process, every solution comes from repeatedly applying the operation $(N, n) \mapsto(N+n, N)$ to $(1,1)$.

This operation maps $\left(F_{i}, F_{i-1}\right)$ to $\left(F_{i+1}, F_{i}\right)$, and $(1,1)=\left(F_{2}, F_{1}\right)$, giving the desired via induction.