Divisible by 17

[ins-]

Let x is the greatest positive root of the equation x^3-3x^2+1=0. Prove that [x^{1788}] is divisible to 17.

[Хорхе]

Где-то в задаче про трисекцию угла видал я это уравнение.

[Руст]

Уравнение имеет 3 действительных корня $-0.6<x_1<-0.5, 0.6<x_2<0.7, 2<x_3=x$. Вычислим числа $A_n=x_1^n+x_2^n+x_3^n, [x_3^n]=A_n-1,n>0$. Так как обратные величины $y_i=\frac{1}{x_i}$ удовлетворяют уравнению $y^3-3y+1=0$, получаем $A_{-1}=0$. Очевидно $A_0=3,A_1=3$. Эта последовательность удовлетворяет рекурентному соотношению $A_{n+3}=3A_{n+2}-A_n$.
Обозначим через A матрицу:
$3 \ \ 0 \ -1$
$1 \ \ 0 \ \ 0$
$0 \ \ 1 \ \ 0$
Остается вычислить n ую степень этой матрицы по модулю $p=17$. Период (не обязательно минимальный) равен $p^3-1$.
Можно вычислить, квадрат этой матрицы, четвертую степень (по модулю 17) и т.д. Перемножив их любую степень по модулю 17. Таким образом определится $A_n$ и $[x^n]=A_n-1\mod 17.$

[AlexandreII]

1. максимальный корень $2<x<3$.
2. $x^2 = \frac{1}{3-x}$

[maxal]

AlexandreII в сообщении #362347 писал(а):

Очевидно $A_0=3,A_1=3$. Эта последовательность удовлетворяет рекурентному соотношению $A_{n+3}=3A_{n+2}-A_n$.

Отсюда, а также из того, что $A_2=9$, следует, что по модулю 17 последовательность имеет период 16: (3, 3, 9, 7, 1, 11, 9, 9, 16, 5, 6, 2, 1, 14, 6, 0).
Поэтому:

$$A_{1788} \equiv A_{12} \equiv 1 \pmod{17}.$$

[Руст]

maxal в сообщении #362519 писал(а):

по модулю 17 последовательность имеет период 16: (3, 3, 9, 7, 1, 11, 9, 9, 16, 5, 6, 2, 1, 14, 6, 0).
Поэтому:

$$A_{1788} \equiv A_{12} \equiv 1 \pmod{17}.$$

Чтобы это проверит надо выписать еще 3 члена или два с учетом $A_{-1}=0=A_{15}$.
Это действительно выполняется. Я отмечал что период должен быть делителем $p^3-1=(p-1)(p^2+p+1)$. Второй сомножитель в этом случае простое число 307. То, что период делитель первого сомножителя 16 посчитал маловероятным и поленился проверит и не вычислил квадраты матриц 4 раза (до 16 - ой) степени.