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

т. е. для простых чисел  вида 8m±1 число 2 является квадратичным вычетом, а для простых чисел вида 8m±3  оно является квадратичным невычетом.

Примеры:  1)Установить, является ли 2 квадратичным вычетом по простому модулю 1097

Так как 1097≡1(mod 8), то 2 является квадратичным вычетом;

2) Разрешимо ли сравнение  x² ≡ 2 (mod 1709), где 1709 простое число?

1709 ≡ 5 (mod 8), поэтому сравнение не разрешимо.

Свойство 6. Закон взаимности нечетных простых чисел.

Если  p и q нечетные простые числа, тогда

 

Доказательство этого  важнейшего утверждения о квадратичных вычетах мы тоже дадим отдельно в  четвертом пункте, здесь же отметим  другое выражение, удобное для практики.

Умножим предварительно обе  части на

Тогда

 

Отсюда видно: если хотя бы одно из чисел p или q имеет форму 4m+1, тогда показатель в правой части равенства четный, поэтому

 

если же как p,  так и q имеет форму 4m+3, тогда показатель степени числа (-1) окажется числом нечетным, и мы будем иметь

 

Пример. Установить, разрешимо  ли сравнение x²≡426(mod 491), где 491 простое число.

Для того чтобы дать ответ  на поставленный вопрос, вычислим символ Лежандра .

Во-первых, разлагаем 426 на множители:

426=2371.

Поэтому, согласно свойству 4,

 

Далее имеем:

так как 491 и 3≡3(mod 4),  а 3≡3(mod 8);

так как 491 и 71≡3( mod 4), 491≡65(mod 71), 5≡1(mod 4), 13≡1(mod 4),     13≡5(mod 8).

Следовательно, другими словами: данное сравнение неразрешимо.

 

 

4. Доказательство 5 свойства символа Лежандра

Чтобы доказать 5 свойство, воспользуемся  полученной формулой

                                     (1)

для символа Лежандра, найдя  предварительно выражение для каждого   в отдельности.

Проанализируем с этой целью, в каком случае и в каком -1.

Начнем с примера.

Для a=5 и x=9 имеем: 59=45≡7≡+17(mod 19); здесь остаток 7 от деления 45 на 19 совпадает с абсолютно наименьшим вычетом 45 по модулю 19, так как поэтому

Одновременно замечаем, что 

 

Для a=5 и x=6 имеем: 56=30≡11≡-18(mod 19); здесь остаток 11 от деления 30 на 19 не совпадает с абсолютно наименьший вычет равен -8, так что одновременно

 

Очевидно, вообще в том и только в том случае, когда при делении ax на p получается остаток ( т. е. когда наименьший положительный вычет ax по модулю   и вместе с тем дробная часть ), и тогда и только тогда, когда указанный остаток (а дробная часть ).

Итак, имеем одновременно:

1. или или и
2. или или и

Для дальнейшего воспользуемся  следующим равенством:

 

 

из чего следует 

 

 

(Пример. Из очевидно, следует

).

Последнее соотношение дает возможность отмеченные в 1) и 2) факты  выразить следующим образом. Имеем  одновременно:

1. число четное и
2. число нечетное и

Таким образом, имеем возможность  представить  в следующем виде:

 

При помощи этого выражения  соотношение (1) переводит в формулу

 

Используя (4), запишем теперь предполагая при этом, что a-нечетное.

Имеем

 

но так как

 

то из предыдущего следует

 

Если теперь в (5) подставить a=1, тогда

 

и мы получаем 5 свойство символа  Лежандра

 

Доказательство закона взаимности

Ввиду 5 свойства, соотношение (5) предыдущего пункта принимает  вид:

 

где a-нечетное число, а

Поэтому для нечетных простых p и q  можем писать

 

 

откуда

 

Так как числа, сравнимые  по  модулю 2 имеют одинаковую четность, то остается доказать, что

 

