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

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

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

Теорема (Квадратичный закон взаимности):

Для любых простых нечетных [math]p[/math] и [math]q[/math] справедливо: [math]\left(\cfrac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\cdot\left(\cfrac{q}{p}\right)[/math] Впервые теорема была сформулирована Эйлером в1783 году, а впоследствии доказана Гауссомв 1796, и имела следующую формулировку: [math]\left(\cfrac{p}{q}\right)\neq\left(\cfrac{q}{p}\right)\Leftrightarrow\begin{cases}p\equiv 3\pmod 4\\q\equiv 3\pmod 4\end{cases}[/math]

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

[math]\triangleright[/math]

Теорема приводится без доказательства.

[math]\triangleleft[/math]

Символ Якоби

Определение:

Пусть [math]n[/math] — нечетное, больше единицы и [math]n=p_1\cdots p_s[/math], где [math]p_1,\cdots,p_s[/math] — простые числа. Тогда символ Якоби [math]\left(\cfrac{a}{n}\right)[/math] определяется следующим равенством: [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{a}{p_1}\right)\times\cdots\times\left(\cfrac{a}{p_s}\right)[/math]. Символ Якоби является обобщением символа Лежандра, а символ Лежандра является частным случаем символа Якоби.

Свойства символа Якоби

Свойства символа Якоби прямо вытекают из соответствующих свойств символа Лежандра. Их доказательство оставляется читателю в качестве самостоятельного упражнения.

Утверждение (1):

[math]a_1\equiv a \pmod n\Rightarrow\left(\cfrac{a_1}{n}\right)=\left(\cfrac{a}{n}\right)[/math]

Утверждение (2):

[math]\left(\cfrac{ab}{n}\right)=\left(\cfrac{a}{n}\right)\left(\cfrac{b}{n}\right)[/math]

Утверждение (3):

НОД[math](a,n)=1\Rightarrow\left(\cfrac{a^2 b}{n}\right)=\left(\cfrac{b}{n}\right)[/math]

Утверждение (4):

[math]\left(\cfrac{1}{n}\right)=1[/math]

Утверждение (5):

[math]\left(\cfrac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}[/math]

[math]\triangleright[/math]

Рассмотрим нечетные [math]n[/math] и [math]m[/math]: [math]0\equiv(n-1)(m-1)\pmod 4\Rightarrow n-1+m-1=nm-1\pmod 4\Rightarrow \cfrac{n-1}{2}+~\cfrac{m-1}{2}\equiv~\cfrac{nm-1}{2}\pmod 4\Rightarrow\cfrac{p_1-1}{2}+\cdots+\cfrac{p_s-1}{2}\equiv\cfrac{p_1p_2\cdots p_s-1}{2}\pmod 2[/math] Так как [math]\left(\cfrac{1}{n}\right)=\left(\cfrac{1}{p_1}\right)\times\cdots\times\left(\cfrac{1}{p_s}\right)=(-1)^{\frac{p_1-1}{2}+\cdots\frac{p_s-1}{2}}[/math], получаем: [math](-1)^{\frac{p_1-1}{2}+\cdots\frac{p_s-1}{2}}=(-1)^{\frac{p_1p_2\cdots p_s-1}{2}}=(-1)^{\frac{n-1}{2}}[/math]

[math]\triangleleft[/math]

Утверждение (6):

[math]\left(\cfrac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}[/math]

[math]\triangleright[/math]

Аналогично предыдущему докажем, что [math]\cfrac{p_1^2-1}{8}+\cdots+\cfrac{p_s^2-1}{8}\equiv\cfrac{(p_1p_2\cdots p_s)^2-1}{8}\pmod 2[/math] Рассмотрим нечетные [math]n[/math] и [math]m[/math]: [math]0\equiv(n^2-1)(m^2-1)\pmod 16\Rightarrow n^2-1+m^2-1\equiv n^2m^2-1\pmod 16\Rightarrow \cfrac{n^2-1}{8}+\cfrac{m^2-1}{8}\equiv\cfrac{n^2m^2-1}{8}\pmod 2\Rightarrow\cfrac{p_1^2-1}{8}+\cdots+\cfrac{p_s^2-1}{8}\equiv\cfrac{(p_1p_2\cdots p_s-1)^2}{8}\pmod 2[/math] Получаем [math](-1)^{\frac{p_1^2-1}{8}+\cdots+\frac{p_s^2-1}{8}}=(-1)^{\frac{(p_1p_2\cdots p_s)^2-1}{8}}=(-1)^{\frac{n^2-1}{8}}[/math]

[math]\triangleleft[/math]

Обобщение квадратичного закона взаимности

Квадратичный закон взаимности для символа Лежандра обобщается на символ Якоби следующим уравнением:

Теорема (Обобщенный квадратичный закон взаимности):

для любых нечетных [math]n[/math] и [math]m[/math] справедливо: [math]\left(\cfrac{m}{n}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{m}\right)[/math].

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

[math]\triangleright[/math]

Разложим [math]n[/math] и [math]m[/math] на простые числа [math]n=p_1\times\cdots\times p_s\\m=q_1\times\cdots\times q_r[/math] Получаем [math]\left(\cfrac{m}{n}\right)=\prod^s_{i=1}\left(\cfrac{m}{p_i}\right)=\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{q_j}{p_i}\right)=\prod^s_{i=1}\prod^r_{j=1}(-1)^{\frac{p_i-1}{2}\frac{q_j-1}{2}}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\sum^r_{j=1}\frac{p_i-1}{2}\frac{q_j-1}{2}}\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\left(\frac{p_i-1}{2}\sum^r_{j=1}\frac{q_j-1}{2}\right)}\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\left(\frac{p_i-1}{2}\frac{m-1}{2}\right)}\prod^r_{j=1}\left(\cfrac{n}{q_j}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{m}\right)[/math]

[math]\triangleleft[/math]

Алгоритм вычисления символа Якоби

Для вычисления символа Якоби [math]\left(\cfrac{a}{n}\right)[/math] эффективно использовать следующий алгоритм:

1. Если [math]a\lt 0[/math], то применяя утверждения 2 и 5, получаем [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}[/math]. Вычисляем [math]\left(\cfrac{-a}{n}\right)[/math] и пропускаем последующие пункты.
2. Если [math]a[/math] четно, то применяя утверждения 2 и 6, получаем [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}[/math]. Вычисляем [math]\left(\cfrac{a/2}{n}\right)[/math] и пропускаем последующие пункты.
3. Если [math]a=1[/math], то применяя утверждение 5 [math]\left(\cfrac{a}{n}\right)=1[/math], вычисление закончилось.
4. Если [math]a\lt n[/math], то применяя теорему 2 получаем [math]\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)[/math]. Вычисляем [math]\left(\cfrac{n}{a}\right)[/math] и пропускаем последующие пункты.
5. [math]\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)[/math]. Вычисляем [math]\left(\cfrac{a\mod n}{n}\right)[/math]. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.