Разложить многочлен в кольце.

[VAL]

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

PWT, если Вы действительно хотите разобраться, то Вам следует начинать с выяснения того, как устроено поле $\mathbb Z_5$, как выполнять операции над его элементами.
Это не сложно.

[PWT]

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

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

PWT, если Вы действительно хотите разобраться, то Вам следует начинать с выяснения того, как устроено поле $\mathbb Z_5$, как выполнять операции над его элементами.
Это не сложно.

Это я понимаю, что это множество из пяти чисел с операциями сложения и умножения, для которых выполнены известные аксиомы.

Причем в поле $\mathbb Z_5$ для $\forall x\in \mathbb Z_5$ и $\forall n\in \mathbb Z$ известно, что $x+5\cdot n=x$.

Правильно ли я понимаю?

P.S. Давненько с абстрактной алгеброй не сталкивался, потому сильно путаюсь.

-- 12.06.2016, 23:51 --

Многочлен называется приводимым над кольцом тогда и только тогда, когда он разлагается в произведение по крайней мере двух многочленов ненулевой степени с коэффициентами из того же кольца. Если же такое разложение многочлена в произведение многочленов над тем же кольцом невозможно, то этот многочлен называется неприводимым.

[Otta]

Чудесно. Если умножить два многочлена (над все тем же кольцом) $x-3$ на $x+3$ - получится многочлен над этим кольцом или как?

[PWT]

Otta в сообщении #1131115 писал(а):

Чудесно. Если умножить два многочлена (над все тем же кольцом) $x-3$ на $x+3$ - получится многочлен над этим кольцом или как?

$(x-3)(x+3)=x^2-9$. Девятка не входит в множество $\{0,1,2,3,4\}$, потому нет.

Хотя $x^2-9 \equiv x^2+1 (\bmod 5)$, a $x^2+1$ будет над этим кольцом.

Правильно ли?

[Otta]

PWT в сообщении #1131118 писал(а):

Хотя $x^2-9 \equiv x^2+1 (\bmod 5)$, a $x^2+1$ будет над этим кольцом.

Вот именно.
И что минус девятка не входит в то множество, погоды не делает - она входит в один класс с единицей. Фактор-группа - это набор классов. Класс отождествляется с одним элементом, для удобства здесь договорились брать первые пять целых неотрицательных. Это только запись. Иногда (по первости) пишут так: $[0],[1],\ldots [4]$, чтоб уж наверняка.

Впрочем, Вы говорили, что знаете, что такое фактор-группа.

[PWT]

Спасибо, теперь стало еще понятнее.

Но не ясно вот что.

Рассмотрим $P(x)=x^2+1$

Многочлен разложим над кольцом $\mathbb{Z}_5$ (это уже обсуждали выше, он сравним по модулю пять с $x^2-9=(x-3)(x+3)$.

Но $P(a)\ne 0$ для $a=0,1,2,3$. Но ведь из-за нарушения именно этих условий забраковали исходный многочлен из стратпоста. Как так? Ведь этот приводим.

[Otta]

PWT
Напишите, как считали.

[VAL]

PWT в сообщении #1131111 писал(а):

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

PWT, если Вы действительно хотите разобраться, то Вам следует начинать с выяснения того, как устроено поле $\mathbb Z_5$, как выполнять операции над его элементами.
Это не сложно.

Это я понимаю, что это множество из пяти чисел с операциями сложения и умножения, для которых выполнены известные аксиомы.

Правильно ли я понимаю?

Нет.

Поле $\mathbb Z_5$ (как и любое кольцо классов вычетов по модулю) состоит не из чисел, а из классов. И каждое целое число входит ровно в один класс.

[ewert]

PWT в сообщении #1131125 писал(а):

Но $P(a)\ne 0$ для $a=0,1,2,3$.

Чему равно $2^2+1$ и $3^2+1$ ?

[PWT]

ewert в сообщении #1131158 писал(а):

PWT в сообщении #1131125 писал(а):

Но $P(a)\ne 0$ для $a=0,1,2,3$.

Чему равно $2^2+1$ и $3^2+1$ ?

Спасибо, понятно, попадает в класс нулей.

-- 13.06.2016, 12:08 --

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

Одним из необходимых условий приводимости над $\mathbb Z_5$ является попадание $P(a)$ в класс нулей при одном из $a=0,1,2,3,4$.
Есть ли еще какие-то простые необходимые условия.

Правильно ли я понимаю, что можно сказать, про эти многочлены?

1) $x^2+1$ -- над полем $\mathbb Z_5$

2) $x^2+9$ -- не над полем $\mathbb Z_5$

3) $7x^2+8x+9$ над полем $\mathbb Z_5$

Правильно ли я понимаю, чтобы разложить многочлен $P(x)$ над $\mathbb Z_5$ перебором, то нужно пробовать раскладывать многочлены, сравнимые с $P(x)$ по модулю пять, такие что они раскладываются на произведения других многочленов, коэффициенты у которых $0,1,2,3,4$?

[Sonic86]

PWT в сообщении #1131193 писал(а):

Одним из необходимых условий приводимости над $\mathbb Z_5$ является попадание $P(a)$ в класс нулей при одном из $a=0,1,2,3,4$.
Есть ли еще какие-то простые необходимые условия.

Не необходимое, а достаточное.

PWT в сообщении #1131193 писал(а):

1) $x^2+1$ -- над полем $\mathbb Z_5$

