учебное-задание - Докажите, что для любого целого $%n≥0$% числа $%F_n$% и $%F_{n+1}$% взаимно просты

Можно также индукцией:

Если $%(F_n,F_{n+1})=1$%, то $%(F_{n+1},F_{n+2})=(F_{n+1},F_n+F_{n+1})=(F_n,F_{n+1})=1,$%

поскольку $%(a,a+b)=(a,b)$%.

@EdwardTurJ, проверяющий сказал, что доказательство неполное. Вы показали, что если предположить взаимную простоту двух соседних чисел Фибоначчи, то из этого будет следовать, что и все последующие пары соседних чисел Фибоначчи будут взаимно просты. А вдруг такой пары взаимно простых чисел не существует? Или вдруг такая пара существует, но для очень очень большого значения n и для всех меньших значений индекса соседние пары не взаимно просты?

@a2g: если применить алгоритм Евклида к соседним числам, то большее из них будет заменяться на разность большего и меньшего. Тогда от $%F_{n+2},F_{n+1}$% мы за один шаг придём к $%F_{n+1},F_n$%, и так несколько раз. В итоге придём к $%F_2,F_1$%, а про них мы знаем, что НОД равен 1.