Поля остатков: пара вопросов начинающего

[Munin]

Рассматриваю поля остатков по модулю простых чисел $\mathbb{Z}_p.$ Интересуюсь конкретными примерами.
Возникли два таких вопроса:
1) всегда ли можно решить в таком поле (а) квадратное, (б) полиномиальное уравнение, и как его расширить, чтобы можно было?
2) как насчёт уравнения типа $\sqrt{x}+\sqrt{x+1}=a$? Я тут выяснил, что оно легко сводится к квадратному, но в обычных числах.
Эти вопросы я задаю самому себе, и дальше такой поток мыслей (вопросы к окружающим - выделены жирным шрифтом).

Например, беру $\mathbb{Z}_5.$ Его таблица умножения такая:

$\begin{array}{|c||c|c|c|c|c|} \hline \cdot&0&1&2&3&4 \\ \hline \hline 0&0&0&0&0&0 \\ \hline 1&0&1&2&3&4 \\ \hline 2&0&2&4&1&3 \\ \hline 3&0&3&1&4&2 \\ \hline 4&0&4&3&2&1 \\ \hline \end{array}$

Вижу, что квадратами являются только числа (0,) 1 и 4, то есть, $\sqrt{2},\sqrt{3}\notin\mathbb{Z}_5.$

Добавляю $\sqrt{2},$ и соответственно, все линейные комбинации (все произведения выразимы в получившемся $\mathbb{Z}_5[\sqrt{2}],$ и даже все частные: в знаменателе можно избавиться от иррациональности). Получается двумерное векторное пространство, в котором $5^2=25$ элементов.
Можно ли в этом $\mathbb{Z}_5[\sqrt{2}]$ извлечь корень из 3?
Обозначим за $r$ корень многочлена $x^2-2.$ Тогда все элементы $\mathbb{Z}_5[\sqrt{2}]$ имеют вид $a+br\quad (a,b\in\mathbb{Z}_5).$ Посмотрим на их квадраты:

$(a+br)^2=a^2+2b^2+2abr.$

Чтобы получившееся число было $\in\mathbb{Z}_5,$ надо, чтобы $2ab=0.$

Правильно ли я понимаю, что в полях делителей нуля нет? Если бы были, то $ab=0\quad\Rightarrow$     $a^{-1}ab=a^{-1}0\quad\Rightarrow$     $b=0.$
Правильно ли я понимаю, что $ab=0\quad\Longleftrightarrow\quad (a=0\quad\vee\quad b=0)$?

Таким образом, имеем два случая: $b=0$ и $a=0.$
Случай $b=0$ мы уже знаем: это "действительные" числа, и их квадратами могут быть только 0, 1 или 4.
Случай $a=0$:     $(a+br)^2=2b^2,$ то есть, $2\cdot\{0,1,4\}=\{0,2,3\}.$
Ура! В этом поле корень из 3 извлекается!
А извлекается ли корень из любого элемента? Как это проверить, не перебирая вручную все 25?

Каковы квадраты в других полях остатков?

$\begin{array}{|c||r|r|r|r|r|r|r|r|r|r|r|r|r|l|} \hline (x^2)&0&1&2&3&4&5&6&7&8&9&10&11&12&\textit{охвачены} \\ \hline \hline \mathbb{Z}_2&0&1&&&&&&&&&&&&\underline{0},\underline{1} \\ \hline \mathbb{Z}_3&0&1&1&&&&&&&&&&&\underline{0},\underline{1},\mathit{2} \\ \hline \mathbb{Z}_5&0&1&4&4&1&&&&&&&&&\underline{0},\underline{1},\mathit{2},\mathit{3},\underline{4} \\ \hline \mathbb{Z}_7&0&1&4&2&2&4&1&&&&&&&\underline{0},\underline{1},\underline{2},\mathit{3},\underline{4},\mathit{5},\mathit{6} \\ \hline \mathbb{Z}_{11}&0&1&4&9&5&3&3&5&9&4&1&&&\underline{0},\underline{1},\mathit{2},\underline{3},\underline{4},\underline{5},\mathit{6},\mathit{7},\mathit{8},\underline{9},\mathit{10} \\ \hline \mathbb{Z}_{13}&0&1&4&9&3&12&10&10&12&3&9&4&1&\underline{0},\underline{1},\mathit{2},\underline{3},\underline{4},\mathit{5},\mathit{6},\mathit{7},\mathit{8},\underline{9},\underline{10},\mathit{11},\underline{12} \\ \hline \end{array}$

