Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

Эта статья находится в разработке!

Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

Лемма (Гаусс, Вычисление квадратичного характера числа по простому модулю):

[math]\left(\cfrac{a}{p}\right)=(-1)^{\mu}[/math], где [math]\mu[/math] — чимло отрицательных вычетов в ряде абсолютно-наименьших вычетов произведений [math]1\cdot a,~2\ cdot a, \dots,~\frac{p-1}{2}\cdot a[/math] по модулю [math]p[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]\pm \varepsilon_i[/math] — наименьший вычет для [math]i \cdot a[/math], где <texvarepsilon_i</tex> положительно. Когда [math]i[/math] пробегает значения между 1 и [math]\frac{p-1}{2}[/math], [math]\mu[/math] будет числом получившихся при этом знаков минус.[math]\varepsilon_i\ne\varepsilon_j[/math], при [math]i\ne j[/math]. Перемножая сравнения [math]1\cdot a \equiv \pm\varepsilon_1(mod~p),~2\cdot a \equiv \pm\varepsilon_2(mod~p), \dots, ~(\frac{p-1}{2})\cdot a \equiv \pm\varepsilon_{\frac{p-1}{2}}(mod~p)[/math], получаем: [math](\frac{p-1}{2})!\cdot a^{\frac{p-1}{2}}\equiv (-1)^{\mu}\cdot(\frac{p-1}{2})! (mod~p)[/math]. Значит [math]a^{\frac{p-1}{2}}\equiv (-1)^{\mu}(mod~p);~a^{\frac{p-1}{2}}\equiv \left(\cfrac{a}{p}\right)~\Rightarrow ~ \left(\cfrac{a}{p}\right)=(-1)^{\mu}[/math].

[math]\triangleleft[/math]