Докажите, что для любого целого $%n≥0$% числа $%F_n$% и $%F_{n+1}$% взаимно просты (то есть их наибольший общий делитель равен 1).

задан 6 Ноя '15 22:16

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)$%.

(6 Ноя '15 22:24) EdwardTurJ

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

(7 Ноя '15 1:27) a2g
1

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

(7 Ноя '15 2:12) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×137
×130
×46
×24
×18

задан
6 Ноя '15 22:16

показан
978 раз

обновлен
7 Ноя '15 2:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru