Сравнимы modp

[xmaister]

Пусть $f\in\mathbb{Z}[x]$ и $p$- простое. Докажите, что $\prod\limits_{i=1}^{p-1}f(z_i)\equiv\prod\limits_{i=1}^{p-1}f(i)\pmod{p}$, где $z_i$- корень из $1$ степени $p-1$. Я что-то не понимаю смысла этого упражнения. Вот беру например $f=1+2x+3x^2$, тогда слева получаю толпу комплексных чисел, а с права число целое. Как быть?

[Aritaborian]

Где вы там вообще нашли комплексные числа?

[nnosipov]

xmaister в сообщении #644066 писал(а):

слева получаю толпу комплексных чисел

Когда Вы их перемножите, получится целое число (ибо всякий симметрический многочлен можно выразить через элементарные симметрические многочлены).

[xmaister]

nnosipov
, тогда хорошо бы понять, как то доказывать.

[fancier]

xmaister в сообщении #644066 писал(а):

Пусть $f\in\mathbb{Z}[x]$ и $p$- простое. Докажите, что $\prod\limits_{i=1}^{p-1}f(z_i)\equiv\prod\limits_{i=1}^{p-1}f(i)\pmod{p}$, где $z_i$- корень из $1$ степени $p-1$. Я что-то не понимаю смысла этого упражнения. Вот беру например $f=1+2x+3x^2$, тогда слева получаю толпу комплексных чисел, а с права число целое. Как быть?

Доказательство для $f(x)=x$ следует из двух фактов: произведение всех комплексных корней степени $p-1$ из 1 равно $-1$, а произведение всех ненулевых элементов конечного поля $\mathbb{Z}_p$ сравнимо с $-1$ по $\mod p$ (см. теорему Вильсона). Отсюда легко следует утверждение для мономов, а значит, и для произвольных многочленов $f\in \mathbb{Z}[x].$

[xmaister]

fancier в сообщении #644181 писал(а):

а значит, и для произвольных многочленов $f\in \mathbb{Z}[x].$

Расскажите пожалуйста поподробнее, как следует?

[Sonic86]

Я не понял: $z_i$ - это корни в $\mathbb{C}$ или в $\mathbb{Z}_p^\times$?

[fancier]

xmaister в сообщении #644185 писал(а):

fancier в сообщении #644181 писал(а):

а значит, и для произвольных многочленов $f\in \mathbb{Z}[x].$

Расскажите пожалуйста поподробнее, как следует?

Видимо, я поторопился. Нужно, видимо, использовать сравнимость элементарных симметрических многочленов от корней $z_1,\ldots , z_{p-1}$ и от ненулевых элементов конечного поля: и те, и другие удовлетворяют уравнению $x^{p-1}-1=0.$

[AV_77]

Нужно использовать, что слева симметрический многочлен от корней $(p-1_$)-й степени из 1.

[nnosipov]

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

Я не понял: $z_i$ - это корни в $\mathbb{C}$ или в $\mathbb{Z}_p^\times$?

В $\mathbb{C}$, конечно, иначе доказывать нечего. Что касается доказательства, то я бы построил гомоморфизм $\varphi:\mathbb{Z}[\zeta] \to \mathbb{Z}_p$, такой, что $\varphi(\zeta)=g$ (здесь $\zeta=\cos{\frac{2\pi}{p-1}}+i\sin{\frac{2\pi}{p-1}} \in \mathbb{C}$, а $g \in \mathbb{Z}_p$ --- некоторый первообразный корень по модулю $p$). Но для этого потребуется поэксплуатировать некоторые свойства кругового многочлена $\Phi_{p-1}(x)$, а именно: а) $\Phi_{p-1}(x) \in \mathbb{Z}[x]$; б) $\Phi_{p-1}(x)$ неприводим над $\mathbb{Q}$; в) $\Phi_{p-1}(g)=0$, где $g$ --- любой первообразный корень по модулю $p$.

Возможно, что есть более простое рассуждение, но что-то я его не вижу.

[fancier]

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

Возможно, что есть более простое рассуждение, но что-то я его не вижу.

А где ошибка в таком рассуждении:
1) Для $f\in \mathbb{Z}[x]$ имеет место равенство

$$\prod_{j=1}^{p-1}f(x_j)=F(\sigma_1(x_1,\ldots ,x_{p-1}),\ldots , \sigma_{p-1}(x_1,\ldots x_{p-1})),\qquad (1)$$

где $\sigma_k$ -- элементарные симметрические многочлены, а $F\in \mathbb{Z}[X_1,\ldots ,X_{p-1}].$

2) $\sigma_k(z_1,\ldots ,z_{p-1})\equiv \sigma_k(1,2,\ldots ,p-1)\mod p,$ так как корни из единицы $z_j$ степени $p-1$ и ненулевые вычеты по $\mod p$ удовлетворяют уравнениям одинакового вида $X^{p-1}-1=0$, а элементарные симметрические многочлены суть его коэффициенты.

3) Подставляя значения симметрических многочленов в (1), получаем требуемое сравнение.

[nnosipov]

fancier в сообщении #644403 писал(а):

А где ошибка в таком рассуждении:

Да нет ошибки, это я всё усложнил.

[xmaister]

nnosipov
Не совсем понятно, как определяетс круговой многочлен $\text{Ф}_n(x)$. Как многочлен над $\mathbb{Z}[\zeta]$, где $\zeta$- корень из $1$ степени $n$? Тогда почему, если $n=p-1$, То все его коэффициенты- целые?

[nnosipov]

xmaister в сообщении #644901 писал(а):

Не совсем понятно, как определяется круговой многочлен $\text{Ф}_n(x)$.

Про круговые многочлены $\Phi_n(x)$ лучше где-нибудь почитать (знакомство с ними, на мой взгляд, полезно само по себе). Можно, например, у Прасолова, "Многочлены". Вот формальное определение: $\Phi_n(x)=\prod (x-\zeta)$, где $\zeta$ пробегает все комплексные примитивные корни из единицы степени $n$ (в частности, $\deg{\Phi_n(x)}=\varphi(n)$ --- функция Эйлера от $n$). Первое упражнение --- это понять, почему $\Phi_n(x)$ имеет целые коэффициенты (здесь поможет формула обращения Мёбиуса). Ну а дальше --- много других интересных фактов.