Пусть $%p>3$% и p простое. Докажите, что если разрешимо сравнение $%x^2+x+1=0$% по модулю p то p сравнимо с 1 по модулю 6

задан 9 Июл '13 17:41

изменен 9 Июл '13 23:30

Deleted's gravatar image


126

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

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

Прежде всего, из условия следует, что число $%(2x+1)^2+3=4(x^2+x+1)$% делится на $%p$%. Это значит, что $%-3$% является квадратом по модулю $%p$%. Тогда, если его возвести в степень $%(p-1)/2$%, то оно будет сравнимо с $%(2x+1)^{p-1}$% по модулю $%p$%, то есть будет сравнимо с единицей ввиду малой теоремы Ферма. (Здесь $%2x+1$% не делится на $%p$%, так как $%p > 3$%.)

Теперь будем рассуждать от противного. Допустим, что $%p$% не сравнимо с 1 по модулю 6. Из условия известно, что $%p$% нечётно, поэтому при делении на 6 оно даёт нечётный остаток. Это 1, 3 или 5. Первое противоречит предположению, а второе невозможно, так как $%p$% не кратно трём. Остаётся третий случай, и можно записать $%p=6m-1$% для некоторого натурального $%m$%. Если мы докажем, что при этих условиях $%(-3)^{\frac{p-1}2}$% сравнимо с $%-1$% по модулю $%p$%, то этим будет установлено противоречие, так как выше было сказано, что $%(-3)^{\frac{p-1}2}$% сравнимо с $%1$% по модулю $%p$%.

Всякое число, не делящееся на $%p$%, сравнимо с одним и только одним из чисел списка $%\pm1$%, $%\pm2$%, ..., $%\pm\,\frac{p-1}2$%. Рассмотрим список чисел от $%1$% до $%\frac{p-1}2=3m-1$%. Их произведение равно $%(3m-1)!$%. Домножим каждое из этих чисел на $%-3$%. Тогда у полученных чисел произведение будет равно $%(-3)^{\frac{p-1}2}(3m-1)!$%. Ясно, что среди рассматриваемых чисел нет таких, которые делились бы на $%p$%, поэтому каждое из них сравнимо с одним из чисел списка, рассмотренного в начале абзаца. Посмотрим, с какими именно. Напомним, что список имеет вид $%\pm1$%, $%\pm2$%, ..., $%\pm(3m-1)$%.

При домножении на $%-3$% чисел от $%1$% до $%m-1$% мы получим числа $%-3$%, $%-6$%, ..., $%-(3m-3)$%, что находится в пределах списка. Следующее число будет равно $%-3m$%, и по модулю $%p=6m-1$% оно сравнимо с числом $%3m-1$% из списка. Затем следует $%-3m-3$%, что сравнимо с $%3m-4$% по модулю $%p$%, и так далее. Числу $%2m-1$% (до домножения) будет соответствовать $%-6m+3$% после домножения, что сравнимо с $%2$% по модулю $%p$%.

Следующее число $%2m$% превращается в $%-6m$% и заменяется на $%-1$% из списка. Числу $%2m+1$% соответствует $%-6m-3$%, заменяемое на $%-4$%, и так далее. Получаются числа списка $%-1$%, $%-4$%, ... с уменьшением на $%-3$%, и для самого последнего числа $%3m-1$% после домножения получится $%-9m+3$%, что сравнимо по модулю $%p$% с $%-(3m-2)$%.

Таким образом, после домножения каждого из чисел от $%1$% до $%3m-1$% на $%-3$% и последующей замены сравнимым по модулю $%p$% числом получился такой список: $$-3,-6,\ldots,-(3m-3);3m-1,3m-4,\ldots,2;-1,-4,\ldots,-(3m-2).$$ Здесь присутствуют по разу все числа от $%1$% до $%3m-1$%, часть из которых взята со знаком минус. Поэтому произведение всех этих чисел равно $%(-1)^s(3m-1)!$%, где $%s$% -- количество минусов. Это количество нетрудно подсчитать. До первой точки с запятой у нас идёт $%m-1$% число, далее $%m$% чисел до следующей точки с запятой, и в конце ещё $%m$% чисел. Знак минус наличествует у $%s=2m-1$% числа, поэтому $%(-1)^s=-1$%.

Таким образом, у нас после домножения чисел на $%-3$% было произведение $%(-3)^{\frac{p-1}2}(3m-1)!$%. После замены чисел сравнимыми по модулю $%p$% получилось произведение $%(-1)^s(3m-1)!=-(3m-1)!$%. Значит, разность одного и другого произведения делится на $%p$%. На $%(3m-1)!$% можно сократить, так как $%p=6m-1$% простое, и на него ни одно из чисел от $%1$% до $%3m-1$% не делится. Тогда мы приходим к тому, что разность $%(-3)^{\frac{p-1}2}-(-1)$% делится на $%p$%, то есть $%(-3)^{\frac{p-1}2}$% сравнимо с $%-1$% по модулю $%p$%, что завершает доказательство.

ссылка

отвечен 9 Июл '13 23:44

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

Имеем $%x^3+x^2+x=0, x^3=1$%Значит, порядок по умножению x равен3. Значит, 3 делит порядок группы $%\mathbb{Z}_p$% без 0 по умножению, то есть р-1 делится на 3 и так как оно четно, оно делится на 6 и р дает остаток 1 при делении на 6

ссылка

отвечен 9 Июл '13 22:35

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×586
×512

задан
9 Июл '13 17:41

показан
799 раз

обновлен
9 Июл '13 23:44

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

по почте:

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

по RSS:

Ответы

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

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