|
Пусть  - множество натуральных чисел,  и
 множество натуральных чисел, меньших чем  и взаимно простых с .
 называется квадратичным вычетом по модулю , если существует такой  , что
 . В противном случае,
называется квадратичным невычетом по модулю .
Пусть  — целое число, и  — простое число, отличное от  . Символ Лежандра
 определяется следующим образом:
 , если делится на ;
 , если является квадратичным вычетом по модулю , то есть не делится на и существует такое целое  , что
 ;
 , если является квадратичным невычетом по модулю , то есть не делится на p и не является квадратичным вычетом по модулю .
Пусть  — нечётное, большее единицы число и
 — его разложение на простые множители (среди
 могут быть равные). Тогда для произвольного целого числа символ Якоби определяется равенством:
 ,
где
 — символы Лежандра.
По определению считаем, что
 для всех .
Пусть и
. Пусть  знает, что не существует такой , что
. хочет доказать  свое знание, не показывая само доказательство несуществования.
|
