Символ Лежандра

Определение. Символом Лежандра называется число $\left( \frac{p}{q} \right) = \begin{cases} 1, \mbox{если $a$ — вычет mod $p$},\\ -1, \mbox{если $a$ — невычет mod $p$},\\ 0, \mbox{если $a\equiv 0$ mod $p$.} \end{cases}$

(читается "символ $a$ по $p$")

Как можно заметить, $\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}}\pmod p$.

Свойства.

1. $\left( \frac{1}{p} \right) = 1$.

2. $\left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right)$.

3. $\left( \frac{ab^2}{p} \right) = \left( \frac{a}{p} \right)$.

Квадратичный закон взаимности

Теорема (Гаусс, квадратичный закон взаимности). Пусть $p, q \in \mathbb {P}\backslash \{ 2\}$. Тогда $\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$.

$\blacktriangle$
Пусть $a\in\mathbb{Z}_p, a\ne 0$. Рассотрим

$1 \cdot a \equiv \varepsilon _1\cdot r_1\pmod p$,

$2 \cdot a \equiv \varepsilon _2\cdot r_2\pmod p$,

$\cdots$

$\frac{p-1}{2} \cdot a \equiv \varepsilon _\frac {p-1}{2}\cdot r_\frac {p-1}{2}\pmod p$.

Где $\varepsilon _ i \in \{ -1, 1\}$. $r_ i\in \{ 1, \ldots , \frac{p-1}{2}\}$.

Докажем, что $r_ i \neq r_ j$ при $i \neq j$. Пусть $r_ i = r_ j \Rightarrow$
$\varepsilon _ i r_ i \equiv \pm \varepsilon _ j r_ j\pmod p \Rightarrow$ $ia \equiv \pm ja\pmod a \Rightarrow$ $(i \pm j)a \equiv 0\pmod p$. Противоречие.

Тогда
$1a\cdot 2a\cdot \ldots \cdot \frac{p-1}{2}a \equiv \varepsilon _1\cdot \ldots \cdot \varepsilon _\frac {p-1}{2} r_1 \cdot \ldots \cdot r_\frac {p-1}{2}\pmod p$ $\Rightarrow$

$\left( \frac{a}{p} \right) \equiv a^\frac {p-1}{2} \equiv \varepsilon _1\cdot \ldots \cdot \varepsilon _\frac {p-1}{2}\pmod p$.

Рассмотрим число $\left[ \frac{2ax}{p} \right] =$
$\left[ 2 \left[ \frac{ax}{p} \right] + 2 \left\{ \frac{ax}{p} \right\} \right] =$
$2 \left[\frac{ax}{p}\right] + \left[2\left\{ \frac{ax}{p} \right\}\right]$.
Оно чётно при $ax < \frac{p}{2}$ и нечётно при $ax \geqslant \frac{p}{2}$.

Тогда $\varepsilon_x = (-1)^{\left[ \frac{2ax}{p} \right]}$, $x\in\{1, \ldots, \frac{p-1}{2}\}$ и $\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} = \varepsilon_1\cdot\ldots\cdot\varepsilon_{\frac{p-1}{2}} = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{2ax}{p} \right]}$.

Возьмём нечётное число $a$:
$\left( \frac{2a}{p} \right) = \left( \frac{2a+2p}{p} \right) = \left( \frac{4\frac{a+p}{2}}{p}\right) = \left(\frac{4}{p}\right)\left(\frac{\frac{a+p}{2}}{p}\right) = \left(\frac{\frac{a+p}{2}}{p}\right) = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{(a+p)x}{p} \right]} = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{ax}{p} \right] + 1+\ldots+\frac{p-1}{2}} \Rightarrow$
$\left(\frac{2}{p}\right)\left(\frac{a}{p}\right) = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{ax}{p} \right] + \frac{p^2-1}{8}}$.

Если взять $a=1$, получим $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1, p = 8m+1, p = 8m+7\\ -1, p = 8m+3, p = 8m+5. \end{cases}$

Так как $\left(\frac{2}{p}\right)\left(\frac{a}{p}\right) = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{ax}{p} \right] + \frac{p^2-1}{8}}$ и $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$, то $\left(\frac{a}{p}\right) = (-1)^{\sum\limits_{x=1}^{\frac{p-1}{2}} \left[ \frac{ax}{p} \right]}$ (до этого была доказана аналогичная формула, но с двойкой).

Теперь можно доказать саму теорему.

Пусть $S := \{ (px, qy) \mid x\in\{1,\ldots,\frac{q-1}{2}\}, q\in\{1,\ldots,\frac{p-1}{2}\} \}$.
Тогда $|S| = \frac{p-1}{2} \frac{q-1}{2}$.

Очевидно, $px \ne qy$ (т.к. $(p,q)=1, x \leqslant \frac{q-1}{2}, y \leqslant \frac{p-1}{2}$).

Найдём количество пар $S_1$ таких, что $px < qy$ и количество пар $S_2$ таких, что $px > qy$.

$S_1 = \sum\limits_{y=1}^{\frac{p-1}{2}} \left[ \frac{qy}{p} \right]$,$\qquad$
$S_2 = \sum\limits_{x=1}^{\frac{q-1}{2}} \left[ \frac{px}{q} \right]$.

$S_1 + S_2 = |S| = \frac{p-1}{2} \frac{q-1}{2}$.

Но $\left(\frac{p}{q}\right) = (-1)^{S_2}$ и $\left(\frac{q}{p}\right) = (-1)^{S_1}$ $\Rightarrow$
$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{S_1 + S_2} = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$, что и требовалось доказать.
$\blacksquare$