2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Упражнение по теме квадратические вычеты
Сообщение07.12.2014, 16:50 
Есть такая зависимость между числами $1^2, 2^2, ..., (p-1)^2$:
$x^2 \equiv (p-x)^2 \pmod{p}$
,где $p$ - простое.
Действительно, $(p-x)^2 = p^2-2px+x^2 \equiv x^2 \pmod{p} $.


Теперь собственно упражнение: нужно показать, что иного вида сравнений между числами $1^2, 2^2, ..., (p-1)^2$ быть не может.

Предположим, что $x^2 \equiv (x+n)^2$, тогда $(x+n)^2$ так же должно быть сравнимо с $(p-x)^2$:
$(x+n)^2 \equiv (p-x)^2$
$x^2+2xn+n^2 \equiv x^2$
$2xn+n^2 \eequiv 0$
$n(2x+n) \equiv 0$

Отсюда:
- либо $n \equiv 0$, что эквивалентно нашей данной зависимости $x^2 \equiv (p-x)^2 \pmod{p}$.
- либо $2x+n \equiv 0$. Тогда $n \equiv -2x$, или иначе $n \equiv p-2x$. Далее, если подставить это в наше предположение $x^2 \equiv (x+n)^2$, то получим:
$x^2 \equiv (x+p-2x)^2$
$x^2 \equiv (p-x)$
то есть нашу первоначальную зависимость.
То есть n - не может быть иным, кроме как $n \equiv p-2x$, что и есть наша зависимость $x^2 \equiv (p-x)^2 \pmod{p}$.

Правильно? Или я гоню?)

 
 
 
 Re: Упражнение по теме квадратические вычеты
Сообщение07.12.2014, 19:46 
Верно. Квадрат в одном месте потеряли. Ну и стоит упомянуть, что именно по простому модулю делители нуля отсутствуют, то бишь из равенства нулю произведения следует равенство нулю одного из сомножителей.

 
 
 
 Re: Упражнение по теме квадратические вычеты
Сообщение07.12.2014, 19:59 
Аватара пользователя
Меня немного смущает классификация. Что такое "сравнение другого вида"? Например, $x^4 \equiv (p-x)^4 \pmod{p}$ - другого вида?
bayah в сообщении #941846 писал(а):
- либо $n \equiv 0$, что эквивалентно нашей данной зависимости $x^2 \equiv (p-x)^2 \pmod{p}$.
То есть вы вводите некоторое отношение эквивалентности для своих сравнений.

Кстати, почему отношение $x^2 \equiv (p+x)^2 \pmod{p}$ эквивалентно именно $x^2 \equiv (p-x)^2 \pmod{p}$? А не скажем, $x^2 \equiv x^2 \pmod{p}$, которое получится из него заменой $p$ на $0$?

 
 
 
 Re: Упражнение по теме квадратические вычеты
Сообщение07.12.2014, 20:33 
bayah в сообщении #941846 писал(а):
Предположим, что $x^2 \equiv (x+n)^2$, тогда $(x+n)^2$ так же должно быть сравнимо с $(p-x)^2$:
$(x+n)^2 \equiv (p-x)^2$
$x^2+2xn+n^2 \equiv x^2$
$2xn+n^2 \eequiv 0$
$n(2x+n) \equiv 0$
Здесь Вы избыточно рассматриваете сравнение $(x+n)^2\equiv (p-x)^2\pmod p$. Достаточно рассмотреть $(x+n)^2\equiv x^2\pmod p$. Лаконичность свидетельствует о ясности и продуманности рассуждения.

Кроме того, было бы желательно, чтобы Вы явно в доказательстве упомянули к месту тот факт, что $p$ - простое, поскольку для доказательства он необходим.

bayah в сообщении #941846 писал(а):
ужно показать, что иного вида сравнений между числами $1^2, 2^2, ..., (p-1)^2$ быть не может.
Это следует сформулировать четче: если $a^2\equiv b^2\pmod p$, то $a\equiv \pm b\pmod p$.
provincialka в сообщении #941957 писал(а):
Что такое "сравнение другого вида"?
ТС имеет ввиду именно это.

