Помогите пожалуйста решить сравнение.

alt text

задан 18 Дек '14 6:51

Аналогичный пример - math.hashcode.ru/questions/46213/

(18 Дек '14 11:36) EdwardTurJ

Что-то у меня не получается решить таким же образом мое сравнение. Там на первом же шаге не получается...

(18 Дек '14 13:59) Andrew
10|600 символов нужно символов осталось
0

Ясно, что $%x$% нечётно; положим $%x=2y+1$% и подставим в сравнение. Оно после упрощений полностью сократится на 4, и получится $%y^2+y\equiv58\pmod{2^6}$%. Отсюда следует, что ни $%y$%, ни $%y+1$% не делится на 4, то есть остаток от деления $%y$% на 4 равен 1 или 2. Разбираем два случая.

1) $%y=4z+1$%; получается $%(4z+1)(2z+1)\equiv29\pmod{32}$%, и далее $%8z^2+6z\equiv28\pmod{32}$%, то есть $%4z^2+3z\equiv14\pmod{16}$%. Значит, $%z$% чётно и не делится на 4, то есть $%z=4t+2$%. После подстановки и упрощений это даёт $%t\equiv2\pmod4$%. Полагая $%t=4k+2$%, далее находим $%z=16k+10$%, $%y=64k+41$% и $%x=2^7k+83$%. По модулю $%2^8$% это даёт два решения: 83 и 211.

2) $%y=4z+2$%. Здесь рассуждения аналогичны предыдущим, и получается также два значения по модулю $%2^8$%: это 45 и 173. Вычисления можно даже не проводить, поскольку вместе с решением $%x=2y+1$% у сравнения будет решение $%-x=-2y-1=2(-y-1)+1$%, где $%y$% меняется на $%-y-1$%. Это сводит второй случай к уже разобранному первому.

Итого $%x\equiv45,83,173,211\pmod{2^8}$%.

ссылка

отвечен 18 Дек '14 18:09

изменен 22 Дек '14 0:19

Благодарю. Только в конце у Вас опечатка. Вместо 41 должно быть 45.

(22 Дек '14 0:09) Andrew

@Andrew: да, это была описка. Я сейчас её исправлю.

(22 Дек '14 0:19) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×42

задан
18 Дек '14 6:51

показан
731 раз

обновлен
23 Май '15 3:16

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

по почте:

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

по RSS:

Ответы

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

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