르장드르 기호
르장드르 기호 (Legendre Symbol) 의 정의는 다음과 같습니다.
홀수 소수 $p$와, $p$와 서로소 인 $a$에 대하여 $a$가 법 $p$에 대한 이차잉여 이면 $\left(\frac{a}{p}\right) = 1$, $a$가 법 $p$에 대한 이차비잉여이면 $\left(\frac{a}{p}\right) = -1$이다.
다음과 같은 성질이 성립합니다.
1. $\left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}{2}} \pmod{p}$ ( 오일러의 규준 )
2. 서로 다른 두 홀수 소수 $p$, $q$에 대하여 $\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{(p - 1) (q - 1)}{4}}$ ( 이차 상호 법칙 )
3. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
4. $a \equiv b \pmod{p}$이면, $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
르장드르 기호를 일반화한 야코비 기호 가 존재합니다.