Делимость.

[Руст]

Пусть $x_1,x_2$ корни уравнения $x^2+px+q=0,p,q\in Z$ и $A_n=x_1^n+x_2^n+p^n$.
Докажите, что все они целые и $A_4|A_{3k+1} \ \ \forall k\in N$.

[Brukvalub]

Про делимость не думал а про целостность: разве это не очевидно, учитывая симметричность многочлена $x_1^n+x_2^n$ и т. Виета?

[Руст]

Целость очевидна, просто нельзя говорит о делимости, не доказав целость.

[maxal]

Руст писал(а):

Пусть $x_1,x_2$ корни уравнения $x^2+px+q=0,p,q\in Z$ и $A_n=x_1^n+x_2^n+p^n$.
Докажите, что все они целые и $A_4|A_{3k+1} \ \ \forall k\in N$.

Я не верю - я проверю.

Для $p=11$ и $q=13$ получаем, что $A_7=11675664$ не делится на $A_4 = 23328$.

[Руст]

Да. На самом деле $A_4$ всегда чётное число и $\frac{A_4}{2}|A_{3k+1}$. А вышеуказанная делимость имеется всегда, если pq - чётное (это всегда так, когда числа $x_1,x_2$ целые).

[Sasha Rybak]

Задача несложно решается с помощью линейных рекуррентных последовательностей. Рассмотрим многочлен $(x^2+px+q)(x-p)=x^3+(q-p^2)x-pq$ - он является аннулирующим многочленом для $\{A_n\}$, то есть $\forall n \in \mathbb N:\ A_{n+3}+(q-p^2)A_{n+1}-pqA_n=0$.

Доказать это можно и непосредственно. А можно заметить, что если P(x) аннулирует последовательность в указанном смысле, то и любое P(x)Q(x) тоже её аннулирует. Также, если две последовательности аннулируются многочленом, то и их сумма - тоже. Тогда $x^2+px+q$ аннулирует $\{x_1^n\}$ и $\{x_2^n\}$, а $x-p$ аннулирует $\{p^n\}$, а из этого - $(x^2+px+q)(x-p)$ аннулирует $\{A_n\}$.

Заменим $p^2-q=a,\ pq=b$. Непосредственно вычисляется, что $A_1=0,\ A_2=2a,\ A_3=3b,\ A_4=2a^2$. Из соотношения $\forall n \in \mathbb N:\ A_{n+3}=aA_{n+1}+bA_n$ индукцией для целых неотрицательных k получаем, что $A_{3k+1} \equiv 0\ (\mathrm{mod}\ a^2),\ A_{3k+2} \equiv c_k a^{k+1}\ (\mathrm{mod}\ a^2),\ A_{3k+3} \equiv d_k a^k b\ (\mathrm{mod}\ a^2)$, где $c_k,d_k \in \mathbb N$.
Для $\{A_n\ (\mathrm{mod}\ 2a^2)\}$ решается аналогично.

[Руст]

Sasha Rybak писал(а):

$A_{3k+1} \equiv 0\ (\mathrm{mod}\ a^2),\ A_{3k+2} \equiv c_k a^{k+1}\ (\mathrm{mod}\ a^2),\ A_{3k+3} \equiv d_k a^k b\ (\mathrm{mod}\ a^2)$, где $c_k,d_k \in \mathbb N$.
Для $\{A_n\ (\mathrm{mod}\ 2a^2)\}$ решается аналогично.

Только $A_{3k+2}=c_kab^k\mod a^2, \ A_{3k+3}=d_kb^{k+1}\mod a^2$ (так как deg(a)=2, deg(b)=3, deg(A_n)=n). При вычислении по модулю 2a^2 (не совсем аналогично) требуется использовать чётность b.