2
1

Последовательность целых чисел задается следующим образом: $%a_1=2$% , $%a_{n+1}=2a_n^2-1$%. Показать, что для любого $%n$% числа $%a_n$% и $%n$% взаимопростые

задан 16 Окт '13 20:32

10|600 символов нужно символов осталось
2

Предположим, что при некотором $%n$% числа $%a_n$% и $%n$% не являются взаимно простыми. Тогда у них имеется общий простой делитель $%p$%. Последовательность остатков от деления на $%p$% для чисел $%a_1$%, $%a_2$%, $%\cdots$% имеет повторения, а из этого следует, что , начиная с некоторого номера, она становится периодической. Она может иметь непериодическую часть, которая не является слишком длинной. В пределах этой непериодической части остатки не повторяются, и в неё не входит хотя бы один из остатков, входящий в период. Следовательно, длина непериодической части не превосходит $%p-1$%.

У нас по условию $%a_n$% делится на $%p$%, то есть даёт остаток, равный нулю. Следующее за ним число $%a_{n+1}$% даёт тот же остаток, что и $%2\cdot0^2-1$%, то есть $%p-1$%. Тогда $%a_{n+2}$% должно давать в остатке столько же, сколько даёт $%2(p-1)^2-1$%, то есть $%1$%. После этого остаток $%1$% будет повторяться в периоде.

Таким образом, в исследуемом случае непериодическая часть имеет длину $%n+1$%, что заведомо больше $%p$%, так как $%n$% делится на $%p$%. Пришли к противоречию.

ссылка

отвечен 16 Окт '13 21:10

Спасибо за решение, третий день мучаюсь :-) Немного не поняла про периодичность, если можно прокомментируйте.

(16 Окт '13 21:20) Танюша

Здесь каждое следующее число однозначно зависит от предыдущего. И если какое-то число даёт в остатке $%r$%, то следующее будет давать тот же остаток, что $%2r^2-1$%. Остатков же от деления на $%p$% конечное число, поэтому в бесконечной последовательности они обязаны повторяться, начиная с некоторого номера (но не обязательно с самого начала). Для примера: если $%p=13$%, то остатки будут такие: 2, 7, 6, 6, ... . Здесь 2, 7 -- непериодическая часть, и далее 6 в периоде.

(16 Окт '13 21:27) falcao
10|600 символов нужно символов осталось
0

Воспользуемся свойством $%НОД(a;b)=НОД(a;b-ac)$%. $$НОД(a_n;2a_n^2-1)=НОД(a_n;2a_n^2-1-a_n(2a_n-1))=НОД(a_n;a_n-1)=1$$ Следовательно, числа взаимнопростые.

ссылка

отвечен 16 Окт '13 20:44

Тут показана взаимная простота $%a_n$% и $%a_{n+1}$%, это не совсем то, что нужно

(16 Окт '13 20:49) Танюша
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×119

задан
16 Окт '13 20:32

показан
590 раз

обновлен
16 Окт '13 21:27

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

по почте:

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

по RSS:

Ответы

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

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