Сравнения второй степени

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:18, 14 мая 2016.

Основные определения и утверждения

(уравнение Пелля)

Пусть - решение, , это уравнение может и не иметь решений по .

Чтобы решение по было: НОД

Значит надо уметь решать двучленные уравнения

Критерий Эйлера

TemplateTheoremIcon.svg Теорема Критерий Эйлера

имеет решения - 2 решения - 0 решений

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

Необходимость:

- решение - тоже решение, т.к.

Если , то

реш.

Если возведем уравнение первой степени в степень, то получим

Достаточность:

Рассмотрим

Утверждаем, что среди них различны только половина, т.к. и - одно и то же.

, в этом ряду выполнено соотношение , что невозможно. Поэтому если - из множества, то два решения, иначе - решений нет.


Теорема Эйлера

TemplateDifinitionIcon.svg Определение «Определение»

Число называется квадратичным вычетом по модулю p:

, если имеет решения, называется квадратичным вычетом, если

TemplateDifinitionIcon.svg Определение «Теорема Эйлера»

Произведение двух квадратичных вычетов или двух квадратичных невычетов есть вычет, произведение вычета по невычету есть невычет.

при одинаковых знаках даст +1, при различных -1.

Символ Лежандра

TemplateDifinitionIcon.svg Определение «Символ Лежандра»

Свойства символа Лежандра

  1. . Следствие:

Закон взаимности

TemplateDifinitionIcon.svg Определение «Закон взаимности»

1783г. Эйлер (без док-ва),

1785г. Лежандр (неправильное док-во),

1796г. Гаусс

TemplateExampleIcon.svg Пример Пример

(по свойству 5)
(первое равенство - из закона взаимности, второе - из свойства 5)


Пусть дано уравнение . Имеет ли оно решение?

Алгоритм проверки:

  1. - это и есть решение
или

Теорема Рабина

TemplateTheoremIcon.svg Теорема Теорема (Rabin)

Задача решения

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

Необходимость:

Примечание: на данный момент в курсе даны методы решения только для специального вида, в общем случае используется метод Берлекемпа.

Достаточность:

НОД

На этом принципе основана криптосистема Рабина.