Означення і властивості символу Лежандра.

Квадратичний закон взаємності Гаусса. Символи Лежандра і Якобі.

Важлива теорема.

Первісний корінь у кільці лишків за модулем .

Умова розв'язності степеневої конгруенції

Покажемо, що розв'язуваністьконгруенції еквівалентна виконанню умови,де.

Перехід до індексів показує, що . Необхідна і достатня умова розв’язності останньої конгруенції полягає в тому, щоб ділився на , тобто .

Домножуючи модуль і обидві частини останньої конгруенції на , одержимо «рівність показників»: . Піднесення у відповідні степені показує, що умова еквівалентна умові .

Наслідок 1. (критерій Эйлера).Розв’язність конгруенції еквівалентна виконанню умови .

Наслідок 2.Нехай - примітивний елемент поля . Тоді квадратичний лишок в тому і тільки тому випадку, коли в представленні число -парне.

Дійсно, якщо , те дискретне логарифмування дає , де модуль парний, отже, ділиться на два.

Відомо, що в кільці лишків за модулем (яке не є полем) існує т.зв. первісний елемент , степені якого представляють усі лишки, взаємно прості з модулем. Ці лишки утворюють в мультиплікативну групу з елементів.

Можна показати, що якщо - первісний корінь у полі , то одне з чисел , де , задовольняє умові і є первісним коренем при будь-якому модулі виду , . Пари чисел a, , для яких виконується співвідношення , зустрічаються рідко. Тому у багатьох випадках первісний модуль за модулем є одночасно первісним елементом для всіх кілець .

Простий вид первісного кореня в кільці лишків за модулем дозволяє звести розв’язування порівняння виду до розв’язування порівняннь за дільниками виду . Виявляється, якщо відомі розв’язки за модулем , то розв’язки за модулем знайти досить просто. Остаточні розв’язки (за модулем ) знаходиться з допомогою китайської теореми про залишки.

Можна показати, що для многочлена від однієї змінної з коефіцієнтами з , кількість коренів, що належать , не перевищує степеня многочлена.

Існують алгоритми для визначення, чи є дане число квадратичним лишком за простим модулем чи ні. Один з алгоритмів позв'язаний з обчисленням значення т.зв. символу Лежандра, якій для непарного простого визначається так:

Значення називається квадратичним характером числа за простим модулем.

Основні властивості символу Лежандра.

;

Критерій Ейлера: ;

;

;

, ;

.

Квадратичний закон взаємності Гаусса: для будь-яких простих непарних чисел і виконується рівність . Символ Лежандра можна обчислити за допомогою наступної послідовності дій.

(1) Якщо , те виділяємо співмножник ;

(2) приводимо за модулем ;

(3) розкладаємо в добуток ступенів простих чисел, використовуючи мультипликативность символу Лежандра: , потім видаляємо співмножники які є квадратами;

(4) виділяємо двійки, наприклад, якщо , обчислюємо ;

(5) для кожного непарного співмножника застосовуємо квадратичний закон взаємності (зменшуємо величини чисел, що беруть участь в обчисленнях,);

(6) при необхідності, переходимо до п.(1).

Приклад.

При використанні ЕОМ, звичайно застосовується критерій Ейлера.