Символ Якоби

Полезным обобщением символа Лежандра является символ Якоби. Пусть Р - нечетное, большее единицы, и P = p₁p₂…p_r - разложение его на простые сомножители (среди них могут быть и равные).

.

Известные свойства символа Лежандра дают возможность установить аналогичные свойства и для символа Якоби.

Если a ? a₁(mod P), то .

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

,

потому что а, будучи сравнимо с а₁ по модулю Р, будет сравнимо с a₁ и по модулям p₁, p₂, ..., p_r, которые являются делителями Р.

.

В самом деле,

.

.

Чтобы убедиться в этом, заметим, что

;

но

,

ввиду чего из формулы (1) выводим

.

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

;

собирая символы с одинаковыми числителями, мы и получим утверждаемое свойство. Отсюда следствие:

.

.

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

; (2)

но

,

ввиду чего из формулы (2) выводим

.

Если Р и Q - положительные нечетные взаимно простые, то

.

Доказательство: Пусть Q = q₁q₂…q_s есть разложение Q на простые сомножители (среди них опять-таки могут быть равные). Имеем

.

Но, подобно тому, как в d, находим

,

ввиду чего последняя формула дает

.

Рассматривая символ Лежандра как частный случай символа Якоби и пользуясь свойствами последнего, можно вычислить символ Лежандра быстрее, чем с помощью теоремы b, п. 2.

Пример. Узнаем, сколько решений имеет сравнение

х² ? 219 (mod 383).

Имеем (применяя последовательно свойства g, b, следствие е, g, b, е, f, g, b, d):

;

следовательно, рассмотренное сравнение имеет два решения. 4