Является ли полем факторкольцо

[ikozyrev]

Решаю тут экзамеционные задачки НМУ первого семестра по алгебре прошлых лет.
Вот одна из них:
Являются ли полями кольца $\math \mathbb F_{1907}[x]/(x^2+x+1) $ и $\math \mathbb F_{2011}[x]/(x^2+x+1) $.
1907 и 2011 - простые.
Понятно, что эти кольца будут полями если многочлен $\math x^2+x+1$ - неприводим над соответсвующими полями.
Но как это проверить? С помощью простой программы, перебором я проверил что для 1907 - многочлен неприводим, а для 2011 - приводим.
Как я понял, эффективных алгоритмов проверки неприводимости многочленов не существует, то есть тут либо перебор либо какой-то "олимпиадный" трюк с делимостью и.т.д.?

[Brukvalub]

Действительно, какого-либо универсального способа проверять неприводимость, видимо, нет. Обычно для этого лезут в таблицы таких многочленов. В данном случае, всякий корень многочлена $x^2+x+1$ может быть только неединичным решением уравнения $x^3=1$ Возможно, это позволит уменьшить перебор при проверке неприводимости.

[ikozyrev]

Brukvalub в сообщении #1165774 писал(а):

Действительно, какого-либо универсального способа проверять неприводимость, видимо, нет. Обычно для этого лезут в таблицы таких многочленов. В данном случае, всякий корень многочлена $x^2+x+1$ может быть только неединичным решением уравнения $x^3=1$ Возможно, это позволит уменьшить перебор при проверке неприводимости.

В таком случае на экзамене я бы привел код программы для проверки неприводимости :))

[Brukvalub]

Возможно, именно это и требовалось. Но что-то "неспортивное" в таком подходе проглядывает.

[kp9r4d]

Ну да, а приводимость второго многочлена из соображений выше как раз очень легко получается, ведь $2011-1$ делится нацело на 3 значит $2^{(2011-1)/3}$ и будет искомым корнем по теореме Ферма (потому что в кубе он даст единицу). Хотя это все заметили до меня, наверное.

[ikozyrev]

kp9r4d в сообщении #1165781 писал(а):

Ну да, а приводимость второго многочлена из соображений выше как раз очень легко получается, ведь $2011-1$ делится нацело на 3 значит $2^{(2011-1)/3}$ и будет искомым корнем по теореме Ферма (потому что в кубе он даст единицу). Хотя это все заметили до меня, наверное.

Угу. Но как проверить 1907? Только перебором?

[kp9r4d]

http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf Example 1.0.4

[g______d]

Вообще, вопрос о том, в каких конечных полях какие корни из единицы возможны, по-видимому, решён полностью и достаточно просто, см., например, http://mathoverflow.net/questions/58357 ... ite-fields

[ikozyrev]

kp9r4d в сообщении #1165785 писал(а):

http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf Example 1.0.4

Спасибо!
Действительно просто...

[VAL]

Brukvalub в сообщении #1165774 писал(а):

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

А как же алгоритм Берлекэмпа?
Конечно, применять его к квадратному трехчлену - это "стрелять из пушек по воробьям".
Так что, я не про этот частный случай, а про универсальный способ.

Разумеется, для данного частного случая не нужен ни Берлекэмп, ни даже перебор потенциальных корней: $x^2+x+1$ неприводим над $\mathbb Z_p$, когда $p$ сравнимо с двойкой по модулю 3. (Впрочем, про это здесь, кажется, уже написали.)

[RIP]

Многочлен $x^2+x+1$ имеет степень 2, поэтому он приводим тогда и только тогда, когда у него есть корень, т.е. нужно всего лишь посчитать символ Лежандра от дискриминанта. Если $p>2$ — простое число, $a,b,c\in\mathbb{Z}$, $p\mathrel{\nmid}a$, то многочлен $ax^2+bx+c$ неприводим над полем $\mathbb{F}_{p}$ тогда и только тогда, когда $\left(\dfrac{b^2-4ac}{p}\right)=-1$.

[Brukvalub]

VAL в сообщении #1165836 писал(а):

А как же алгоритм Берлекэмпа?

Согласен, мне нужно было добавить слова: "какого-либо универсального способа вручную за время экзамена силами испуганного студента проверить неприводимость , видимо, нет."

[VAL]

RIP в сообщении #1165838 писал(а):

Многочлен $x^2+x+1$ имеет степень 2, поэтому он приводим тогда и только тогда, когда у него есть корень, т.е. нужно всего лишь посчитать символ Лежандра от дискриминанта. Если $p>2$ — простое число, $a,b,c\in\mathbb{Z}$, $p\mathrel{\nmid}a$, то многочлен $ax^2+bx+c$ неприводим над полем $\mathbb{F}_{p}$ тогда и только тогда, когда $\left(\dfrac{b^2-4ac}{p}\right)=-1$.

Настаиваю, что найти остаток от деления $p$ на 3, все же, быстрее. Хотя понимаю, что вычисление символа Лежандра, по сути, сведется к тому же.

[RIP]

VAL в сообщении #1165848 писал(а):

Настаиваю, что найти остаток от деления $p$ на 3, все же, быстрее.

Это-то да. Если знать этот критерий заранее. Через символ Лежандра он получается сам собой:

$$\left(\frac{-3}{p}\right)=(-1)^{\frac{p-1}{2}}\cdot(-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)=\left(\frac{p}{3}\right).$$

Даже думать не нужно. Аналогичный критерий можно получить для любого фиксированного квадратного многочлена.

[ikozyrev]

RIP в сообщении #1165838 писал(а):

Многочлен $x^2+x+1$ имеет степень 2, поэтому он приводим тогда и только тогда, когда у него есть корень, т.е. нужно всего лишь посчитать символ Лежандра от дискриминанта. Если $p>2$ — простое число, $a,b,c\in\mathbb{Z}$, $p\mathrel{\nmid}a$, то многочлен $ax^2+bx+c$ неприводим над полем $\mathbb{F}_{p}$ тогда и только тогда, когда $\left(\dfrac{b^2-4ac}{p}\right)=-1$.

Для меня это неочевидно, но попробую в качестве упражнения это доказать..