Это утверждение что-ли? Если да, то все 3 многочлена являются многочленами над $\mathbb{Z}_5$ (можно над коэффициентами черточки поставить, чтобы не путать с целыми числами)

PWT в сообщении #1131193 писал(а):

Правильно ли я понимаю, чтобы разложить многочлен $P(x)$ над $\mathbb Z_5$ перебором, то нужно пробовать раскладывать многочлены, сравнимые с $P(x)$ по модулю пять, такие что они раскладываются на произведения других многочленов, коэффициенты у которых $0,1,2,3,4$?

Очень странная формулировка. При чем тут вообще $0,1,2,3,4$???

[PWT]

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

Очень странная формулировка. При чем тут вообще $0,1,2,3,4$???

Коэффициенты должны быть из этого же кольца.

Это связано с определением разложимости:

Многочлен называется приводимым над кольцом тогда и только тогда, когда он разлагается в произведение по крайней мере двух многочленов ненулевой степени с коэффициентами из того же кольца. Если же такое разложение многочлена в произведение многочленов над тем же кольцом невозможно, то этот многочлен называется неприводимым.

Коэффициенты должны быть из этого же кольца.

-- 13.06.2016, 12:43 --

Из этого же примера

Цитата:

Если умножить два многочлена (над все тем же кольцом) $x-3$ на $x+3$ - получится многочлен над этим кольцом или как?

получался многочлен не из этого же кольца $x^2-9$ неразложим из-за девятки. Почему же тогда разложим $x^2+9$?

Там были вопросы, а не утверждения*

-- 13.06.2016, 12:45 --

А если над коэф не ставить черточки, понимая под этим именно целые числа, то тогда многочлен не из кольца?

[Sonic86]

PWT в сообщении #1131205 писал(а):

Коэффициенты должны быть из этого же кольца.

Да, но что, Вы считаете, что ли, что $7\not\in\mathbb{Z}_5$? Так это неверно.

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

$\mathbb{Z}_5=\langle\{\{...-10,-5,0,5,10,...\},\{...-9,-4,1,6,11,...\},...,\{...-6,-1,4,9,14,...\}\};+;\cdot \rangle$

Т.е. строго говоря есть $\mathbb{Z}=\{...-2,-1,0,1,2,...\}$, а есть $\mathbb{Z}_5=\{5\mathbb{Z},1+5\mathbb{Z},2+5\mathbb{Z},3+5\mathbb{Z},4+5\mathbb{Z}\}$. Элементы его также обозначают $[0],[1],[2],[3],[4]$ или $\bar 0, \bar 1, \bar 2, \bar 3, \bar 4$. Есть каноническое отображение $\varphi:\mathbb{Z}\to\mathbb{Z}_5$ по правилу $x\to x+5\mathbb{Z}$. $\varphi$ также легко индуцирует отображение многочленов $\psi:\mathbb{Z}[x]\to\mathbb{Z}_5[x]$ по правилу $\psi(a_nx^n+...+a_0)=\varphi(a_n)x^n+...+\varphi(a_0)$, которое всюду определено И если Вы пишете $x^2+1$ над $\mathbb{Z}_5$ то на самом деле Вы имеете ввиду $(1+5\mathbb{Z})x^2+(1+5\mathbb{Z})$. Но все это формально расписывать мне лень, потому обычно просто пишут $x^2+1$, имея ввиду $\psi(x^2+1)$. А поскольку $\psi$ всюду определено, то нафиг не нужны никакие проверки на то, лежат ли коэффициенты в $\mathbb{Z}_5$ или нет - они там всегда лежат.

Когда пишут $a=b$ для $a,b\in\mathbb{Z}_5$, то понимают под этим $a\equiv b\pmod 5$.
Когда пишут $P(x)=Q(x)$ для $a,b\in\mathbb{Z}_5[x]$, то имеют ввиду равенство коэффициентов многочленов по модулю 5 (т.е. $\psi(P)=\psi(Q)$)

PWT в сообщении #1131205 писал(а):

получался многочлен не из этого же кольца $x^2-9$ неразложим из-за девятки.

Если многочлен разложим над $\mathbb{Z}$, то он разложим над $\mathbb{Z}_5$.

[Slav-27]

PWT
Контрольный вопрос.

Какую степень имеет следующий многочлен из $\mathbb Z_7[x]$?
$0x^{17}+7x^{14}-0x^{13}+14x^{10}-11x^7+49x-22$

Запишите его в более приличном виде.

[PWT]

Цитата:

потому обычно просто пишут $x^2+1$, имея ввиду $\psi(x^2+1)$.

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

Цитата:

Если умножить два многочлена (над все тем же кольцом) $x-3$ на $x+3$ - получится многочлен над этим кольцом или как?

Тогда ответ на этот вопрос "да"?

Я вижу идею разложения над кольцом так:

1)

а) Проверяем - равенство ли $P(a)=5k,\;\;k\in \mathbb{Z}$ для $a=0,1,2,3,4$.

б) Если оказывается равенство верным для некоторого $k\in \mathbb{Z}$, то далее делим уголком на $(x-a)$ и получаем

$P(x)=(x-a)Q(x)+5k\equiv (x-a)Q(x) (\bmod 5)$

в) У многочлена $Q(x)$ степень на единицу меньше, далее проверяем $Q(x)$ аналогично и постепенно раскладываем до тех пор, пока не будет находится некоторый $k\in \mathbb{Z}$, для которого выполнено равенство из пункта $(a)$. Но как дальше тогда? Или на этот вопрос уже гораздо сложнее ответить? Правильно ли я представляю алгоритм?