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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма Гаусса для вычисления квадратичного характера числа по простому модулю)
(не показаны 2 промежуточные версии 2 участников)
Строка 6: Строка 6:
 
|about=Вычисление квадратичного характера числа по простому модулю
 
|about=Вычисление квадратичного характера числа по простому модулю
 
|statement=  
 
|statement=  
<tex>\left(\cfrac{a}{p}\right)=(-1)^{\mu}</tex>, где <tex>\mu</tex> — число отрицательных вычетов в ряде абсолютно-наименьших вычетов произведений <tex>1\cdot a,~2\ cdot a, \dots,~\frac{p-1}{2}\cdot a</tex> по модулю <tex>p</tex>.
+
<tex>\left(\cfrac{a}{p}\right)=(-1)^{\mu}</tex>, где <tex>\mu</tex> — число отрицательных вычетов в ряде абсолютно-наименьших вычетов произведений <tex>1\cdot a,~2\cdot a, \dots,~\frac{p-1}{2}\cdot a</tex> по модулю <tex>p</tex>.
 
|proof=  
 
|proof=  
Пусть <tex>\pm \varepsilon_i</tex> — наименьший вычет для <tex>i \cdot a</tex>, где <texvarepsilon_i</tex> положительно. Когда <tex>i</tex> пробегает значения между 1 и <tex>\frac{p-1}{2}</tex>, <tex>\mu</tex> будет числом получившихся при этом знаков минус.<tex>\varepsilon_i\ne\varepsilon_j</tex>, при <tex>i\ne j</tex>. Перемножая сравнения <tex>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)</tex>, получаем:
+
Пусть <tex>\pm\varepsilon_i</tex> — наименьший вычет для <tex>i \cdot a</tex>, где <tex>\varepsilon_i</tex> положительно. Когда <tex>i</tex> пробегает значения между 1 и <tex>\frac{p-1}{2}</tex>, <tex>\mu</tex> будет числом получившихся при этом знаков минус.<tex>\varepsilon_i\ne\varepsilon_j</tex>, при <tex>i\ne j</tex>. Перемножая сравнения <tex>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)</tex>, получаем:
 
<br>
 
<br>
 
<tex>(\frac{p-1}{2})!\cdot a^{\frac{p-1}{2}}\equiv (-1)^{\mu}\cdot(\frac{p-1}{2})! (mod~p)</tex>.
 
<tex>(\frac{p-1}{2})!\cdot a^{\frac{p-1}{2}}\equiv (-1)^{\mu}\cdot(\frac{p-1}{2})! (mod~p)</tex>.
Строка 14: Строка 14:
 
Значит <tex>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}</tex>.
 
Значит <tex>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}</tex>.
 
}}
 
}}
 +
 
==Квадратичный характер числа 2 по простому модулю==
 
==Квадратичный характер числа 2 по простому модулю==
Итак, нас интересует <tex>\left(\cfrac{2}{p}\right)</tex>. В лемме Гаусса для числа 2, без учета требования того, что члены ряда - абсолютно-наименьшие, получим ряд <tex>2,4,\dots,p-1</tex>. Применяя опущенное требование получим, что все члены ряда, меньшие <tex>\frac{p}{2}</tex> останутся положительными, а остальные - станут отрицательными. Рассмотрим 4 случая:
+
Итак, нас интересует <tex>\left(\cfrac{2}{p}\right)</tex>. В лемме Гаусса для числа 2, без учета требования того, что члены ряда абсолютно-наименьшие, получим ряд <tex>2,4,\dots,p-1</tex>. Применяя опущенное требование получим, что все члены ряда, меньшие <tex>\frac{p}{2}</tex> останутся положительными, а остальные станут отрицательными. Рассмотрим 4 случая:
 
# <tex>p=1(mod~8)</tex>
 
# <tex>p=1(mod~8)</tex>
 
# <tex>p=3(mod~8)</tex>
 
# <tex>p=3(mod~8)</tex>
 
# <tex>p=5(mod~8)</tex>
 
# <tex>p=5(mod~8)</tex>
 
# <tex>p=7(mod~8)</tex>
 
