$%{x^2} \equiv - 2\,(\bmod \,113)$% Разрешимо ли? (показать, почему разрешимо)

задан 21 Июн '17 18:22

изменен 22 Июн '17 0:24

night-raven's gravatar image


4.1k318

а верно ли следующее решение: (111/113)=(113/111)(-1)^(((113-1)/2)((111-1)/2))=-1 следовательно не разрешимо? (следует из определения символа Лежандра)

(21 Июн '17 19:58) kokos1337

-2 - это остаток, а не число. -2 mod 113 = 111 mod 113

(21 Июн '17 20:03) Williams Wol...

@kokos1337: У Вас неправильно из-за того, что 111 не является простым числом, поэтому квадратичный закон взаимности использовать нельзя!

(21 Июн '17 20:52) goldish09

$%x = 26 + 113n,\,\,y = 87 + 113n,\,\,n \in {\Bbb Z}$% Разрешимость доказывается через символ Лежандра.

(22 Июн '17 0:23) night-raven

@void_pointer: если уже приведён пример конкретного решения x=26, то разрешимость можно доказать прямой подстановкой -- символы Лежандра при этом уже не нужны.

(22 Июн '17 15:35) falcao
10|600 символов нужно символов осталось
1

Число 113 простое, и можно использовать свойства символа Лежандра. Ввиду того, что p=113 имеет вид 4k+1, верно равенство (-1/p)=1. Далее, 113 является числом вида 8k+1, а тогда (2/p)=1 по известному свойству. Следовательно, (-2/113)=(-1/113)(2/113)=1, то есть уравнение разрешимо. Можно найти решение подбором: подходит x=26, а также x=-26, то есть x=87, но это уже не требуется.

Можно решать и другими способами. Если вычислять символ Лежандра числа 111 вместо -2, то можно разложить это число на множители, и найти (3/113)(37/113). Далее закон взаимности не меняет знака, так как 113=4k+1. Получается (113/3)(113/37)=(2/3)(2/37)=1, так как оба символа равны -1 (число 37 не имеет вида 8m+-1).

Наконец, можно вычислять символ Лежандра как символ Якоби, пользуясь законом взаимности для символов Якоби. Это даст (111/113)=(113/111)=(2/111), и здесь снова работает свойство символа для двойки, где критерий в случае символов Якоби такой же. А именно, получится 1, так как 111 имеет вид 8m-1.

Лично я считаю лучшим первый из способов.

ссылка

отвечен 21 Июн '17 21:03

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

$$x^2\equiv-2 (\bmod113)$$ $$x^2\equiv 111 (\bmod113)$$ $$\left(\frac{111}{113}\right)=\left(\frac{3\cdot37}{113}\right)=\left(\frac{3}{113}\right)\left(\frac{37}{113}\right)=$$ [тут уже можно использовать квадратичный закон взаимности] $$=(-1)(-1)=1$$

Ответ: разрешимо.

ссылка

отвечен 21 Июн '17 20:57

изменен 21 Июн '17 21:00

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

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

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

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

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

отмечен:

×879

задан
21 Июн '17 18:22

показан
499 раз

обновлен
22 Июн '17 15:35

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

по почте:

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

по RSS:

Ответы

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

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