Покажем, что имеет место  даже равенство указанных выражений. Для этого построим в прямоугольной  системе координат прямоугольник с вершинами О(0,0), А(), B()  и С(0,) и, отметив на сторонах этого прямоугольника ОА и ОС соответственно точки с амбициями x=1,2,…, и ординатами y=1,2,…, найдем число его внутренних целочисленных точек. Сопоставление результатов двух таких подсчетов приведет нас к искомому соотношению.

С одной стороны, считая по рядам и по столбцам, мы сразу  же видим, что число внутренних целочислительных точек равно произведению .

Перейдем теперь к другому  подсчету.

Предварительно заметим, что внутри отрезка ОВ нет целочисленных  точек. На самом деле, уравнение прямой ОВ имеет вид и, когда x пробегает значения 1,2,…,, y не может стать целым числом.

Таким образом, остается подсчитать количество целочисленных точек  внутри треугольников  ОАВ и ОВС.

Прямая x=k через положительную целочисленную абсциссу k пересекает ОВ в точке .  Очевидно, что количество целочисленных точек этой прямой, расположенных над осью Ox и ниже ОВ, равно .

Так как внутри отрезка ОА k может принять только лишь значения 1,2,…,, то число целочисленных точек внутри треугольника OAB равно сумме

 

Рассматривая аналогично прямые  y=l  через положительные целочисленные ординаты l  внутри отрезка ОС, мы найдем, что число целочисленных точек внутри треугольника ОВС  равно сумме

 

Итак, число целочисленных  точек внутри всего прямоугольника ОАВС равно

 

Отсюда следует (ввиду  формулы (2))- закон взаимности

 

Закон взаимности, который  Гаусс справедливо называет «фундаментальной теоремой» о квадратичных вычетах, впервые эмпирически был найден Эйлером в 1772 г. И опубликован им в 178 г. Независимо от Эйлера к этому закону в 1785 г. пришел Лежандр, но и он не сумел еще дать строгого его доказательства.

Впервые закон взаимности был  доказан Гауссом в 1796 г. В  дальнейшем ему удалось найти  еще 6 других доказательств этого закона. После Гаусса  можно насчитать около 50 доказательств, данных  другими учеными. Изложение доказательство дано Эйзенштейном.

 

 

 

 

 

 

 

 

5. Практическая часть.

Пример 1. Вычислить символ Лежандра

 

Пример 2. Вычислить символ Лежандра

 

Пример 3. Вычислить символ Лежандра

 

Пример 4. Вычислением символа  Лежандра установить, какие из следующих  сравнений разрешимы, и найти  их решения:

 

 не имеет  решений.

Пример 5. Вычислением символа Лежандра установить, какие из следующих сравнений разрешимы, и найти их решения:

 

 имеет два  решения 

 

 

Заключение

При больших значениях  модуля p критерием Эйлера неудобно вычислять, является ли a квадратичным вычетом или нет. Эффективный способ в решении этого вопроса получается применением символа, который ввел Лежандр.

Этот символ (читается так: «символ Лежандра a по отношению к p») определяется для нечетных простых p и чисел a, которые не делятся на p; при этом a называется числителем, а p знаменателем символа.

Если a квадратичный вычет по модулю p, тогда символу сопостовляется число +1, т. е. =+1; если a квадратичный невычет по модулю p, тогда символу сопостовляется число -1, т. е. =-1.

 

 

 

 

 

 

 

 

 

 

 

Литература

1. Михелович Ш. Х.  Теория чисел. – М.: Высшая школа, 1962. – 260 с.
2. Грибанов В. У., П. И. Титов Сборник упражнений по теории чисел. – М.: Просвещение, 1964. – 144 с.
3. Нестеренко Ю. В. Теория чисел. – М.: Академия,  2008. – 272 с.
4. Бухштаб А. А. Теория чисел. – М.: Просвещение. 1966. – 379 с.