Особые простые числа

[Sonic86]

maxal писал(а):

Бесконечность количества простых, по модулю которых 2 - первообразный корень, недоказана, и это действительно частный случай гипотезы Артина. Но в данной задаче требуются простые, по модулю которых 2 НЕ является первообразным корнем. Бесконечность количества таких простых можно легко доказать, например, с помощью Zsigmondy Theorem.

Угу. Еще 2 не является первообразным для $p=8k \pm 1$, так как $( \frac{2}{p} ) = 1$, а простых вида $8k \pm 1$ бесконечно по т.Дирихле. Насчет тех простых, для которых 2 - первообразный, - это я просто так спросил - все равно смежный вопрос.

maxal писал(а):

Sonic86
Представьте, что делитель нуля $x$ зафиксирован и вы ищите для него подходящий со-делитель $y$, решая систему линейных уравнений по модулю 2. Матрица этой системы - циркулянт размером $p \times p$, определяемый $x$, и система будет иметь ненулевое решение, только если определитель этого циркулянта равен 0. А далее - см. по ссылке.

Как все-таки решать? Вот я взял $x$ (только я возьму $x$ с нечетным числом единиц, иначе $x_0+...+x_{p-1} \equiv 0(2)$, а значит со-делителем будет $1=(1,1,...,1)$, а этот случай мы исключаем, минор в этом случае брать не получится - он не циркулянт, так как $p$ не имеет нетривиального делителя). Беру для него $y$, строю систему, определитель у меня - циркулянт, по формуле по ссылке он равен норме алгебраического числа $x_0+...+\omega^{p-1}x_{p-1}$. Можно даже это число разделить на $x_0+...+x_{p-1}$ если охота. Я теперь должен определить, когда циркулянт сравним с 0 по модулю 2 (делится на 2), а когда нет. $2=N(1+\omega)$ если надо. А вот что дальше - ? Я ведь даже не знаю - когда 2 простое в $\mathbb{Z}[\omega]$, а когда - нет (хотя вроде как $1+\omega$ - всегда простое, но это доказывать надо). В общем - не знаю, как дальше.

maxal писал(а):

Это в точности те простые , для которых -й круговой многочлен приводим по модулю 2.
Они же простые, для которых 2 не является примитивным корнем.

Это - часть того же доказательства, которое я найти не могу, или - другого?

[maxal]

Sonic86
Детерминант циркулянта равен произведению значений многочлена $f_x(t)=x_0 + x_1 t + \dots + x_{p-1} t^{p-1}$ на множестве корней $p$-го кругового многочлена $\Phi_p(t) = 1 + t + \dots + t^{p-1}$. Он будет равен нулю по модулю 2, только если эти два многочлена имеют общие корни (в некотором расширении поля $\mathbb{Z}_2$), причем все они будут корнями многочлена $\text{НОД}(f_x(t),\Phi_p(t))$ над $\mathbb{Z}_2$. Таким образом, детерминант равен нулю по модулю 2 если и только если $\text{НОД}(f_x(t),\Phi_p(t))$ над $\mathbb{Z}_2$ является нетривиальным многочленом (делителем $\Phi_p(t)$).
В обратную сторону и того проще - если $\Phi_p(t)$ приводим над $\mathbb{Z}_2$, то есть имеет нетривиальный делитель, то можно выбрать $x$ так, чтобы $f_x(t)$ был равен этому делителю, и тогда соответствующий детерминант будет равен нулю.
Итак, делители нуля, отличные от $(1,1,\dots,1)$ (в этом случае $f_x(t)=\Phi_p(t)$), существуют тогда и только тогда, когда $\Phi_p(t)$ приводим над $\mathbb{Z}_2$.

[Sonic86]

maxal писал(а):

Таким образом, детерминант равен нулю по модулю 2 если и только если ${НОД}(f_x(t), Phi_p(t))$ над $\mathbb{Z}_2$ является нетривиальным многочленом

maxal
Скажите мне, что я в следующем не прав, тогда я больше ничего не спрошу:
Пусть я взял конкретный делитель нуля $x=(1,1,0,...,0)$, для него $f_x(t)=1+t$, у него 1 корень $t=1$ в $\mathbb{Z}_2$. $\Phi_p(1)=1 \neq 0$ в $\mathbb{Z}_2$, значит ${НОД}(f_x(t), \Phi_p(t))=1$, однако определитель будет равен 0. И это - для любого $p$.

[maxal]

Sonic86
Вы правы. Просто я в своих рассуждениях неявно предполагал (как и вы ранее), что в $x$ нечетное число 1ц (т.е. $f_x(1)=1$ в $\mathbb{Z}_2$). Именно поэтому я говорил о корнях $\Phi_p(t)$, а не $t^p-1$.

[Sonic86]

maxal
Ваше замечание я понял.
Хорошая идея с определителем. С ее помощью еще можно определить например, все числа $m: a^m=a, a=(1,1,0,...,0)$.
Попробовал я статью Motose прочесть. Интересно, что он указывает разложение $\Phi_p(x)$ сразу на неприводимые многочлены. Я вот еще не научился тут неприводимые от приводимых отличать...
Объясните мне, пожалуйста, обозначение $|\alpha|_l$ у Motose, не могу понять - что это такое. Переводится вроде как "порядок числа $\alpha$ по $l$", но что за порядок, и при чем тут $l$. Если это порядок в $Z/lZ$, то откуда он вообще берется, ведь необязательно $\alpha \in Z/lZ$, только $\alpha \in R, Z/lZ \subset R$ (в этой задаче $l=2$, а $R=Z_2[x],x:x^p=1$ и там даже $\alpha \not \in Z_2$). Если же $|\alpha|_l$ - это порядок $\alpha$ в $R^*$, то при чем тут $l$ и какая связь с $Z\lZ$ и откуда она вылазит?

[maxal]

Sonic86
$|\alpha|_{l}$ - это мультипликативный порядок элемента $\alpha$ в $R$, который для элементов базового кольца $Z/lZ$ он совпадает с порядком (или показателем) по модулю $l$. Элемент же $\alpha$ там не произвольный, а такой, что $\Phi_n(\alpha)=0$, откуда следует, что порядок $|\alpha|_{l}$ конечен и является делителем $n$.