Наблюдаем интересную картину: в квадраты попадает половина (ненулевых) остатков (исключением является $\mathbb{Z}_2,$ но оно малоинтересно, отброшу его в дальнейшем). Проверим это:
1) Не больше половины. Это очевидно: $(-x)^2=x^2,$ так что все противоположные элементы дают тот же квадрат. А противоположных ненулевых остатков ровно половина ($p$ нечётное).
2) Не меньше половины. Вот это интересно. Допустим, квадраты совпадают: $x^2=a^2.$ Тогда

$x^2-a^2=0$
$(x-a)(x+a)=0$

и мы имеем два случая: либо $x=a,$ либо $x=-a.$
Однако верно ли это? Возможный пробел я вижу в таком месте: многочлен $x^2-a^2$ может раскладываться на множители более чем одним способом... Возможно ли это в полях? В полях остатков? (По сути, я вообще ничего не доказал, а переформулировал вопрос в эквивалентный, и по-прежнему не знаю на него ответа.)

Если неквадратов половина, то верно ли, что мы можем научиться извлекать корни из любого "действительного" числа, добавив только корень из одного такого числа? Кажется верным. Пусть ниже $r^2=a$ для некоторого $a,$ не являющегося квадратом. Тогда мы имеем даже "на мнимой оси" все числа вида $br,$ а их квадраты имеют вид $b^2r^2=ab^2.$ Достаточно, чтобы они не совпали с квадратом никакого третьего числа $c,$ чтобы тогда они заполнили всю половину неквадратов.
$ab^2-c^2=0$
$(br-c)(br+c)=0,$
однако я снова упираюсь в вопрос: можно ли смело раскладывать разность квадратов на множители, или это не равносильное преобразование в полях?

----------------

Попробую извлечь корень 3-й степени из "действительного числа" в $\mathbb{Z}_5[\sqrt{2}].$

$(a+br)^3=a^3+2b^3r+3a^2br+6ab^2(=1ab^2)$

Для действительности нужно

$b(2b^2+3a^2)=0$
$2b^2=2a^2\quad b^2=a^2\quad b=\pm a.$

Вроде, у нас получилось 3 кандидата, как и в $\mathbb{C}.$ Но я ещё не проверил действительную часть. И ещё:
Нет ли ещё других решений?

Уф, вопросы пока всё.

[arseniiv]

Munin в сообщении #1204695 писал(а):

Правильно ли я понимаю, что в полях делителей нуля нет? Если бы были, то $ab=0\quad\Rightarrow$ $a^{-1}ab=a^{-1}0\quad\Rightarrow$ $b=0.$
Правильно ли я понимаю, что $ab=0\quad\Longleftrightarrow\quad (a=0\quad\vee\quad b=0)$?

Да. Более общо, это выполняется для целостных колец (второе — как раз требование, предъявляемое к таким кольцам). И оно как раз и означает, что делителей нуля нет.

[Munin]

А поля $\subset$ целостные кольца. (Не забывайте этого добавлять, а то я всей системы понятий не знаю, она слишком большая пока для моей головы.)

[AV_77]

Munin в сообщении #1204695 писал(а):

А извлекается ли корень из любого элемента?

В расширении поля $\mathbb{Z}_p$, полученном присоединением корня уравнения $x^2 = a$, где $a$ не является квадратичным вычетом, разрешимы все уравнения такого вида для любого $a \in \mathbb{Z}_p$.

Munin в сообщении #1204695 писал(а):

Однако верно ли это?

Верно. Над любым полем многочлен степени $n$ не может иметь более $n$ корней.

Munin в сообщении #1204695 писал(а):

можно ли смело раскладывать разность квадратов на множители, или это не равносильное преобразование в полях?

Можно. И не только над полями, но и над любыми коммутативными кольцами.

[Munin]

AV_77 в сообщении #1204714 писал(а):

Верно. Над любым полем многочлен степени $n$ не может иметь более $n$ корней.

А меня пугали, что скажем, квадратных корней может быть много... Это в кольцах?

AV_77 в сообщении #1204714 писал(а):

