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

[Sonic86]

Пусть $n$ - натуральное. Определим в $Z_2^n$ операцию умножения:
$z=x \cdot y \Leftrightarrow z_k=\sum\limits_{k=i+j}x_iy_j$
(в $k=i+j$ сложение по модулю $n$).
Назовем простое число $p$ особым $\Leftrightarrow$ в $Z_2^p$ существуют делители нуля, отличные от $(1,1,...,1)$.
Найти все особые простые числа.

Решение задачи мне неизвестно, буду рад хотя бы литературе или подсказкам.

[maxal]

Это в точности те простые $p$, для которых $p$-й круговой многочлен $x^{p-1}+x^{p-2}+\dots+1$ приводим по модулю 2.
Они же простые, для которых 2 не является примитивным корнем.

Последовательность этих простых начинается так:
7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89, 97, ...

Добавлено спустя 3 минуты 29 секунд:

Подсказка:
http://mathworld.wolfram.com/CirculantDeterminant.html

[Sonic86]

maxal писал(а):

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

Последовательность этих простых начинается так:
7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89, 97, ...

Добавлено спустя 3 минуты 29 секунд:

Подсказка:
http://mathworld.wolfram.com/CirculantDeterminant.html

Огромное спасибо! Я оказывается очень сильно тормозил. Вы меня из ступора вывели.
Наверное и без подсказки можно: раскладываем круговой многочлен на множители и перегруппировываем их с $1-x$.

[Sonic86]

Блин, все равно не понял почему
Откуда это утверждение берется?

[maxal]

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

[incvezitor]

помнится мне что этим вопросом занимался Фёдоров

[Sonic86]

incvezitor писал(а):

помнится мне что этим вопросом занимался Фёдоров

А он кто? (извините я не знаю)

[maxal]

maxal в сообщении #211706 писал(а):

Это в точности те простые $p$, для которых $p$-й круговой многочлен $x^{p-1}+x^{p-2}+\dots+1$ приводим по модулю 2.
Они же простые, для которых 2 не является примитивным корнем.

По этому поводу можно сказать чуть больше - см. Theorem 3 в статье
On values of cyclotomic polynomials. V

[Sonic86]

maxal
Спасибо еще раз за утверждение, но Ваше доказательство его мне недоступно. Я попытался, но теорию алгебраических чисел знаю плохо. Но теперь мне хочется описать все подкольца и их взаимоотношения, может быть Вы приведете свое доказательство.

У меня получилось без формулы для циркулянта, проверьте пожалуйста.
Рассмотрим еще операцию сложения векторов $+$ покомпонентно по модулю 2. Пусть $x$ - делитель нуля, тогда все числа из $xZ_2^p$ - делители нуля. $xZ_2^p$ - конечное подкольцо $Z_2^p$, значит в нем есть базис, значит оно изоморфно $Z_2^k,k<p$, значит $|xZ_2^p|=2^k$. У любого кольца $xZ_2^p$ $\{ 0 \}$ - его подкольцо ($0=(0,0,...,0)$).
Пусть $x$ делитель нуля, отличный от $0$ и $1=(1,1,...,1)$, тогда все его $p$ циклических сдвигов различны. Кроме того, $xZ_2^p$ содержит $0$, может содержать $1$, а может и не содержать $1$, а остальные вектора группируем в классы циклически эквивалентных можностью $p$, тогда $|xZ_2^p|=qp+1;2$.
Отсюда $qp+1;2=2^k \Leftrightarrow 2^k \equiv 1;2 (p)$. Для нетривиального $x$ (то есть отличного от $0;1$) будет $k>1$, так как для $k=0$ имеем $\{ 0 \}$, а для $k=1$ имеем $\{ 0;1 \}$. Если $2$ - первообразный по $p$, то $2^k \equiv 1;2 (p) \Leftrightarrow k \equiv 0;1 (p-1)$. Случай $k=0;1$ мы уже исключили. $k=p$ невозможен, иначе $(1,0,...,0)$ - делитель нуля. Случай $k=p-1$ соответствует $aZ_2^p$, где $a=(1,1,0,...,0)$. Но единственный соделитель нуля для делителя $a$ есть $1$ (это можно найти из упомянутой Вами системы уравнений по модулю 2, например).
Таким образом, если $2$ - первообразный по $p$, то нетривиальных делителей нуля нету.
Если $2$ - не первообразный, то $\{ 2; 2^2; ... ; 2^{p-1} \} = \{ c_1; c_2; ... ; c_m \} =С$ - нетривиальная подгруппа $Z_p$, тогда вектор $b$, в котором 0-я и $c_j$-ые компоненты равны 1, а остальные равны 0 будет идемпотент: $b^2=b$ (так как $2C=C$) (число единиц в $b$ нечетно), а множество его циклических сдвигов составляет группу по умножению, где $b$ - единица по умножению (хотя это не нужно). $b$ - делитель нуля, так как $b^2=b \Leftrightarrow b(b-e)=0$, но $b \neq e$ ($e=(1,0,...,0)$).

P.S. "Существует бесконечно много простых $p$, для которых 2 - первообразный корень" - это доказано? Или это - только гипотеза Артина для $a=2$?
Theorem 3 сейчас посмотрю.
(обалдеть какое оформление! )

[Iosif1]

maxal писал(а):

Последовательность этих простых начинается так:
7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89, 97, ...

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

[maxal]

Sonic86 писал(а):

У меня получилось без формулы для циркулянта, проверьте пожалуйста.
...
P.S. "Существует бесконечно много простых $p$, для которых 2 - первообразный корень" - это доказано? Или это - только гипотеза Артина для $a=2$?

Доказательство похоже на правду, хотя оно и сложнее чем то, что я предложил выше.

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

[maxal]

Iosif1 писал(а):

maxal писал(а):

Последовательность этих простых начинается так:
7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89, 97, ...

И что уже установлено, что этот числовой ряд простых чисел не даёт сбоев ?

Не знаю, что в данном случае "сбой". Но указанный ряд простых чисел дает решение исходной задачи.

[Iosif1]

Я имею ввиду, что построение чисел по применяемому алгоритму всегда приводит к успеху -получению простого числа?

[maxal]

Iosif1 писал(а):

Я имею ввиду, что построение чисел по применяемому алгоритму всегда приводит к успеху -получению простого числа?

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

[Iosif1]

maxal в сообщении #212830 писал(а):

Каждый элемент этого ряда является простым числом по определению.

Ничего себе, третий класс! Это даже не седьмой!! Спасибо!!!