二次剩余
定义
设 p 是奇素数,且 a≡0(modp)。如果存在整数 x 满足
x2≡a(modp),
就称 a 是模 p 的二次剩余;否则是二次非剩余。这里先只讨论非零剩余类。
例如模 7 的非零平方余数是 1,2,4,因为 12,22,32 分别同余于 1,4,2,另外三个非零元素的平方重复这些结果。
Euler 判别法
在上述条件下,
a(p−1)/2≡{1−1a 是二次剩余,a 是二次非剩余.(modp)
若 a≡x2,费马小定理给出 a(p−1)/2≡xp−1≡1。反过来,有限域中多项式 X(p−1)/2−1 的根至多有 (p−1)/2 个,而非零平方余数恰有这么多个,因此这些根恰好就是非零二次剩余。
范围
- a≡0 时应单独处理。
- p=2、合数模数不直接套用这里的判别式。
- 判别是否有解与实际求出平方根是两个问题;后者可以继续学习 Cipolla 或 Tonelli–Shanks。
来源与延伸