В расширении поля $\mathbb{Z}_p$, полученном присоединением корня уравнения $x^2 = a$, где $a$ не является квадратичным вычетом, разрешимы все уравнения такого вида для любого $a \in \mathbb{Z}_p$.

AV_77 в сообщении #1204714 писал(а):

Верно. Над любым полем многочлен степени $n$ не может иметь более $n$ корней.

AV_77 в сообщении #1204714 писал(а):

Можно. И не только над полями, но и над любыми коммутативными кольцами.

Сложные ли это утверждения? Если нет, то можно узнать доказательство? Если да, то отсылку к литературе (достаточно простой)?

[AV_77]

Munin в сообщении #1204727 писал(а):

Это в кольцах?

В кольцах с делителями нуля. Например, в $\mathbb{Z}_{16}$ у уравнения $x^2 = 0$ есть 4 корня.

Munin в сообщении #1204727 писал(а):

Сложные ли это утверждения? Если нет, то можно узнать доказательство? Если да, то отсылку к литературе (достаточно простой)?

В принципе, не сложные. Классическая литература - Р. Лидл и Г. Нидеррайтер. Конечные поля.

Первое утверждение сразу следует из того, что, с точностью до изоморфизма, все конечные поля одного порядка изоморфны, то есть их можно считать одним и тем же полем. В частности, все квадратичные расширения дают одно и то же поле.
Утверждение про корни многочленов получается как следствие того, что кольцо многочленов над полем целостное.
Ну а последнее - это легко проверяемое в коммутативном кольце равенство $(a-b)(a+b) = aa + ab - ba - bb = a^2 - b^2$.

[Munin]

А, понял! То есть, $(a-b)(a+b)=a^2-b^2$ верно всегда, а вот уже переход к $a-b\quad\vee\quad a+b$ требует целостности?
Спасибо!

А Лидл, Нидеррайтер - сложный? (В Википедии видел на него ссылки.) Или какого-нибудь Кострикина лучше для начала поискать? (Если да, какую главу?)

[AV_77]

Munin в сообщении #1204735 писал(а):

А, понял! То есть, $(a-b)(a+b)=a^2-b^2$ верно всегда, а вот уже переход к $a-b\quad\vee\quad a+b$ требует целостности?

Да. В коммутативном кольце.

Munin в сообщении #1204735 писал(а):

А Лидл, Нидеррайтер - сложный?

Ну, как сказать... умеренный :) Попробуйте посмотреть. Если интересуют только основы теории конечных полей, то это первые две главы, точнее первая глава - введение необходимых понятий типа группы, кольца, поля и их основные свойства. Дальше идут уже специальные вопросы про свойства многочленов, характеры, линейные рекуррентные последовательности и т.д.

Есть еще книжка Mullen, Finite Fields. Она более современная, но я ее не видел, только отрывки.

[Munin]

Суровые вы люди :-) Ладно, пойду в Лидла...

[Sonic86]

Munin в сообщении #1204735 писал(а):

А Лидл, Нидеррайтер - сложный? (В Википедии видел на него ссылки.)

Мне был трудноват, м.б. Вам легче будет.

Munin в сообщении #1204695 писал(а):

1) всегда ли можно решить в таком поле (а) квадратное, (б) полиномиальное уравнение, и как его расширить, чтобы можно было?

Не всегда, зависит от уравнения. Расширять поле корнем многочлена - стандартно.

Munin в сообщении #1204695 писал(а):

2) как насчёт уравнения типа $\sqrt{x}+\sqrt{x+1}=a$? Я тут выяснил, что оно легко сводится к квадратному, но в обычных числах.

Да примерно так же и решается.

Munin в сообщении #1204695 писал(а):

А извлекается ли корень из любого элемента? Как это проверить, не перебирая вручную все 25?

Не из любого. Проверять, извлекается ли - например с помощью критерия Эйлера: $(\exists x)x^2\equiv a \pmod p \Leftrightarrow a^{\frac{p-1}{2}}\equiv 1\pmod p$. Или с помощью символа Лежандра.

