雅可比符号

定义

设m=p1⋯prm=p_1\cdots p_r是奇素数pip_i的乘积

(am)=(ap1)⋯(apr)\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)\cdots\left(\frac{a}{p_r}\right)

性质

  • 若m=p1⋯prm=p_1\cdots p_r是奇数

    • (a+mm)=(am)\left(\frac{a+m}{m}\right)=\left(\frac{a}{m}\right)

    • (a⋅bm)=(am)(bm)\left(\frac{a\cdot b}{m}\right)=\left(\frac{a}{m}\right)\left(\frac{b}{m}\right)

    • 设(a,m)=1\left(a,m\right)=1，则(a2m)=1\left(\frac{a^2}{m}\right)=1

    • m−12≡p1−12+⋯pr−12(mod  2)\frac{m-1}{2}\equiv \frac{p_1-1}{2}+\cdots\frac{p_r-1}{2}\left(\mod 2\right)

    • m2−12≡p12−12+⋯pr2−12(mod  2)\frac{m^2-1}{2}\equiv \frac{p_1^2-1}{2}+\cdots\frac{p_r^2-1}{2}\left(\mod 2\right)

    • (1m)=1\left(\frac{1}{m}\right)=1

    • (−1m)=(−1)m−12\left(\frac{-1}{m}\right)={\left(-1\right)}^{\frac{m-1}{2}}

    • (2m)=(−1)m2−18\left(\frac{2}{m}\right)={\left(-1\right)}^{\frac{m^2-1}{8}}

  • 若m,nm,n均为奇数

    • (nm)=(−1)m−12⋅n−12(mn)\left(\frac{n}{m}\right)={\left(-1\right)}^{\frac{m-1}{2}\cdot\frac{n-1}{2}}\left(\frac{m}{n}\right)

上一页模p平方剩余判断下一页模平方根

最后更新于

这有帮助吗？