Пусть $%\mathbb F_{p^n}$% - поле разложения $%x^{p^n}-x\in \mathbb F_p[x]$%. Доказать, что 3 утверждения эквивалентны:

  1. $%k$% делит $%n$%
  2. $%p^k-1$% делит $%p^n-1$%
  3. $%\mathbb F_{p^k}\subset \mathbb F_{p^n}$%

Эквивалентность 1 и 3 есть в учебниках, а с 2 как быть?

задан 21 Июн 7:38

Это отдельный теоретико-числовой факт. Легко доказывается (при помощи алгоритма Евклида), что НОД(x^m-1,x^n-1)=x^d-1, где d=НОД(m,n). Можно ещё так: если k=nq+r (деление с остатком), то p^n=1(mod p^n-1), откуда p^k=p^r по тому же модулю. Тогда p^r-1 делится на p^n-1, где 0<=r < n, откуда r=0.

(21 Июн 13:13) falcao

А как в общем случае доказать НОД(x^m-1,x^n-1)=x^d-1?

Если применять алгоритм Евклида, получается (x^n-1,x^k-1)=(x^k-1,x^{n-k}-1)=(x^{n-k}-1,x^{2k-n}-1)=(x^{2k-n}-1,x^{2n-3k}-1)=... но где и как останавливаться?

(21 Июн 19:08) Slater

@Slater: достаточно одного шага алгоритма. От пары m,n при m>=n мы переходим к паре (m-n,n). Такой алгоритм работает медленнее обычного, но ведёт к этому же итогу, и в теории за ним проще следить. Останавливается всё тогда, тогда одно из чисел обнуляется. Тогда второе будет ответом.

(21 Июн 19:21) falcao

Ну остановились мы на (m-n, n). Когда-то одно обнулится, из всего этого пока не видно, что НОД(x^m-1,x^n-1)=x^d-1

(21 Июн 19:40) Slater

@Slater: а зачем это видеть? Важно знать, каков очередной шаг алгоритма, и каков признак остановки. Также надо быть уверенным, что процедура оканчивается за конечное время. Здесь достаточно заметить только то, что оба алгоритма работают параллельно. Если от (m,n) мы перешли к (m-n,n) для чисел, то от многочленов x^m-1, x^n-1 мы перейдём к x^{m-n}-1 и x^n-1. Последнее очевидно, если заметить, что x^{m-n}(x^n-1)=x^m-x^{m-n}, что мы вычитаем из первого многочлена. Это единственный содержательный момент во всей процедуре. И вообще, это всё относится к курсу элементарной математики.

(21 Июн 19:47) falcao

Я что-то не до конца понимаю импликацию 2=>3. Если p^k-1 делит p^n-1, то у мультипликативной группы поля порядка p^n есть элемент порядка p^k-1. Как это использовать?

(8 Авг 0:32) Slater

@Slater: здесь нужно использовать теорию. Тот факт, что если k|n, то поле порядка p^n содержит подполе порядка p^k, вообще говоря, не очевиден. Способы доказательства могут зависеть от порядка изложения теоретических фактов.

(8 Авг 10:25) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×3,769

задан
21 Июн 7:38

показан
117 раз

обновлен
8 Авг 10:25

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

по почте:

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

по RSS:

Ответы

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

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