20
правок
Изменения
Нет описания правки
<tex>\left(\cfrac{m}{n}\right)=\prod^s_{i=1}\left(\cfrac{m}{p_i}\right)=\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{q_j}{p_i}\right)=\prod^s_{i=1}\prod^r_{j=1}(-1)^{\frac{p_i-1}{2}\frac{q_j-1}{2}}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\sum^r_{j=1}\frac{p_i-1}{2}\frac{q_j-1}{2}}\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\left(\frac{p_i-1}{2}\sum^r_{j=1}\frac{q_j-1}{2}\right)}\prod^s_{i=1}\prod^r_{j=1}\left(\cfrac{p_i}{q_j}\right)=(-1)^{\sum^s_{i=1}\left(\frac{p_i-1}{2}\frac{m-1}{2}\right)}\prod^r_{j=1}\left(\cfrac{n}{q_j}\right)=(-1)^{\frac{m-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{m}\right)</tex>
}}
===Алгоритм вычисления символа Якоби===
Для вычисления символа Якоби <tex>\left(\cfrac{a}{n}\right)</tex> эффективно использовать следующий алгоритм:
#Если <tex>a<0</tex>, то применяя утверждения 2 и 5, получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{-a}{n}\right)\times(-1)^{\frac{n-1}{2}}</tex>. Вычисляем <tex>\left(\cfrac{-a}{n}\right)</tex> и пропускаем последующие пункты.
#Если <tex>a</tex> четно, то применяя утверждения 2 и 6, получаем <tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a/2}{n}\right)\times(-1)^{\frac{n^2-1}{8}}</tex>. Вычисляем <tex>\left(\cfrac{a/2}{n}\right)</tex> и пропускаем последующие пункты.
#Если <tex>a=1</tex>, то применяя утверждение 5 <tex>\left(\cfrac{a}{n}\right)=1</tex>, вычисление закончилось.
#Если <tex>a<n</tex>, то применяя теорему 2 получаем <tex>\left(\cfrac{a}{n}\right)=(-1)^{\frac{a-1}{2}\frac{n-1}{2}}\left(\cfrac{n}{a}\right)</tex>. Вычисляем <tex>\left(\cfrac{n}{a}\right)</tex> и пропускаем последующие пункты.
#<tex>\left(\cfrac{a}{n}\right)=\left(\cfrac{a\mod n}{n}\right)</tex>. Вычисляем <tex>\left(\cfrac{a\mod n}{n}\right)</tex>. Пирменяем алгоритм для каждого символа Якоби, который необходимо вычислить.
[[Категория: Теория чисел]]
