Закрыть

Квадратичные вычеты

Автор: Васин Алексей
Опубликовано 11.04.2012 в 09:51
Раздел: Теория чисел
Теги:

Пусть $p$ - простое нечетное число. Тогда число $a$, такое, что $GCD(a, p)=1$, называется вычетом степени $n$, если   $\exists(x):x^{n}\equiv a ~mod~{p}.$

В обратном случае число $a$ называется невычетом степени $n$. При $n=2$ вычет (невычет) $a$ называется квадратичным, при $n=3$ - кубическим, а при $n=4$ - биквадратичным. При $n=2$ слово квадратичный опускают и называют $a$ просто вычетом (невычетом).

Рассмотрим группу $\mathbb{Z}_{p}^{*}=\{1, 2, ... , p-1\}$ с заданной операцией умножения по модулю $p$. Элементы, являющиеся квадратами какого-то числа в $\mathbb{Z}_{p}^{*}$, - вычеты.

Примеры:

Пусть $p=7$, $\mathbb{Z}_{p}^{*}=\{1, 2, 3, 4, 5, 6\}$.

$1^{2}=1  ~mod~{7},$

$2^{2}=4  ~mod~{7},$

$3^{2}=2  ~mod~{7},$

$4^{2}=2  ~mod~{7},$

$5^{2}=4  ~mod~{7},$

$6^{2}=1  \pmod{7}.$

Числа $1,2,4$ будут являться квадратичными вычетами, а числа $3,5,6$ - квадратичными невычетами.

Утверждение 1. В $\mathbb{Z}_{p}^{*}$ существует ровно $\frac{p-1}{2}$ квадратичных вычетов, сравнимых с числами: $1^2, 2^2,...,\frac{p-1}{2}^2$.

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

Сначала покажем, что приведенный список чисел содержит квадраты всех элементов из $\mathbb{Z}_{p}^{*}$.

Это становится очевидно, если представить $\mathbb{Z}_{p}^{*}$ как     $\{-\frac{p-1}{2},..., -2, -1, 1, 2, ...,\frac{p-1}{2}\}$.

Теперь пусть $\exists i, j\in \mathbb{Z}_{p}^{*}: i^2\equiv j^2 ~ mod ~ {p},  0<i<j\leq\frac{p-1}{2}$. Тогда сравнению $x^2\equiv i^2 ~mod~{p}$ удовлетворяло бы 4 корня: $x=\pm i, \pm j$, чего быть не может, а значит все     числа из списка $1^2, 2^2,...,\frac{p-1}{2}^2$ различны по модулю $p$.

Таким образом, приведенный список $1^2, 2^2,...,\frac{p-1}{2}^2$ состоит из $\frac{p-1}{2}$ различных по модулю $p$ чисел, представляющих все вычеты в группе $\mathbb{Z}_{p}^{*}$.

Утверждение 2. Если $\mathbb{Z}_{p}^{*}=\{1, \theta, \theta^{2},..., \theta^{p-2}\}$, где $\theta$ - порождающий элемент, то справедливо следующее: $a=\theta^{j}$ - квадратичный вычет  $\Leftrightarrow$ $j$ - четное.

Пусть $a=\theta^{j}$ - квадратичный вычет. Тогда $\exists x: x^{2}\equiv a ~ mod ~{p}$.

Так как $\theta$ - порождающий элемент, значит $\exists i: x=\theta^{i}$, откуда следует, что $\theta^{2i}=\theta^{j}$, то есть \textit{j} - четное.

В обратную сторону, пусть $j$ - четное. Тогда $j=2i$ для некоторого $i$, то есть     $a=\theta^{2i}$. Это значит, что $\exists x=\theta^{i}: x^{2}\equiv a ~ mod ~ {p}$, то есть $a$ - квадратичный вычет.

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей