Найдите число различных корней многочлена $%x^{125}-25$% в поле $%\mathbb Z_{373}$%

задан 29 Май '15 21:26

изменен 29 Май '15 21:52

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Пусть $%p$% простое, $%n$% натуральное, взаимно простое с $%p-1$%. Тогда уравнение $%x^n=a$% имеет в $%\mathbb Z_p$% в точности одно решение. Действительно, при $%a\equiv 0\pmod{p}$% это очевидно (решение только нулевое), а в противном случае $%a$% задаёт элемент мультипликативной группы $%\mathbb Z_p^{\ast}$%. Воспользуемся тем, что это циклическая группа. Она имеет образующий $%g$% (первообразный корень по модулю $%p$%). При этом $%a=g^k$% для некоторого $%k$% от $%0$% до $%p-2$%. Ясно, что $%x$% не делится на $%p$%, поэтому $%x$% также принадлежит мультипликативной группе поля, если решение имеется, и при этом $%x=g^m$% для некоторого $%m$% от $%0$% до $%p-2$%. Чтобы получилось решение, необходимо и достаточно выполнение условия $%g^{mn}=g^k$% в мультипликативной группе, а оно равносильно тому, что $%mn\equiv k\pmod{p-1}$%, поскольку порядок $%g$% равен $%p-1$%. При заданных $%n$% и $%k$% такое линейное сравнение имеет в точности одно решение относительно $%m$% при $%(n,p-1)=1$%. Из этого факта вытекает существование и единственность решения исходного сравнения относительно $%x$%, поскольку $%g^m$% подходит.

ссылка

отвечен 29 Май '15 23:28

$$x=335.$$

(29 Май '15 23:50) EdwardTurJ

@EdwardTurJ: да, я проверял на компьютере, какое именно значение корня получается. Не знаю, можно ли его получить как-то из общих соображений, использую специфику чисел из условия. Там может быть не случайно, что присутствуют 125 и 25, а также то, что 373 -- это 3x125-2. Но я не увидел, как это всё между собой связать. Единственность там следует из достаточно общих соображений.

(29 Май '15 23:58) falcao

@falcao: Я тоже пытался найти корень, учитывая специфику коэффициентов, но затем нашёл его программно.

В начале 1970-х я отправил в журнал "Квант" задачу: Для любого натурального $%a$% сравнение $%x^3\equiv a\pmod{1979}$% имеет решение. Редакция ответила, что опубликует задачу в 1979 году, если к тому времени в школе будут изучать символ Лежандра.

(30 Май '15 0:24) EdwardTurJ

@EdwardTurJ: а у Вас решение использовало какие-то элементарные средства? Скажем, малая теорема Ферма вполне могла использоваться в задачах.

(30 Май '15 0:35) falcao

@falcao: Мое решение использовало символ Лежандра.

(30 Май '15 0:40) EdwardTurJ

А разве символ Лежандра не для квадратичных вычетов?

(30 Май '15 0:52) Lyudmyla

@Lyudmyla: Символ Лежандра для квадратичных вычетов появится в процессе доказательства, при вычитании двух сравнений: $%x^3\equiv a\pmod{1979}$% и $%y^3\equiv a\pmod{1979}$%.

(30 Май '15 1:02) EdwardTurJ

@EdwardTurJ: я не знаю, как рассуждал @EdwardTurJ, но естественно рассмотреть такое решение. Достаточно доказать, что возведение в куб по модулю p=1979 инъективно. Уравнение $%x^3-y^3=0$% распадается на два, и для $%x^2+xy+y^2=0$% отсутствие ненулевых решений равносильно тому, что -3 не является квадратом по модулю p. Вручную это трудновато установить, а при помощи квадратичных символов Лежандра это делается быстро. Но это не школьное решение всё-таки.

(30 Май '15 1:03) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×310
×69

задан
29 Май '15 21:26

показан
536 раз

обновлен
30 Май '15 1:03

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

по почте:

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

по RSS:

Ответы

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

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