Символ Лежандра
Определение. Символом Лежандра называется число (pq)={1,если a — вычет mod p,−1,если a — невычет mod p,0,если a≡0 mod p.
(читается "символ 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