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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

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

;

;

,;

.

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

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

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

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

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

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

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

Приклад.

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

Дата добавления: 2014-10-15