二次剩余

定义

设 是奇素数,且 。如果存在整数 满足

就称 是模 的二次剩余;否则是二次非剩余。这里先只讨论非零剩余类。

例如模 的非零平方余数是 ,因为 分别同余于 ,另外三个非零元素的平方重复这些结果。

Euler 判别法

在上述条件下,

若 ,费马小定理给出 。反过来,有限域中多项式 的根至多有 个,而非零平方余数恰有这么多个,因此这些根恰好就是非零二次剩余。

范围

  • 时应单独处理。
  • 、合数模数不直接套用这里的判别式。
  • 判别是否有解与实际求出平方根是两个问题;后者可以继续学习 Cipolla 或 Tonelli–Shanks。

来源与延伸