Вообще извлечение корня степени $k$ в каком-то смысле просто: мультипликативная группа конечного поля $\mathbb{Z}_p^\times$ (и даже $\mathbb{F}_{p^n}^\times$) циклична, т.е. существует $g: \mathbb{F}_{p^n}^\times=\{g^0, ..., g^{p^n-1}\}$, ее порядок $p^n-1$. И дальше просто: если $k \mid p^n-1$, то корень извлекается - их ровно $k$ штук (как и в любой цикличной группе), иначе - не извлекается. И сами решения через образующую довольно легко выписываются.

[Munin]

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

Мне был трудноват, м.б. Вам легче будет.

Да вы все издеваетесь??? У меня мозги уже заскорузлые, мне что попроще бы! Сразу же сказал! Мой уровень - научно-популярные лекции Савватеева на YouTube.

[vpb]

Дозвольте и мне слово молвить...
Лидл-Нидеррайтер --- никоим образом не учебник, а справочник-монография по специальным вопросам. Первые две главы там --- это контрольный список, checklist, для освежения памяти, для тех, кто уже раньше проходил общий курс алгебры. Предназначен, как я представляю, в значительной степени для дискретчиков-криптографов (но и для некоторых математиков тоже). Как введение же в общие понятия о группах-кольцах-полях, по моему, очень хороши первые три главы ван дер Вардена. Во всяком случае, почему разложение на неприводимые многочлены для многочленов от одной переменной над полем однозначно, я именно оттуда узнал (И кое-что еще из ван дер Вардена хорошо, но далеко не всё).

-- 30.03.2017, 14:35 --

ЗЫ. Ну, вдВ это и есть попроще, имхо.

[Munin]

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

И дальше просто: если $k \mid p^n-1$, то корень извлекается

Что-то я не понял. Вот у меня $\mathbb{Z}_5,$ квадратный корень, я проверяю $2\mid 5-1,$ выполняется, и получаю, что корень должен извлекаться. Но из 1 и 4 он извлекается, а из 2 и 3 - нет.

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

Не из любого.

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

Ах да. Ведь возведение в квадрат - не инъекция! :-(

-- 30.03.2017 15:36:51 --

vpb в сообщении #1204891 писал(а):

Как введение же в общие понятия о группах-кольцах-полях, по моему, очень хороши первые три главы ван дер Вардена.
ЗЫ. Ну, вдВ это и есть попроще, имхо.

Спасибо большое!
Алгебра, надеюсь?

[kp9r4d]

Если $k= \mathbb{F}_q$ конечное поле характеристики $\neq 2$, то $f: k^{\times} \to k^{\times}$ $f(x)=x^2$ - это гомоморфизм групп, его ядро имеет размер два $\operatorname{Ker}(f) = \{1,-1\}$, поэтому в поле $k$ есть ровно $| k^{\times}/\operatorname{Ker}(f)|=(q-1)/2$ квадратичных вычетов. Отсюда - требуемого конечного поля нету.

Чтобы проверить является ли $a$ квадратичным вычетом в $\mathbb{Z}_p$ есть эффективный вычислительный алгоритм - вычисление символа Якоби.

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

[vpb]

Ну вот, например, почему многочлен, с коэффициентами из поля, не может иметь больше корней, чем его степень. Давайте, чтоб голову не морочить, считать, что поле --- это ${\mathbb C}$. Прежде всего, если $f(X)\in {\mathbb C}[X]$ --- многочлен, а $x_1$ --- его корень, то $f(X)$ делится на $X-x_1$, т.е. существует многочлен $f_1(X)$ такой, что $f(X)=f_1(X)(X-x_1)$. В самом деле, $f$ можно разделить на $X-x_1$ с остатком в столбик, получим что $f(X)=f_1(X)(X-x_1)+r$, где $r\in {\mathbb C}$. Подставим в правую и левую части $X=x_1$. Слева нуль получится, а справа первое слагаемое нуль, а второе $r$. Значит на самом деле $r=0$, т.е. делится нацело.
Теперь допустим, что степень $f(X)$ равна $n$, а $X=x_1$ --- корень. Тогда $f(X)=f_1(X)(X-x_1)$, а степень $f_1(X)$ есть $n-1$ . Если $X=x$ --- корень для $f(X)$, отличный от
$x_1$, то $x-x_1\ne0$, значит $f_1(x)=0$. Но таких $x$ есть не более чем $n-1$ штук (предположение индукции). Ну, значит, у $f(X)$ --- не более $n$ (а именно, $x_1$ и еще корни для $f_1(X)$, числом не более $n-1$).