Многочлен минимального порядка для заданных корней

[npetric]

Напишите приведенный многочлен минимальной степени с коэффициентами $a_i \in \mathbb{Z}_n$, имеющий в $\mathbb{Z}_n$ ровно n корней для
a) $n = 101
b) $n = 111 = 37*3
c) $n = 121 = 11^2$

a) Нет делителей нуля. Пользуясь теоремой Безу, выписываем многочлен
b) $\mathbb{Z}_{111} \simeq \mathbb{Z}_{37} \times \mathbb{Z}_3$
для каждого составляем свой многочлен, пользуемся КТО - получаем нужный многочлен степени 37
c) ???

Не могу с последним пунктом разобраться. Казалось, что надо выкинуть одночлены $(x-i*11), i>1$ из разложения, но для n=9 похожие рассуждения не помогли - есть приведенный многочлен степени 6 с нужным свойством. Подскажите, пожалуйста

[Aritaborian]

(Обозначения)

npetric в сообщении #1294269 писал(а):

b) $n = 111 = 37*3$

Астериск не принято использовать для обозначения умножения. При необходимости используйте \cdot и \times.

[vpb]

npetric в сообщении #1294269 писал(а):

a) Нет делителей нуля. Пользуясь теоремой Безу, выписываем многочлен
b) $\mathbb{Z}_{111} \simeq \mathbb{Z}_{37} \times \mathbb{Z}_3$
для каждого составляем свой многочлен, пользуемся КТО - получаем нужный многочлен степени 37

Каковы эти многочлены в явном виде?

[npetric]

a) $x^{101} + 100x$
b) $75x^{37}+37x^3+110x$

-- 25.02.2018, 17:18 --

Уточнение: все корни различны

[vpb]

npetric
Что-то я не понимаю. А что Вы вообще понимаете под приведенным многочленом? По моим понятиям, приведенный многочлен над конечным полем ${\mathbb F}_p$ --- это тот, который не содержит членов степени $\geq p$ (см. Боревич, Шафаревич, Теория чисел, гл.1, параграф 1). Отсюда единственный приведенный многочлен над ${\mathbb F}_p$, имеющий $p$ корней --- это нулевой многочлен. А какое определение Вы используете?

[npetric]

В книге формулировка задачи начинается так:
"Напишите приведенный многочлен $x^m + a_1 x^{m-1} + ... + a_{m-1} x + a_m$" ...
По всей видимости, имеется ввиду, что коэффициент при старшей степени должен быть единицей. Извиняюсь, что ввёл в заблуждение.

[vpb]

Ну так это другая задача. В случае простого поля многочлен $x^p-x$, а для случая б) у Вас ответ тогда неверен.

-- 25.02.2018, 16:56 --

Кстати, из какой книги задача?

[npetric]

Действительно, не обратил внимание. Значит, нужно многочлен из $\mathbb{Z}_3$ домножить, например, на многочлен $(x-1)^{34}$, чтобы при переходе в $\mathbb{Z}_{111}$ получить приведенный.

-- 25.02.2018, 17:59 --

Городенцев, Алгебра-1, задача 3.17

[vpb]

npetric в сообщении #1294316 писал(а):

Значит, нужно многочлен из $\mathbb{Z}_3$ домножить, например, на многочлен $(x-1)^{34}$, чтобы при переходе в $\mathbb{Z}_{111}$ получить приведенный.

Многочлен с коэффициентами из ${\mathbb Z}_3$ называется многочленом не из ${\mathbb Z}_3$, а над ${\mathbb Z}_3$. Если Вы имеете в виду, что надо взять многочлен $(x^3-x)(x-1)^{34}$ (над ${\mathbb Z}$) и потом рассмотреть его образ в ${\mathbb Z}_{111}[X]$, то это, конечно, будет многочлен со старшим коэффициентом $1$, но сомневаюсь, что тот, который нам нужен.