А в целом нормально, ну сумбурно немного.

provincialka в сообщении #941957 писал(а):
То есть вы вводите некоторое отношение эквивалентности для своих сравнений.
Ага: сравнения эквивалентны, когда они эквивалентны как высказывания :-)

(Оффтоп)

provincialka в сообщении #941957 писал(а):
Кстати, почему отношение $x^2 \equiv (p+x)^2 \pmod{p}$ эквивалентно именно $x^2 \equiv (p-x)^2 \pmod{p}$? А не скажем, $x^2 \equiv x^2 \pmod{p}$, которое получится из него заменой $p$ на $0$?
:shock: не надо так :roll:

 
 
 
 Re: Упражнение по теме квадратические вычеты
Сообщение08.12.2014, 17:52 
iifat в сообщении #941951 писал(а):
Верно. Квадрат в одном месте потеряли. Ну и стоит упомянуть, что именно по простому модулю делители нуля отсутствуют, то бишь из равенства нулю произведения следует равенство нулю одного из сомножителей.

Да - точно, квадрат потерял.
И знак сравнения по модулю еще забыл (так называется тройное равно?)).
И да, конечно, именно по простому модулю из равенства нулю произведения следует равенство нулю одного из сомножителей, спасибо.

provincialka в сообщении #941957 писал(а):
Меня немного смущает классификация. Что такое "сравнение другого вида"? Например, $x^4 \equiv (p-x)^4 \pmod{p}$ - другого вида?

Ну такое сравнение ведь получается тождественным $x^2 \equiv (p-x)^2 \pmod{p}$ ?

provincialka в сообщении #941957 писал(а):
То есть вы вводите некоторое отношение эквивалентности для своих сравнений.

Это у меня вольное, неверное использование слова эквивалетность) Я хотел сказать тождественно.

provincialka в сообщении #941957 писал(а):
Кстати, почему отношение $x^2 \equiv (p+x)^2 \pmod{p}$ эквивалентно именно $x^2 \equiv (p-x)^2 \pmod{p}$? А не скажем, $x^2 \equiv x^2 \pmod{p}$, которое получится из него заменой $p$ на $0$?


Ну мы же хотим показать соотношение между числами от $1^2$ до $(p-1)^2$, а $(p+x)^2$ и $x^2$ одно и то же число. А $(p-x)^2$ не то же что $x^2$. Нет?

Sonic86 в сообщении #941982 писал(а):
Здесь Вы избыточно рассматриваете сравнение $(x+n)^2\equiv (p-x)^2\pmod p$. Достаточно рассмотреть $(x+n)^2\equiv x^2\pmod p$. Лаконичность свидетельствует о ясности и продуманности рассуждения.

Да, я сам смотрю, что потом к этому же и пришел. Что-то я тут запутался.)
Я вообще хотел доказывать от противного - предполагать, что $x^2$ сравним с каким-то еще числом из $1^2, 2^2, ..., (p-1)^2$, кроме $(x-p)^2$. Потом из того, что предполагаемое число так же должно быть сравнимо и с $(x-p)^2$ прийти к противоречию.

Sonic86 в сообщении #941982 писал(а):
Кроме того, было бы желательно, чтобы Вы явно в доказательстве упомянули к месту тот факт, что $p$ - простое, поскольку для доказательства он необходим.

Ну вначале есть, что p - простое. Или вы имеете ввиду упомянуть еще в местах, где это неявно используется?

Sonic86 в сообщении #941982 писал(а):
Это следует сформулировать четче: если $a^2\equiv b^2\pmod p$, то $a\equiv \pm b\pmod p$

Ну даа... Так и яснее стало. Спасибо)

 
 
 
 Re: Упражнение по теме квадратические вычеты
Сообщение08.12.2014, 18:50 
bayah в сообщении #942515 писал(а):
вы имеете ввиду упомянуть еще в местах, где это неявно используется?
Да.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group