Символ Лежандра
Определение. Символом Лежандра называется число $\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$.
Свойства.
$\left( \frac{1}{p} \right) = 1$.
$\left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right) $.
$\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$