# <tex>p=7(mod~8)</tex>
* Перый случай: <tex>p=1(mod~8)\Rightarrow \frac{p-1}{2}=0 (mod~4)</tex>. Получается в лемме Гаусса количество чисел в ряде кратно 4. Рассмотрим два центральных числа - с номером <tex>\frac{p-1}{4}</tex>, и с номером <tex>\frac{p-1}{4}+1</tex>. Очевидно первое из них положительно, и равно <tex>\frac{p-1}{2}</tex>, а второе отрицательно, и равно <tex>\frac{p-1}{2}+2-p=\frac{p+3}{2}+p</tex>. Значит все числа делятся ровно пополам, и первые <tex>\frac{p-1}{4}</tex> из них - положительны, а остальные - отрицательны. Но так как <tex>\frac{p-1}{2}\vdots 4</tex>, то в каждой половине четное количество чисел, значит количество знаков "минус" в ряде четное, значит, по лемме Гаусса, <tex>\left(\cfrac{2}{p}\right) =1</tex>.<br>
+
* Перый случай: <tex>p=1(mod~8)\Rightarrow \frac{p-1}{2}=0 (mod~4)</tex>. Получается в лемме Гаусса количество чисел в ряде кратно 4. Рассмотрим два центральных числа с номером <tex>\frac{p-1}{4}</tex>, и с номером <tex>\frac{p-1}{4}+1</tex>. Очевидно первое из них положительно, и равно <tex>\frac{p-1}{2}</tex>, а второе отрицательно, и равно <tex>\frac{p-1}{2}+2-p=\frac{p+3}{2}+p</tex>. Значит все числа делятся ровно пополам, и первые <tex>\frac{p-1}{4}</tex> из них положительны, а остальные отрицательны. Но так как <tex>\frac{p-1}{2}\vdots 4</tex>, то в каждой половине четное количество чисел, значит количество знаков "минус" в ряде четное, значит, по лемме Гаусса, <tex>\left(\cfrac{2}{p}\right) =1</tex>.<br>
* Второй случай: <tex>p=3(mod~8)\Rightarrow \frac{p-1}{2}=1 (mod~4)</tex>. Значит в лемме Гаусса количество чисел в ряде нечетно, причем если убрать одно число, то все остальные будут делиться на равные две части, количество чисел в каждой из которых - четно. Значит требуется узнать, является ли среднее число положительным, или отрицательным. Его номер <tex>\frac{\frac{p-1}{2}-1}{2}+1</tex>, следовательно оно равно <tex>\frac{p-1}{2}-1+2=\frac{p+1}{2}>\frac{p}{2}</tex> - значит оно отрицательно, то есть в ряде четное число положительных, и нечетное число отрицательных чисел, значит <tex>\left(\cfrac{2}{p}\right)=-1</tex>.<br>
+
* Второй случай: <tex>p=3(mod~8)\Rightarrow \frac{p-1}{2}=1 (mod~4)</tex>. Значит в лемме Гаусса количество чисел в ряде нечетно, причем если убрать одно число, то все остальные будут делиться на равные две части, количество чисел в каждой из которых четно. Значит требуется узнать, является ли среднее число положительным, или отрицательным. Его номер <tex>\frac{\frac{p-1}{2}-1}{2}+1</tex>, следовательно оно равно <tex>\frac{p-1}{2}-1+2=\frac{p+1}{2}>\frac{p}{2}</tex> значит оно отрицательно, то есть в ряде четное число положительных, и нечетное число отрицательных чисел, значит <tex>\left(\cfrac{2}{p}\right)=-1</tex>.<br>
* Третий случай: <tex>p=5(mod~8)\Rightarrow \frac{p-1}{2}=2 (mod~4)</tex>. Получаем ситуацию как в первом случае, с тем отличием, что в каждой половине ряда нечетное количество чисел - значит отрицательных чисел нечетное количество, и значит <tex>\left(\cfrac{2}{p}\right)=-1</tex>.<br>
+
* Третий случай: <tex>p=5(mod~8)\Rightarrow \frac{p-1}{2}=2 (mod~4)</tex>. Получаем ситуацию как в первом случае, с тем отличием, что в каждой половине ряда нечетное количество чисел значит отрицательных чисел нечетное количество, и значит <tex>\left(\cfrac{2}{p}\right)=-1</tex>.<br>
* Четвертый случай: <tex>p=7(mod~8)\Rightarrow \frac{p-1}{2}=3 (mod~4)</tex>. Аналогично второму случаю, но при разбиение на две половины, количество чисел в каждой из них - нечетно. Число в середине так же получим отрицательное, значит всего отрицательных чисел четное количество, и <tex>\left(\cfrac{2}{p}\right)=1</tex>.<br>
+
* Четвертый случай: <tex>p=7(mod~8)\Rightarrow \frac{p-1}{2}=3 (mod~4)</tex>. Аналогично второму случаю, но при разбиение на две половины, количество чисел в каждой из них нечетно. Число в середине так же получим отрицательное, значит всего отрицательных чисел четное количество, и <tex>\left(\cfrac{2}{p}\right)=1</tex>.<br>
 
