Последовательность и 2011

[staric]

Целочисленная последовательность (ТМ Xenia1996 ) задана следующей формулой:

$a_{n+1}=3a_n-a_{n-1}, a_1=1, a_2=1 $

Найти наименьший член последовательности, кратный 2011.

[Sonic86]

По-моему, таких нет:
$a_n=C_1 \alpha ^{n-1} + C_2 \beta ^{n-1}$
$\alpha = \frac{3+\sqrt{5}}{2}, \beta = \frac{3-\sqrt{5}}{2}, \alpha \beta = 1$
$C_1 = \frac{5-\sqrt{5}}{10}, C_2 = \frac{5+\sqrt{5}}{10}, C_1C_2 = 5^{-1}$
Тогда
$a_n \equiv 0 \pmod p \Leftrightarrow C_1 \alpha ^{2n-2} + C_2 \equiv 0 \pmod p \Leftrightarrow$
$\Leftrightarrow \alpha ^{2n-2} \equiv -C_2C_1^{-1} \equiv -5C_2^2 \pmod p,$
что возможно тогда и только тогда, когда $\left( \frac{-5}{p} \right) = 1$, в то время как
$\left( \frac{-5}{2011} \right) = \left( \frac{-1}{2011} \right) \left( \frac{5}{2011} \right) = -1 \cdot (-1)^{\frac{2011-1}{2} \cdot \frac{5-1}{2}} \left( \frac{2011}{5} \right) = -1$.
И еще забыл сказать, что символ Лежандра мы можем применить потому, что $\alpha \in \mathbb{Z}_p$, поскольку $\left( \frac{5}{2011} \right) =1$.
Проверьте.

(Оффтоп)

уверен, что Xenia1996 знает решение проще или найдет здесь ошибку

[svv]

Это последовательность Фибоначчи, из которой выброшены элементы с четными индексами.

[svv]

Последовательность остатков от деления $a_n$ на $2011$ периодическая, период равен $1005$. Нулевой остаток не встречается.

[staric]

Sonic86 в сообщении #429429 писал(а):

И еще забыл сказать, что ...

Отсюда подробнее, а то я уж хотел предложить
$\left( \frac{-5}{17} \right) посчитать

svv в сообщении #429503 писал(а):

Последовательность остатков от деления $a_n$ на $2011$ периодическая, период равен $1005$. Нулевой остаток не встречается.

Вы реально проверяли? Респект. А если б я 62011 предложил?

[ИСН]

"Подумаешь, бином Ньютона". Там всё то же самое, только период 3445.

[svv]

Конечно. Проверяет-то программа. Ну, был бы ещё в 30 раз больший респект (если зависимость линейная).
И ещё интересно. Период состоит из двух зеркально-симметричных частей. Один элемент для обеих частей общий, поэтому период нечетный.
Так что размер "неповторимости" всего 503.

[staric]

svv в сообщении #429602 писал(а):

Конечно. Проверяет-то программа.

Я вообще поначалу заподозрил использование A060305 , но потом понял - без железа никак.

ИСН в сообщении #429563 писал(а):

"Подумаешь, бином Ньютона".

Конечно, надо было сразу 10000002011 дать А то вроде как получается, Sonic86 не по делу старался...

[svv]

staric писал(а):

А то вроде как получается, Sonic86 не по делу старался...

Нет, ну что Вы... По умолчанию каждое следующее сообщение не отрицает, а дополняет предыдущие.

[Батороев]

По-видимому, в рассмотрении можно где-то попытаться использовать формулу $5a^2-4=b^2$, характеризующую элементы последовательности Фибоначчи, имеющие нечетные номера.

[Батороев]

Если предположить, что какое-то число из рассматриваемой последовательности $a_n$ кратно $2011$, то $b^2+4=5a^2$ тоже должно делиться на $2011$.
Число, равное сумме двух квадратов, не может иметь делители, отличные от тех, что имеют остаток $1\pmod 4$, к которым $2011$ не относится.

[staric]

Батороев в сообщении #429943 писал(а):

Число, равное сумме двух квадратов, не может иметь ...

Это близко к авторскому решению. Можно воспользоваться ф-лой для Фибоначчи $F_{2n+1}=F_{n+1}^2+F_{n}^2$, и "спуститься" (ес-сно, для простых делителей вида 4k+3). Но мне отчего-то больше нравится решение Соника через символы Лагранжа.