|
Последовательность целых чисел задается следующим образом: $%a_1=2$% , $%a_{n+1}=2a_n^2-1$%. Показать, что для любого $%n$% числа $%a_n$% и $%n$% взаимопростые задан 16 Окт '13 20:32 
Танюша |
|
Предположим, что при некотором $%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 
falcao Спасибо за решение, третий день мучаюсь :-) Немного не поняла про периодичность, если можно прокомментируйте.
(16 Окт '13 21:20)
Танюша
Здесь каждое следующее число однозначно зависит от предыдущего. И если какое-то число даёт в остатке $%r$%, то следующее будет давать тот же остаток, что $%2r^2-1$%. Остатков же от деления на $%p$% конечное число, поэтому в бесконечной последовательности они обязаны повторяться, начиная с некоторого номера (но не обязательно с самого начала). Для примера: если $%p=13$%, то остатки будут такие: 2, 7, 6, 6, ... . Здесь 2, 7 -- непериодическая часть, и далее 6 в периоде.
(16 Окт '13 21:27)
falcao
|
|
Воспользуемся свойством $%НОД(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 
chameleon Тут показана взаимная простота $%a_n$% и $%a_{n+1}$%, это не совсем то, что нужно
(16 Окт '13 20:49)
Танюша
|