平方剩余

假设p是素数，a是整数。 如果存在一个整数x使得x^2≡a(mod p) （即x^2-a可以被p整除）， 那么就称a在p的剩余类中是平方剩余的。

欧拉定理说：如果p是奇素数，则a平方剩余当且仅当 a^{(p-1)/2}≡1 (mod p).

在{1,2,...,p-1}中恰好有（p-1）/2 个数是平方剩余的。

拉格朗日符号： 【a/p】=1 (相应的，-1) 如果 a是平方剩余(相应的， 如果 a不是平方剩余）。

高斯著名的二次互反律告诉我们：假设p和q是2个不同的奇素数，则

【q/p】*【p/q】=(-1)^{(p-1)*(q-1)/4}.