Решение 1:   Пусть наибольший общий делитель чисел $a$ и $b$ равен $d, a = ud, b = vd$.  По условию  $d(u^{n+1} + v^{n+1})$  делится на  $u^n + v^n$  для бесконечного множества натуральных $n$. Поскольку $u$ и $v$ взаимно просты, числа  $u^{n+1} + v^{n+1}$  и  $u^n + v^n$  взаимно просты с $u$ и $v$, а кроме того, могут иметь общим множителем максимум $|v-u|$ (это следует из того, что  $u^{n+1} + v^{n+1} - u(u^n + v^n) = v^n(v - u))$.

  Но ненулевое число, не превосходящее  $d|v - u|$,  не может делиться на  $u^n + v^n$  для бесконечно многих $n$. Значит,  $u = v$,  откуда  $a = b$.

Решение 2:  Пусть, например,  $a > b$.  Дробь $\dfrac{a^{n+1}+b^{n+1}}{a^n+b^n}$ меньше $a$, но стремится к $a$ при  $n\to\infty.$  Значит,  $a - 1 < \frac{a^{n+1} + b^{n+1}}{a^n+b^n} < a$  при достаточно больших $n$. Противоречие.

Решение 3:Пусть, например,  $a > b$.  Тогда  $b < \dfrac{a^{n+1}+b^{n+1}}{a^n+b^n} < a$  при всех натуральных $n$. Так как между $b$ и $a$ конечное число целых чисел, найдутся такие различные натуральные $m$ и $k$, что  $\dfrac{a^{m+1}+b^{m+1}}{a^m+b^m} =\dfrac{a^{k+1}+b^{k+1}}{a^k+b^k}$.  Умножив на знаменатели и приводя подобные, получим  $a^mb^k(a - b) = a^kb^m(a - b)$,  или  $\left(\frac{a}{b}\right)^{m-k} = 1$,  откуда  $m = k$.  Противоречие.

Обязательно.