模p平方剩余判断

  • METHOD1: 定理

    pp为奇素数

    • (2p)=(1)p218\left(\frac{2}{p}\right)={\left(-1\right)}^{\frac{p^2-1}{8}}

    • (a,2p)=1\left(a,2p\right)=1,则(ap)=(1)T(a,p)\left(\frac{a}{p}\right)={\left(-1\right)}^{T_{\left(a,p\right)}},其中

  • METHOD2: 二次互反律

    p,qp,q为互素奇素数,则(pq)=(1)p12q12(pq)\left(\frac{p}{q}\right)={\left(-1\right)}^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\frac{p}{q}\right)

最后更新于

这有帮助吗?