И еще. По моему, учебник Городенцева весьма хаотичен. Галопом по Европам, так сказать. Думаю, что даже продвинутым студентам НМУ в нем нелегко что-либо понять. Лучше читать Кострикина или Винберга.

-- 25.02.2018, 17:54 --

Собственно, по задаче. Подсказка: придумайте-ка некий многочлен из ${\mathbb Z}_{111}[X]$ степени 3, обращающийся в нуль при всех $x\in{\mathbb Z}_{111}$.

[npetric]

Нет, конечно же нужно будет $(x^3 - x)(x-1)^{34}$ над $\mathbb{Z}_3$ скрестить с $x^{37}-x$ над $\mathbb{Z}_{37}$ по КТО, чтобы получить нужный многочлен над $\mathbb{Z}_{111}$

Часть 3 Кострикина читал - остановился пока на представлениях групп. Захотелось почитать про кольца и поля, поэтому отвлёкся.

Про пункт с) - спасибо, буду думать

-- 25.02.2018, 19:54 --

Ваша подсказка относится к $\mathbb{Z}_{121}[X]$ ведь, верно? Над $\mathbb{Z}_{111}$ многочленов степени 3, удовлетворяющих условию, нет

[vpb]

npetric в сообщении #1294337 писал(а):

Ваша подсказка относится к $\mathbb{Z}_{121}[X]$ ведь, верно? Над $\mathbb{Z}_{111}$ многочленов степени 3, удовлетворяющих условию, нет

Нет, я имел в виду именно 111. Многочлен степени 3 такой есть, только у него старший коэффициент не единица.

npetric в сообщении #1294337 писал(а):

Захотелось почитать про кольца и поля, поэтому отвлёкся

Почитать про кольца и поля больше, чем в Кострикине --- мысль неплохая, но мое мнение о книжке Городенцева см.выше. Я сторонник классики: ван дер Варден, Кострикин, Винберг, Калужнин "Введение в общую алгебру". Отчасти Ленг.

[npetric]

Сделав то, что я сказал выше, я получил следующий многочлен:
$x^{37} + 74(x^{36} + ... + x^{29}) + 37x^{28} + 74x^{10} + 37(x^9 + ... +x^2) + 110x$

Получил я его не руками, конечно, и проверил результат так же не руками. Многочленов степени ниже 37 с нужными характеристиками нет, так как любой такой многочлен должен "проецироваться" по КТО на $\mathbb{Z}_{37}$ ($a_i \to a_i mod 37$), сохраняя свои характеристики, а $\mathbb{Z}_{37}$ - поле

Стало быть, на вопрос второго пункта я ответил. Помогите, пожалуйста, с последним

[vpb]

Многочлен у Вас получился довольно страховидный. Кроме того, задача в книжке не предполагала, несомненно, использования компьютера. Подумайте всё-таки над этим

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

Многочлен степени 3 такой есть, только у него старший коэффициент не единица

и увидите, что всё гораздо проще.

[npetric]

$x^{37}-x$ тождественно равен нулю по малой теореме Ферма над $\mathbb{Z}_3$, и над $\mathbb{Z}_{37}$ у него каждый элемент поля является корнем - поэтому над $\mathbb{Z}_{111} \simeq \mathbb {Z}_{37} \times \mathbb{Z}_3 $ у него каждый элемент поля также будет корнем

[vpb]

npetric,
очень хорошо! (Еще даже лучше, чем я придумал. Я вообще имел в виду рассмотреть два многочлена $37(x^3-x)$ и
$3(x^{37}-x)$, и потом уже из них скомбинировать что надо, а что $x^{37}-x$ сам по себе подходит, не заметил).
Со $121$ вопрос так решается: многочлен это $(x^{11}-x)^2$ (почему он подходит?), а что минимальная степень --- это действительно $22$, доказывать довольно сложно (я сам не доказал, мне рассказал один умный человек, так что и Вы про это лучше не думайте).