[[Категория: Теория чисел]]
 
[[Категория: Теория чисел]]

Версия 08:26, 14 мая 2011

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

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

Лемма (Гаусс, Вычисление квадратичного характера числа по простому модулю):
[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], где [math]\varepsilon_i[/math] положительно. Когда [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]

Квадратичный характер числа 2 по простому модулю

Итак, нас интересует [math]\left(\cfrac{2}{p}\right)[/math]. В лемме Гаусса для числа 2, без учета требования того, что члены ряда — абсолютно-наименьшие, получим ряд [math]2,4,\dots,p-1[/math]. Применяя опущенное требование получим, что все члены ряда, меньшие [math]\frac{p}{2}[/math] останутся положительными, а остальные — станут отрицательными. Рассмотрим 4 случая:

  1. [math]p=1(mod~8)[/math]
  2. [math]p=3(mod~8)[/math]
  3. [math]p=5(mod~8)[/math]
  4. [math]p=7(mod~8)[/math]
  • Перый случай: [math]p=1(mod~8)\Rightarrow \frac{p-1}{2}=0 (mod~4)[/math]. Получается в лемме Гаусса количество чисел в ряде кратно 4. Рассмотрим два центральных числа — с номером [math]\frac{p-1}{4}[/math], и с номером [math]\frac{p-1}{4}+1[/math]. Очевидно первое из них положительно, и равно [math]\frac{p-1}{2}[/math], а второе отрицательно, и равно [math]\frac{p-1}{2}+2-p=\frac{p+3}{2}+p[/math]. Значит все числа делятся ровно пополам, и первые [math]\frac{p-1}{4}[/math] из них — положительны, а остальные — отрицательны. Но так как [math]\frac{p-1}{2}\vdots 4[/math], то в каждой половине четное количество чисел, значит количество знаков "минус" в ряде четное, значит, по лемме Гаусса, [math]\left(\cfrac{2}{p}\right) =1[/math].
  • Второй случай: [math]p=3(mod~8)\Rightarrow \frac{p-1}{2}=1 (mod~4)[/math]. Значит в лемме Гаусса количество чисел в ряде нечетно, причем если убрать одно число, то все остальные будут делиться на равные две части, количество чисел в каждой из которых — четно. Значит требуется узнать, является ли среднее число положительным, или отрицательным. Его номер [math]\frac{\frac{p-1}{2}-1}{2}+1[/math], следовательно оно равно [math]\frac{p-1}{2}-1+2=\frac{p+1}{2}\gt \frac{p}{2}[/math] — значит оно отрицательно, то есть в ряде четное число положительных, и нечетное число отрицательных чисел, значит [math]\left(\cfrac{2}{p}\right)=-1[/math].
  • Третий случай: [math]p=5(mod~8)\Rightarrow \frac{p-1}{2}=2 (mod~4)[/math]. Получаем ситуацию как в первом случае, с тем отличием, что в каждой половине ряда нечетное количество чисел — значит отрицательных чисел нечетное количество, и значит [math]\left(\cfrac{2}{p}\right)=-1[/math].
  • Четвертый случай: [math]p=7(mod~8)\Rightarrow \frac{p-1}{2}=3 (mod~4)[/math]. Аналогично второму случаю, но при разбиение на две половины, количество чисел в каждой из них — нечетно. Число в середине так же получим отрицательное, значит всего отрицательных чисел четное количество, и [math]\left(\cfrac{2}{p}\right)=1[/math].