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

Пусть р- простое, а < р, р>2.
Определение 1. а – квадратичный вычет  .
Пример 1.  Пусть р = 7, тогда 1, 2, 4 – квадратичные вычеты, а 3, 5, 6 – не квадратичные вычеты:
 (mod 7)
Теорема 1. Существует   квадратичных вычетов и  не квадратичных вычетов в GF(p). У каждого квадратичного вычета существуют два корня  такие, что , где  называется основным корнем.
Д о к а з а т е л ь с т в о.  При  следовательно, уравнение  = x имеет не менее двух корней. Если , то

Тогда или   -(n) или   (n). Отсюда   имеет ровно два значения корня квадратного или ни одного. Ровно половина ненулевых элементов GF(p) есть квадратичные вычеты.
Теорема 2. Если n = p  q, где p, q – простые, то  квадратичных вычетов по modn  и у каждого квадратичного вычета 4 корня.
Пример 2.  n = 35 = 5  7  квадратичных вычетов по 
mod 35: 1, 4, 9, 11, 16, 29. Каждый квадратичный вычет имеет ровно 4 корня.
Определение 2. Для целого а и простого p>2 символ Лежандра определяется следующим образом:
L(a, p) = 0, если р/а;
L(a, p) = 1, если а- квадратичный вычет по mod p;
L(a, p) = -1, если а- не квадратичный вычет по mod p.
Теорема 3. L(a, p) =  .
Д  о к а з а т е л ь с т в о.
1.	.
2.	а- квадратичный вычет, то есть . Тогда по теореме Ферма 
.
Таких a ровно . Рассмотрим уравнение
.
Любое а – его корень. Отсюда каждое a является корнем одного из сомножителей в следующем уравнении:
.
Значит,  значений квадратичных вычетов а являются корнями уравнения
.
Тогда по основной теореме алгебры остальные а, не являющиеся квадратичными вычетами, являются корнями уравнения
.
Если а- не квадратичный вычет, тогда 
       .
Теорема доказана.
Определение 3. Пусть р- простое, g < p. g называется примитивным элементом мультипликативной группы поля GF(p) (или примитивным элементом по mod p), если  0 < n   p-1    a:  .
Пример 3.  При p = 11, 2 есть примитивный мультипликативной группы GF(11).

Каждое число  n(1; 10) может быть представлено в виде .
Для р = 11 числа 2, 6,7,8 являются примитивными элементами мультипликативной группы GF(11). Остальные не являются примитивными элементами.
Замечание. В GF(p) (p-1) примитивных элементов.
Нахождение примитивного элемента, вообще говоря, не является простой задачей. Примитивный элемент находится легко, если известна факторизация р-1. Пусть - простые множители р-1. Для того чтобы проверить, является ли g примитивным элементом по mod p, вычисляется . Если для некоторого i это число равно 1, то g- не примитивный элемент. Если это не выполняется ни для какого , то g- примитивный элемент.
Пример 4. При р = 11 имеем  р - 1 = 10 = 2  5.  Проверим, что число 2 является примитивным элементом мультипликативной группы GF(11).

следовательно, 2 – примитивный элемент. Проверим 3.

следовательно, 3 не примитивный элемент мультипликативной группы GF(11).