Целая часть степени корня кубического уравнения

[nnosipov]

Пусть $\alpha$ --- наибольший корень уравнения $x^3-3x^2+1$. Вычислите $[\alpha^{p+1}] \bmod{p}$, где $p$ --- простое число.

Примечание. Квадратные скобки обозначают целую часть.

[Dmitriy40]

Я опять влезу с тупым перебором, вдруг кому пригодится для сверки.

(Оффтоп)

Для $p=18k \pm 1$ результат равен $8$, для остальных $p-1$. Забавно.

[nnosipov]

Dmitriy40
Да, ответ, безусловно, верный. Надеюсь, кто-нибудь напишет объяснение.

[maxal]

Понятно почему:
https://en.wikipedia.org/wiki/Pisot%E2% ... PV-numbers
https://en.wikipedia.org/wiki/Newton%27 ... olynomials

[nnosipov]

maxal
А как со степенными суммами работать? Что-то я не понимаю, как здесь могут помочь тождества Ньютона.

А про числа Пизо хорошее замечание (я почему-то про них и не вспомнил).

[vpb]

(Оффтоп)

Интересно, Как Вы их придумываете или откуда выкапываете ? Надо бы мне хоть одну как-нибудь попытаться решить...

[maxal]

nnosipov, так в лоб же. Мы знаем $e_1=3$, $e_2=0$, $e_3=-1$ и $e_k=0$ для $k>3$, а нужно вычислить сумму $(p+1)$-х степеней.

[nnosipov]

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

так в лоб же

Да, но там придется оценивать сумму

$$\sum_{r_3=0}^{[m/3]}\frac{(m-2r_3-1)!}{(m-3r_3)!r_3!}(-3)^{m-3r_3}$$

при $m=p+1$ по модулю $p$. Неужели это можно сделать непосредственно? Эта сумма вычисляется (в поле $\mathbb{R}$), но это вернет нас к тривиальному выражению для степенной суммы. В любом случае нужно будет придумывать какой-то трюк, ибо для произвольного кубического многочлена это не будет работать (так как ответ в разумном виде вряд ли возможен).

vpb
С этой задачей такая история: нашел ее случайно в одном из файлов от одного питерского товарища; эта была задача для школьников, но в оригинальной формулировке она мне показалась несколько пресной, вот и решил добавить "немного специй". Впрочем, судите сами, вот оригинальная формулировка: докажите, что числа $[\alpha^{1788}]$ и $[\alpha^{1988}]$ делятся на $17$.

[maxal]

nnosipov в сообщении #1491302 писал(а):

Да, но там придется оценивать сумму

$$\sum_{r_3=0}^{[m/3]}\frac{(m-2r_3-1)!}{(m-3r_3)!r_3!}(-3)^{m-3r_3}$$

при $m=p+1$ по модулю $p$. Неужели это можно сделать непосредственно?

Ну так у нас же $(m-2r_3-1)!=(p-2r_3)!\equiv -\frac{(p-1)!}{(2r_3-1)!}\pmod{p}$, что всё облегчает.

[nnosipov]

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

что всё облегчает

Увы, не вижу, как облегчает. Этот факториальный коэффициент при $(-3)^{m-2r_3}$ ведет себя непонятно как по модулю $p$. И если, кстати, в сумме степень $(-3)^{m-2r_3}$ заменить на (например) $(-4)^{m-2r_3}$, то результат (значение суммы) становится трудно предсказуемым. Возможно, я чего-то не вижу. Буду рад, если дадите подробное объяснение.

[vpb]

nnosipov в сообщении #1491302 писал(а):

Впрочем, судите сами, вот оригинальная формулировка: докажите, что числа $[\alpha^{1788}]$ и $[\alpha^{1988}]$ делятся на $17$.

Что ж, подумаем ...

[maxal]

nnosipov, сумма сворачивается в что-то такое:

$$\int_0^1 [x^1] (x^2y+x^{-1}-3)^{p-1}\, dy = \int_0^1 [x^p] (x^3y+1-3x)^{p-1}\, dy$$

Далее можно использовать мультисекцию рядов для вычисления коэффициента при $x^p$ (как разность суммы по корням степени $p$ и суммы по корням степени $2p$) в $(x^3y+1-3x)^{p-1}$, но провести все выкладки пока нет времени.

[nnosipov]

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

но провести все выкладки пока нет времени

Да не горит. Но, вообще, хотелось бы в образовательных целях увидеть пример подобной техники. Думаю, это было бы интересно не только мне.

[Руст]

Составляете рекурентную последовательность с таким характеристическим уравнением:

$$x_{n+1}=3x_n-x_{n-2}.$$

Берем решение, являющееся последовательностью Люка (Это я так называю)
$V_n=x_1^n+x_2^n+x_3^n. Если $x_1=\alpha$ максимальный корень, то $2<\alpha <3$ и $x_2,x_3$ корни по модулю меньше 1.
Причем, положительный из них больше, так как $\alpha+x_2+x_3=3>\alpha$.
Поэтому $[\alpha^{n+1}]=V_{n+1}-1$.
Начальные условия $V_0=3, V_1=3, V_2=9$. Согласно автоморфизму Фробениуса $V_{p+1}=V_2\mod p$, Следовательно $[\alpha^{p+1}]=8\mod p$.

[nnosipov]

Руст в сообщении #1491402 писал(а):

Следовательно $[\alpha^{p+1}]=2\mod p$.

Это неверно. Правильный ответ был дан выше.

И хотя правильные слова уже произнесены, есть нюанс.

-- Вт ноя 10, 2020 00:17:05 --

Руст в сообщении #1491402 писал(а):

Следовательно $[\alpha^{p+1}]=8\mod p$.

Вот так вернее. Но все равно не совсем.