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

alt text

Символ Лежандра равен единице, значит сравнение разрешимо. После чего делаю так:

alt text

Вот дальше не могу решить это сравнение... Пытаюсь делать так Получаю, что 17 = 1(mod 8). Представляю 17 в виде: 17 = (2^4)*1 + 1 Т.е. k=4; h=1 Далее я читал, что решение имеет вид: alt text

Про N написано, что это произвольный квадратичный невычет по модулю p, а про s_k написано, что произвольное больше нуля. Вот я не очень понимаю, какие числа вместо них подставлять, да и вообще не уверен в правильности того, что написал. Помогите пожалуйста.

задан 17 Дек '14 18:24

изменен 17 Дек '14 18:30

@Andrew, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

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

Это верно, что сначала надо решить сравнение по модулю 17. Это делается совсем просто, без применения каких-либо формул. Решение находится подбором; в самом худшем случае надо перебрать значения от 1 до 8, возводя каждое их них в квадрат. (То, что решение точно есть, мы знаем из вычисления символа Лежандра.) Ещё более простой способ подбора основан на том, что мы берём число 8 и начинаем прибавлять к нему по 17, пока не получим точный квадрат. Здесь это происходит сразу же, и получается 25, откуда следует, что подходят $%x=\pm5$% по модулю 17. Других корней нет, как как уравнение квадратное по простому модулю.

Теперь полагаем $%x=17k\pm5$% и подставляем в исходное сравнение по модулю $%17^2$%. Получается $%\pm170k+25\equiv178\pmod{17^2}$%, что после упрощений и полного сокращения на 17 равносильно $%\pm10k\equiv9\pmod{17}$%. Это линейное сравнение, оно решается просто. Заменяем 9 на 60, сокращаем на 10. Получается $%k\equiv\pm6\pmod{17}$%. Отсюда $%k=17m\pm6$%, и $%x=17(17m\pm6)\pm5=17^2m\pm107$% с согласованным выбором знаков. Тем самым, решения исходного сравнения имеют вид $%x\equiv\pm107\pmod{17^2}$%.

ссылка

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

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

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

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

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

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

отмечен:

×43

задан
17 Дек '14 18:24

показан
451 раз

обновлен
17 Дек '14 19:03

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

по почте:

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

по RSS:

Ответы

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

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