르장드르 기호

수론에서 르장드르 기호(Legendre symbol)는 어떤 수가 제곱 잉여인지 아닌지를 나타내는 함수이다.

홀수 소수 ${\displaystyle p}$와 정수 ${\displaystyle a}$에 대하여, 르장드르 기호는 다음과 같다.

${\displaystyle \left({\frac {a}{p}\right)={\begin{cases}1&p\nmid a\land \exists x\in \mathbb {Z} \colon x^{2}\equiv a{\pmod {p}\\-1&p\nmid a\land \not \exists x\in \mathbb {Z} \colon x^{2}\equiv a{\pmod {p}\\0&p\mid a\end{cases}$

즉, ${\displaystyle a}$가 ${\displaystyle p}$에 대한 제곱 잉여일 때 1을, ${\displaystyle a}$가 ${\displaystyle p}$에 대한 제곱 비잉여일 때 -1을, ${\displaystyle a}$가 ${\displaystyle p}$의 배수일 때 0을 값으로 한다. 르장드르 기호는 마치 분수처럼 생겼지만, 분수의 계산과는 관련이 없다.

다음과 같은 항등식들이 성립한다.

${\displaystyle \left({\frac {a}{p}\right)\equiv a^{p(p-1)/2}{\pmod {p}$

${\displaystyle \left({\frac {a}{p}\right)=\left({\frac {p+a}{p}\right)}$

${\displaystyle \left({\frac {ab}{p}\right)=\left({\frac {a}{p}\right)\left({\frac {b}{p}\right)}$

${\displaystyle \left({\frac {a^{2}{p}\right)={\begin{cases}1&p\nmid a\\0&p\mid a\end{cases}$

이들은 제곱 잉여의 성질에 대응한다. 예를 들어, 세 번째 항등식에 따라, 두 제곱 잉여의 곱은 제곱 잉여이다.

만약 ${\displaystyle 2,p\nmid a}$라면, 다음이 성립한다.

${\displaystyle \left({\frac {a}{p}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor ak/p\rfloor }$

 이 부분의 본문은 이차 상호 법칙입니다.

홀수 소수 ${\displaystyle p,q}$가 ${\displaystyle p\neq q}$라고 하자. 그렇다면, 다음이 성립한다.

${\displaystyle \left({\frac {p}{q}\right)={(-1)^{(p-1)(q-1)/4}\left({\frac {q}{p}\right)}$

이를 이차 상호 법칙이라고 한다. 즉, ${\displaystyle p}$와 ${\displaystyle q}$는

${\displaystyle p\equiv q\equiv 3{\pmod {4}$

인 경우를 제외하면 서로에 대한 제곱 잉여이거나, 서로에 대한 제곱 비잉여이다.

작은 정수의 홀수 소수 ${\displaystyle p}$에 대한 르장드르 기호는 다음과 같다.

${\displaystyle \left({\frac {1}{p}\right)=1}$

${\displaystyle \left({\frac {-1}{p}\right)=(-1)^{(p-1)/2}$

${\displaystyle \left({\frac {2}{p}\right)=(-1)^{(p^{2}-1)/8}$

야코비 기호는 르장드르 기호를 소수에서 임의의 홀수까지 확장하며, 크로네커 기호는 이를 임의의 짝수에까지 확장한다.

프랑스의 수학자 아드리앵마리 르장드르가 도입하였다.