Не могу найти ошибку

[Sonic86]

$$0 \equiv 0' \equiv (x^p-x)' \equiv px^{p-1}-1 \equiv -1 \pmod p$$

В чем ошибка?

[nnosipov]

Sonic86, а разве сравнения (тем более числовые) можно дифференцировать? Брать производную можно у многочлена, а $x^p-x$ отнюдь не нулевой многочлен.

[Sonic86]

Сравнение исключительно многоченное. Под $0$ понимается многочлен, тождественно равный нулю и с единицей аналогично. Кроме того, формальную производную брать никто не запрещал, ее даже используют для нахождения кратных корней у многочленов над полями.

Вопрос возник при решении Putnama B6, здесь: http://e-science.ru/forum/index.php?sho ... 5214&st=20
Там есть ссылка на AoPS, http://www.artofproblemsolving.com/Foru ... 9#p2531879 , используется этот прием. Я не могу понять рамки допустимости использования этого приема

[nnosipov]

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

Сравнение исключительно многоченное.

Сравнение $x^p-x \equiv 0 \pmod{p}$ является числовым, ибо оно верно при любом целом $x$. А как иначе его понимать?

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

Кроме того, формальную производную брать никто не запрещал, ее даже используют для нахождения кратных корней у многочленов над полями.

Само собой, но над полями конечной характеристики это надо делать аккуратно.

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

Там есть ссылка на AoPS

Что-то я не вижу, чтобы там дифференцировали.

[Sonic86]

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

Сравнение $x^p-x \equiv 0 \pmod{p}$ является числовым, ибо оно верно при любом целом $x$. А как иначе его понимать?

Гм, пожалуй, я торможу... Надо бы примеров пособирать, поразличать... Не очень понятно, почему это не сравнение многочленов...

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

Что-то я не вижу, чтобы там дифференцировали.

Я тоже не вижу. Я в упор не понимаю, откуда берется кратность корней. Вид суммы $\sum\limits_{k=0}^{p-1}\frac{x^k}{k!}$ и поиск ее кратных корней подталкивает только к использованию производной. Других идей нет...

-- Чт дек 08, 2011 14:23:21 --

Ааааа!!!! Я посмотрел решение жюри! Они там дифференцируют!!!! (ссылка на e-science, ну или сразу: http://amc.maa.org/a-activities/a7-prob ... ndex.shtml)

[nnosipov]

Я ничего не смотрел, но здесь всё понятно. Утверждается, что любой корень $a$ многочлена $f(x)=\sum_{k=0}^{p-1} x^k/k!-x+x^p$, лежащий в $\mathbb{F}_p$, является кратным. Действительно, ясно, что $a \neq 0$ и, как легко заметить, $a$ является корнем $f'(x)$ (по малой теореме Ферма и теореме Вильсона). Если мы предположим, что $f(x)=(x-a)g(x)$, где $g(a) \neq 0$ (т.е. что корень $a$ простой), то моментально получим противоречие.

[Sonic86]

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

Утверждается, что любой корень $a$ многочлена $f(x)=\sum_{k=0}^{p-1} x^k/k!-x+x^p$, лежащий в $\mathbb{F}_p$, является кратным.

Мы же ищем корни в $\mathbb{Z}_p$? Значит и многочлен над $\mathbb{Z}_p$? Но тогда $f(x) \equiv \sum\limits_{k=0}^{p-1} x^k/k! \pmod p$, а у этого многочлена кратных корней нет (это можно "доказать" с помощью производной) или рассмотреть случай $p=5$ - получаемый многочлен имеет 1 некратный корень.

-- Чт дек 08, 2011 15:16:34 --

Вы же только что говорили, что в $\mathbb{Z}_p$ дифференцировать нельзя. А сами дифференцируете.

[nnosipov]

Sonic86, многочлены $f_1(x)=\sum_{k=0}^{p-1}x^k/k!-x+x^p$ и $f_2(x)=\sum_{k=0}^{p-1}x^k/k!$ --- это разные многочлены над $\mathbb{F}_p$ (другое дело, что они задают одну и ту же функцию $\mathbb{F}_p \to \mathbb{F}_p$). Поэтому то, что $f_2(x)$ не имеет кратных корней, не означает, что их нет у $f_1(x)$.

[Sonic86]

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

$f_1(x)=\sum_{k=0}^{p-1}x^k/k!-x+x^p$ и $f_2(x)=\sum_{k=0}^{p-1}x^k/k!$ --- это разные многочлены над $\mathbb{F}_p$ (другое дело, что они задают одну и ту же функцию $\mathbb{F}_p \to \mathbb{F}_p$

Так. Вроде понятно. Функции одинаковые, да. Многочлены разные (вектора коэффициентов из $\mathbb{Z}_p^{\infty}$ разные). Но множества корней-то у них одинаковые. Хотя кратность необязательно одинаковая, так? Т.е., например, множество многочленов $f(x)+(x^p-x)^k$ имеют разные кратности корней, а множества корней одинаковы...
Пойду кратности повычисляю...

[nnosipov]

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

Вы же только что говорили, что в $\mathbb{Z}_p$ дифференцировать нельзя. А сами дифференцируете.

Я не говорил, что нельзя. Формальная производная многочлена всегда существует. Но нужно быть аккуратным, перенося некоторые утверждения, в формулировке которых участвуют производные, с обычных многочленов (скажем, с числовыми коэффициентами или, более общо, над полем нулевой характеристики) на многочлены, заданные над полем характеристики $p$. Возьмём, к примеру, такое утверждение: многочлен $f(x)$ взаимно прост со своей производной тогда и только тогда, когда он не имеет кратных неприводимых делителей (над тем полем, над которым он задан). Над полем ненулевой характеристики это утверждение может оказаться неверным (правда, над полем $\mathbb{F}_p$ оно всё-таки верно, но это не очевидно). А вот с утверждением о том, что $a$ --- кратный корень $f(x)$ тогда и только тогда, когда $f(a)=f'(a)=0$, всё в порядке, оно верно над любым полем (собственно, в данной задаче используется именно это утверждение). Наконец, третий пример: утверждение о том, что многочлен взаимно прост со своей производной тогда и только тогда, когда он не имеет кратных корней. Здесь нужны дополнительные пояснения: где именно он не должен иметь кратных корней. Если в своём поле разложения, то всё ok; если же только в поле своих коэффициентов, то утверждение может оказаться неверным.

[Sonic86]

Ух, спасибо, пока вроде понятно.
Сейчас я еще с кратностями поиграюсь и скорее всего этого хватит...

-- Чт дек 08, 2011 16:10:42 --

Все правильно Благодарю Вас.