Пусть мне дан многочлен над Z_2, скажем $$f(x) = x^4 + x + 1$$ Я хочу найти такой натуральный n, чтобы f(x) являлся делителем многочлена x^n + 1.

Учитель дал мне наводку, что здесь можно воспользоваться фактом, что элементы конечного поля из q = p^n элементов есть в сущности корни многочлена x^q - x.

Вроде бы я нашел такой n, построив поле

$${Z_2}/{(f(x))} \simeq F_{16}$$ И положив n = 15, получил f(x) делит x^15 + 1. Но если честно, я не понимаю что здесь произошло.

Более того, как мне действовать, чтобы найти такой n для многочлена $$g(x) = (x^4 + x + 1)(x^3 + x + 1) ?$$

задан 12 Фев 16:04

Как это можно объяснить ?

(12 Фев 23:35) ЖанВаль
10|600 символов нужно символов осталось
1

Пусть многочлен $%f(x)$% неприводим над полем $%F=\mathbb Z_2$%. Тогда факторкольцо $%F[x]/(f(x))$% по главному идеалу является полем. Если степень многочлена равна $%n$%, то поле состоит из $%2^n$% элементов. Порядок мультипликативной группы равен $%2^n-1$%, поэтому $%x^{2^n-1}=1$% для любого элемента поля кроме нуля. Отсюда следует, что любой элемент поля удовлетворяет уравнению $%x^{2^n}-x=0$%. Из теоремы Безу следует, что многочлен раскладывается на линейные множители над этим полем. То есть корни этого многочлена -- в точности все элементы поля.

Рассмотрим НОД многочленов $%f(x)$% и $%x^{2^n}-x$% над основным полем. Он делит $%f(x)$%, и ввиду неприводимости, НОД равен 1 или $%f(x)$%. Первый случай невозможен, так как $%f(x)$% имеет корень в расширении поля (это класс вычетов многочлена $%x$%). Значит, $%x(x^{2^n-1}-1)$% делится на $%f(x)$%, а потому $%f(x)$% делит $%x^{2^n-1}-1$%. В нашем случае $%x^4+x+1$% делит $%x^{15}+1$% ("минус" и "плюс" для поля характеристики 2 -- одно и то же).

Этот факт можно сформулировать в виде олимпиадной задачи (она где-то предлагалась). Есть бесконечная линия из лампочек, на них можно одновременно нажимать при помощи "расчёски" с выломанными зубцами. В нашем случае это будут лампочки под номерами $%n$%, $%n+1$%, $%n+4$%. Изначально ни одна лампочка не горит; надо доказать, что после нескольких нажатий можно зажечь ровно 2 лампочки. В этом легко непосредственно убедиться, делая следующее. Сначала зажигаем лампочки с номерами 0, 1, 4. Далее левым краем "расчёски" касаемся лампочки 1, меняя статус лампочек 1, 2, 5. После этого у нас горят номера 0, 2, 4, 5. Лампочку 0 не трогаем, и начинаем с лампочки 2, меняя статус лампочек 2, 3, 6. И так далее. Это однозначный процесс, в ходе которого мы зажжём 0 и 15, в чём можно убедиться, делая рисунки.

По поводу $%g(x)$%: это произведение двух неприводимых над $%F$% многочленов, первый из которых делит $%x^{15}-1$%, а второй $%x^7-1$%. Ввиду того, что $%x^{mn}-1$% всегда делится на $%x^m-1$%, получаем, что $%x^{105}-1$% делится на оба многочлена, а потому и на их произведение, так как они неприводимы и различны.

ссылка

отвечен 13 Фев 0:43

а что Вы называете «основным полем» во втором абзаце?

(13 Фев 17:46) ЖанВаль

@ЖанВаль: поле $%F=\mathbb Z_2$%.

(13 Фев 18:39) falcao

Большое спасибо!

(13 Фев 23:28) ЖанВаль
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,496
×412
×151
×22

задан
12 Фев 16:04

показан
158 раз

обновлен
13 Фев 23:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru