Соседние числа Фибоначчи взаимно просты

[RFZ]

Здравствуйте. Помогите пожалуйста решить такую задачку:
Пусть $\{F_n\}$ - последовательность Фибоначчи.
Нужно доказать, что $(F_n, F_{n+1})=1$.
Не знаю с чего начать

[Whitaker]

Честно говоря, задачка самая простейшая
Докажите от противного

[RFZ]

Пусть $(F_n, F_{n+1})=d>1$
Дальше не знаю что

[Whitaker]

Вспоминайте алгоритм Евклида нахождения НОД двух чисел.

[RFZ]

Получается, что $F_{n}$ и $F_{n+1}$ делятся на $d>1$

[Whitaker]

Скажите-ка, как определяется последовательность Фибоначчи?

[RFZ]

$F_N=F_{N-1}+F_{N-2}$, где $N>2$, $F_{1}=F_{2}=1$

[Whitaker]

RFZ в сообщении #522553 писал(а):

Получается, что $F_{n}$ и $F_{n+1}$ делятся на $d>1$

Теперь рассмотрите разность $F_n$ и $F_{n+1}$

[RFZ]

$F_n$ и $F_{n+1}$ делятся на $d$.
Следовательно, $F_{n+1}-F_n$ делится на $d$, т.е. $F_{n-1}$ делится на $d$.
Я правильно делаю?

[Whitaker]

Пока, что ДА
Теперь рассмотрите разность $F_{n}$ и $F_{n-1}$. Короче продолжайте процесс.

[RFZ]

Whitaker
я рассмотрел как Вы сказали у меня получилось, что $F_1$ делится на $d>1$

[Whitaker]

Ну вот и ВСЁ!
Вы пришли к противоречию, т.е. число $1$ делится на $d>1$, но это невозможно! Полученное противоречие доказывает Ваше утверждение!

[bot]

Ну получилось и получилось. Вывод-то какой?

[RFZ]

Whitaker
Я Вам очень благодарен за помощь