勒让德符号

由欧拉判别法可以知道有

(\frac{a}{p}) \equiv a^{(p - 1) /2} (m o d p)

(\frac{1}{p}) = 1

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2}

如果 $a \equiv b (m o d p)$ ，则有

(\frac{a}{p}) = (\frac{b}{p})

(\frac{a + p}{p}) = (\frac{a}{p})

如果 $(a, p) = 1$

(\frac{a ^{2}}{p}) = 1

(\frac{a _{1} a _{2} \dots a _{n}}{p}) = (\frac{a _{1}}{p}) (\frac{a _{2}}{p}) \dots (\frac{a _{n}}{p})

(\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8} = {1 - 1 p \equiv \pm 1 (m o d 8) p \equiv \pm 3 (m o d 8)

如果 p，q 都是奇素数， $(p, q) = 1$

(\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) /4} (\frac{p}{q})

🪴 Cyril