Произведение квадратичных невычетов

[Dave]

Пусть $p>3$ - простое число, $N_p$ - произведение всех квадратичных невычетов по модулю $p$, больших $1$ и меньших $p-1$. Докажите, что $N_p \equiv 1 \pmod p$.

[Sonic86]

$p\equiv 1(4)\Rightarrow N_p\equiv g^{1+3+...+(p-2)}\equiv g^{\frac{(p-1)^2}{4}}\equiv g^{(p-1)\frac{p-1}{4}}\equiv 1\pmod p$.
$p\equiv 3(4)\Rightarrow N_p\equiv -g^{1+3+...+(p-2)}\equiv g^{\frac{(p-1)^2}{4}+\frac{p-1}{2}}\equiv g^{(p-1)\frac{p+1}{4}}\equiv 1\pmod p$.
Для $p=3$ утверждение также верно, если считать произведение по пустому множеству равным $1$ (что обычно и делается).

[Dave]

А как доказать, что такой элемент $g$ всегда существует?

[Sonic86]

Группы $\mathbb{Z}_{p^k}^{\times}$ и $\mathbb{Z}_{2p^k}^{\times}$ для $p>2$ всегда цикличны. Мультипликативные группы всех полей также цикличны. Это общеизвестный факт (проще всего с позиции конечных полей доказывать. Книги - Лидл Нидеррайтер Конечные поля или Айрленд Роузен Классическое введение в современную теорию чисел. Даже в Бухштабе есть (но там не про поля)).
(по памяти: группа $G$ циклична $\Leftrightarrow$ ее порядок совпадает с ее экспонентой. Считаем мощность группы и считаем число элементов порядка $d:d| |G|$ - сравниваем - второе меньше. Через формулу обращения Мёбиуса получаем формулу для числа образующих)

-- Чт май 31, 2012 04:52:36 --

Можно попытаться обобщить: произведение всех элементов $\mathbb{Z}_p^{\times}$ равно 1. Пусть $p\equiv 1\pmod q, q>2$. Произведение всех $q$-х степеней равно $g^{d+2d+...+p-1}\equiv g^{(p-1)\frac{(p-1+d)}{2d}}\equiv 1\pmod{p}$. Значит произведение все не-$q$-х степеней тоже равно 1.

[Dave]

Спасибо. В Айрленде-Роузене аж 3 доказательства!

Sonic86 в сообщении #578821 писал(а):

Можно попытаться обобщить: произведение всех элементов $\mathbb{Z}_p^{\times}$ равно 1. Пусть $p\equiv 1\pmod q, q>2$. Произведение всех $q$-х степеней равно $g^{d+2d+...+p-1}\equiv g^{(p-1)\frac{(p-1+d)}{2d}}\equiv 1\pmod{p}$. Значит произведение все не-$q$-х степеней тоже равно 1.

А здесь 2 ошибки (если не считать опечатку $d \sim q$). Во-первых, по теореме Вильсона, произведение всех элементов $\mathbb{Z}_p^{\times}$ равно $-1$. Во-вторых, $g^{(p-1)\frac{(p-1+d)}{2d}}\equiv \left(g^{\frac {p-1} 2}\right)^{\frac {p-1} d +1}\equiv (-1)^{\frac {p-1} d +1}\equiv \pm 1 \pmod p$. В случае нечётного $d$ ($q$) минус на минус даёт плюс, так что всё верно, в случае же чётного $q$ возможны варианты. К примеру, при $p=13$, $q=4$ произведение всех невычетов $4$-й степени таки даёт $-1$ по модулю $13$, а не $1$.

-- 31.05.2012, 17:04 --

А как насчёт сумм?

Пусть $p \geqslant 7$ - простое число, $Q_p$ - сумма квадратов всех квадратичных невычетов по модулю $p$, больших $0$ и меньших $p$. Докажите, что $Q_p \equiv 0 \pmod p$.

[Sonic86]

Dave в сообщении #578984 писал(а):

А здесь 2 ошибки (если не считать опечатку $d \sim q$). Во-первых, по теореме Вильсона, произведение всех элементов $\mathbb{Z}_p^{\times}$ равно $-1$. Во-вторых, $g^{(p-1)\frac{(p-1+d)}{2d}}\equiv \left(g^{\frac {p-1} 2}\right)^{\frac {p-1} d +1}\equiv (-1)^{\frac {p-1} d +1}\equiv \pm 1 \pmod p$. В случае нечётного $d$ ($q$) минус на минус даёт плюс, так что всё верно, в случае же чётного $q$ возможны варианты. К примеру, при $p=13$, $q=4$ произведение всех невычетов $4$-й степени таки даёт $-1$ по модулю $13$, а не $1$.

(Оффтоп)

Ааа, да, спасибо, я расслабился

Извините, действительно $d$ вместо $q$.

Dave в сообщении #578984 писал(а):

А как насчёт сумм?

Пусть $p \geqslant 7$ - простое число, $Q_p$ - сумма квадратов всех квадратичных невычетов по модулю $p$, больших $0$ и меньших $p$. Докажите, что $Q_p \equiv 0 \pmod p$.

Давайте тогда считать симметрические функции от $d$-х степеней . Обозначим их множество $M_d=\{g^d,\ldots,g^{dn}\}$, $|M_d|=\frac{p-1}{d}=n$. Любая симметрическая функция от $M_d$ выражается через элементарные симметрические многочлены от $M_d$ --- $\sigma _1(M_d),\ldots,\sigma_n(M_d)$. Уже нашли $\sigma_n(M_2)\equiv (-1)^{n+1}\pmod p$ (т. Вильсона --- $\sigma_n(M_1)\equiv -1\pmod p$). Для $1\leqslant k<n$, поскольку $g^dM_d\equiv M_d$ ($x\to x\cdot g^d$ --- биекция на $M_d$), то $\sigma_k(M_d)$ не меняется при умножении на $g^{dk}$: $g^{dk}\sigma_k(M_d)\equiv\sigma_k(M_d)$. И тогда, если $p-1\nmid kd$, то $\sigma_k(M_d)\equiv 0\pmod{p}$. Отсюда получается то, что Вы ищете: искомая сумма $\eqiuiv\sigma_1(M_1)-(\sigma_1^2(M_2)-2\sigma_2(M_2))\equiv 0\pmod p$, т.к. $p-1 \nmid 1,2,4$ при $p\geqslant 7$.
Надо бы еще разобрать случай $p-1\mid kd\Leftrightarrow n\mid k$...
upd: туплю - все сводится к $\sigma_n(M_d)\equiv (-1)^{n+1}\pmod p$.

[Dave]

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

Cумма $t$-х степеней всех квадратичных вычетов (так же, как и всех невычетов) по простому модулю $p$ делится на $p$, если только $p>2t+1$.