Символ Якоби

Символ Якоби — это обобщение легендровского символа, которое используется в теории квадратичных вычетов и в алгоритмах проверки простоты. Для нечётного положительного целого числа n с разложением на простые множители $n=\prod_{i=1}^k p_i^{e_i}$ символ Якоби определяют через произведение соответствующих легендровских символов $\left(\frac{a}{n}\right)=\prod_{i=1}^k\left(\frac{a}{p_i}\right)^{e_i}$. В отличие от легендровского символа, определённого только для простых модулей, символ Якоби задаётся для произвольных нечётных модулей; при этом он принимает лишь три возможных значения $\left(\frac{a}{n}\right)\in\{-1,0,1\}$ и равен нулю тогда и только тогда, когда a и n имеют общий простой делитель.

Символ Якоби обладает важными алгебраическими свойствами, которые делают его удобным инструментом в вычислениях и теории чисел. В частности, он мультипликативен по числителю и знаменателю, что записывают формулой $\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$. Существуют также аналоги закона взаимности для Якоби-символа: для двух взаимно простых нечётных чисел m и n действует соотношение, сходное с квадратичной взаимностью, в форме $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}$. Частный случай для аргумента 2 даёт простую формулу вычисления символа при базе 2: $\left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}$. Эти свойства используются в алгоритмах факторизации и тестах на квадратичность, а также при упрощении выражений вида символа Якоби для быстрого вычисления его значения.