Квадратичный закон взаимности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал «Квадратичные вычеты часть 2» в «Квадратичный закон взаимности»: Разделение статьи)
Строка 1: Строка 1:
 
{{Требует доработки
 
{{Требует доработки
|item1=Статью необходимо разбить на несколько отдельных статей.
+
|item1=(Исправлено)Статью необходимо разбить на несколько отдельных статей.
 
}}
 
}}
 
==Квадратичный закон взаимности==
 
  
 
{{Теорема
 
{{Теорема
Строка 14: Строка 12:
 
Впервые теорема была сформулирована Эйлером в1783 году, а впоследствии доказана Гауссомв 1796, и имела следующую формулировку:
 
Впервые теорема была сформулирована Эйлером в1783 году, а впоследствии доказана Гауссомв 1796, и имела следующую формулировку:
 
<tex>\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}</tex>
 
<tex>\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}</tex>
|proof=
 
Теорема приводится без доказательства.
 
}}
 
 
==Символ Якоби==
 
 
{{Определение
 
|definition=
 
Пусть <tex>n</tex> {{---}} нечетное, больше единицы и <tex>n=p_1\cdots p_s</tex>, где <tex>p_1,\cdots,p_s</tex> {{---}} простые числа. Тогда символ Якоби <tex>\left(\cfrac{a}{n}\right)</tex> определяется следующим равенством:
 
 
<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a}{p_1}\right)\times\cdots\times\left(\cfrac{a}{p_s}\right)</tex>.
 
 
Символ Якоби является обобщением символа Лежандра, а символ Лежандра является частным случаем символа Якоби.
 
}}
 
 
===Свойства символа Якоби===
 
 
Свойства символа Якоби прямо вытекают из соответствующих свойств символа Лежандра. Их доказательство оставляется читателю в качестве самостоятельного упражнения.
 
 
{{Утверждение
 
|id=proposal1
 
|about=1
 
|statement=
 
<tex>a_1\equiv a \pmod n\Rightarrow\left(\cfrac{a_1}{n}\right)=\left(\cfrac{a}{n}\right)</tex>
 
}}
 
 
{{Утверждение
 
|id=proposal2
 
|about=2
 
|statement=
 
<tex>\left(\cfrac{ab}{n}\right)=\left(\cfrac{a}{n}\right)\left(\cfrac{b}{n}\right)</tex>
 
}}
 
 
{{Утверждение
 
|id=proposal3
 
|about=3
 
|statement=
 
НОД<tex>(a,n)=1\Rightarrow\left(\cfrac{a^2 b}{n}\right)=\left(\cfrac{b}{n}\right)</tex>
 
}}
 
 
{{Утверждение
 
|id=proposal4
 
|about=4
 
|statement=
 
<tex>\left(\cfrac{1}{n}\right)=1</tex>
 
}}
 
 
{{Утверждение
 
|id=proposal5
 
|about=5
 
|statement=
 
<tex>\left(\cfrac{-1}{n}\right)=(-1)^{\frac{n-1}{2}}</tex>
 
|proof=
 
Рассмотрим нечетные <tex>n</tex> и <tex>m</tex>:
 
 
<tex>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</tex>
 
 
Так как <tex>\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}}</tex>, получаем: <tex>(-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}}</tex>
 
 
}}
 
}}
  
{{Утверждение
 
|id=proposal6
 
|about=6
 
|statement=
 
<tex>\left(\cfrac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}</tex>
 
|proof=
 
Аналогично предыдущему докажем, что
 
 
<tex>\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</tex>
 
 
Рассмотрим нечетные <tex>n</tex> и <tex>m</tex>:
 
 
<tex>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</tex>
 
 
Получаем <tex>(-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}}</tex>
 
}}
 
 
===Обобщение квадратичного закона взаимности===
 
 
Квадратичный закон взаимности для символа Лежандра обобщается на символ Якоби следующим уравнением:
 
{{Теорема
 
|id=th2
 
|about=Обобщенный квадратичный закон взаимности
 
|statement=для любых нечетных <tex>n</tex> и <tex>m</tex> справедливо:
 
 
<tex>\left(\cfrac{m}{n}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{m}\right)</tex>.
 
|proof=
 
Разложим <tex>n</tex> и <tex>m</tex> на простые числа
 
 
<tex>n=p_1\times\cdots\times p_s\\m=q_1\times\cdots\times q_r</tex>
 
 
Получаем
 
 
<tex>\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)</tex>
 
}}
 
 
===Алгоритм вычисления символа Якоби===
 
 
Для вычисления символа Якоби <tex>\left(\cfrac{a}{n}\right)</tex> эффективно использовать следующий алгоритм:
 
 
#Если <tex>a<0</tex>, то применяя утверждения [[#proposal2|2]] и [[#proposal5|5]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}</tex>. Вычисляем <tex>\left(\cfrac{-a}{n}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a</tex> четно, то применяя утверждения [[#proposal2|2]] и [[#proposal6|6]], получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}</tex>. Вычисляем <tex>\left(\cfrac{a/2}{n}\right)</tex> и пропускаем последующие пункты.
 
#Если <tex>a=1</tex>, то применяя утверждение 5 <tex>\left(\cfrac{a}{n}\right)=1</tex>, вычисление закончилось.
 
#Если <tex>a<n</tex>, то применяя [[#th2|теорему 2]] получаем <tex>\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)</tex>. Вычисляем <tex>\left(\cfrac{n}{a}\right)</tex> и пропускаем последующие пункты.
 
#<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)</tex>. Вычисляем <tex>\left(\cfrac{a\mod n}{n}\right)</tex>. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.
 
 
[[Категория: Теория чисел]]
 
[[Категория: Теория чисел]]

Версия 18:11, 30 июня 2010

Эта статья требует доработки!
  1. (Исправлено)Статью необходимо разбить на несколько отдельных статей.

Если Вы исправили некоторые из указанных выше замечаний, просьба дописать в начало соответствующего пункта (Исправлено).

Теорема (Квадратичный закон взаимности):
Для любых простых нечетных [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]