Упражнение по теме квадратические вычеты

[bayah]

Есть такая зависимость между числами $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}$.

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

[iifat]

Верно. Квадрат в одном месте потеряли. Ну и стоит упомянуть, что именно по простому модулю делители нуля отсутствуют, то бишь из равенства нулю произведения следует равенство нулю одного из сомножителей.

[provincialka]

Меня немного смущает классификация. Что такое "сравнение другого вида"? Например, $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$?

[Sonic86]

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$?

не надо так

[bayah]

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$

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

[Sonic86]

bayah в сообщении #942515 писал(а):

вы имеете ввиду упомянуть еще в местах, где это неявно используется?

Да.