Квадратичный вычет: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
LGB (обсуждение | вклад) уточнение |
LGB (обсуждение | вклад) Примеры для ясности |
||
Строка 5:
Понятие квадратичного вычета широко применяется в [[теория чисел|теории чисел]], оно также нашло практические применения в [[Акустика|акустике]], [[Криптография|криптографии]] и других прикладных науках.
== Примеры ==
Числа <math>a=0</math> и <math>a=1</math> являются квадратичными вычетами по любому модулю, так как сравнения <math>x^2 \equiv 0 \pmod{m}</math> и <math>x^2 \equiv 1 \pmod{m}</math> всегда имеют решения <math>x=0</math> и <math>x=1</math> соответственно.
''Следствие'': поскольку для модуля <math>m=2</math> существуют только два класса вычетов <math>[0[_2</math> и <math>[1[_2,</math> любое число по модулю 2 является квадратичным вычетом.
По модулю 3 существуют три класса вычетов: <math>[0[_3, [1[_3, [2[_3.</math> Их квадраты попадают в классы вычетов <math>[0[_3, [1[_3, [1[_3</math> соответственно. Отсюда видно, что числа из классов <math>[0[_3</math> и <math>[1[_3</math> являются квадратичными вычетами, и числа из класса <math>[2[_3</math> (например, <math>2, 5, 8, -1, -4\dots</math>) — квадратичные невычеты.
== Свойства ==
* [[Критерий Эйлера]]: Пусть <math>p>2</math> простое. Число a, [[взаимно простые числа|взаимно простое]] с <math>p</math>, является квадратичным вычетом по модулю <math>p</math> тогда и только тогда, когда<ref name=VIN/>:
*: <math>a^{(p-1)/2}\equiv 1\pmod{p},</math>
| |||