르장드르 기호

정의

\(p\)가 3 이상의 소수이고 \(a\)가 \((a,p)=1\)인 정수일 때, 다음 기호

[math]\displaystyle{ \left(\frac{a}{p}\right)=\begin{cases} 1,& (\exists x\in \mathbb{Z})[x^2 = a]\\ -1,& (\forall x\in\mathbb{Z})[x^2\ne a] \end{cases} }[/math]

를 르장드르 기호(Legendre symbol)라고 한다. 즉, \(a\)가 법 \(p\)에 대한 이차잉여이면 \(\left(\frac{a}{p}\right)=1\)이고 그렇지 않으면 \(\left(\frac{a}{p}\right)=-1\)이다.

성질

\(p,q\)가 서로 다른 3 이상의 소수이고 정수 \(a,b\)에 대해 \((a,p)=(b,p)=1\)일 때,

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

\(x=a\)는 합동식 \(x^2\equiv a^2\pmod p\)의 해이므로 자명하다.

• \(a\equiv b \pmod p\)이면 \(\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\)이다.

\(a\equiv b \pmod p\)라고 가정하면 두 합동식 \(x^2\equiv a\pmod p\)와 \(x^2\equiv b\pmod p\)는 동치이므로 원하는 결론을 얻는다.

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

오일러의 규준이라고도 불린다. [math]\displaystyle{ x_1,\ldots. x_{\frac{p-1}{2}} }[/math]를 [math]\displaystyle{ \pmod p }[/math]의 이차잉여라 하자. [math]\displaystyle{ a }[/math]가 이차잉여인 경우 [math]\displaystyle{ \{ax_1,\ldots, ax_{\frac{p-1}{2}} \} }[/math]는 집합으로서 [math]\displaystyle{ \{x_1,\ldots, x_{\frac{p-1}{2}} \} }[/math] 와 일치할 것이다. 따라서 모든 원소의 곱도 일치하고, [math]\displaystyle{ a^{\frac{p-1}{2}} x_1\cdots x_{\frac{p-1}{2}} \equiv x_1\cdots x_{\frac{p-1}{2}} \pmod{p} }[/math]가 성립한다. 양변을 소거하면 오일러의 규준을 얻는다. [math]\displaystyle{ a }[/math] 가 이차잉여가 아닐 경우, [math]\displaystyle{ ax_i }[/math] 들 또한 이차잉여가 아닐 것이고, 마찬가지로 [math]\displaystyle{ ax_i^{-1} }[/math] 또한 이차잉여가 아닐 것이다. 따라서 [math]\displaystyle{ \{x_1,\ldots, x_{\frac{p-1}{2}} \} \cup \{ax_1^{-1} ,\ldots, ax_{\frac{p-1}{2}} ^{-1} \} = \{1,2,\ldots, p-1\} }[/math] 이다. 모든 원소의 곱을 비교하면 [math]\displaystyle{ a^{\frac{p-1}{2}} \equiv (p-1)! \equiv -1 \pmod p }[/math] 를 얻는다. 여기서 마지막 등호는 윌슨의 정리의 결과이다.

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

지수법칙에 의해

[math]\displaystyle{ \begin{align} \left(\frac{ab}{p}\right)&=(ab)^{\frac{p-1}{2}}\\ &=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\\ &=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \end{align} }[/math]

이므로 원하는 결론을 얻는다.

• [math]\displaystyle{ \left(\frac{-1}{p}\right)=\begin{cases} 1,&\text{if }p\equiv 1\pmod 4\\ -1,&\text{if }p\equiv -1\pmod 4 \end{cases} }[/math]
• [math]\displaystyle{ \left(\frac{2}{p}\right)=\begin{cases} 1,&\text{if }p\equiv \pm 1\pmod 8\\ -1,&\text{if }p\equiv \pm 3\pmod 8 \end{cases} }[/math]
• \(p\ge 5\)일 때 [math]\displaystyle{ \left(\frac{3}{p}\right)=\begin{cases} 1,&\text{if }p\equiv \pm 1\pmod{12}\\ -1,&\text{if }p\equiv \pm 5\pmod{12}\\ \end{cases} }[/math]
• \(\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\) (이차상반성)

예시

\(\left(\frac{860}{103}\right)\)의 값을 구해 보자. 103은 소수이고,

[math]\displaystyle{ 860=8\cdot 103 + 36 }[/math]

이므로 \(860 \equiv 36 \pmod{103}\)이다. 따라서

[math]\displaystyle{ \left(\frac{860}{103}\right)=\left(\frac{36}{103}\right) }[/math]

이다. 그런데 \(36=6^2\)이므로

[math]\displaystyle{ \left(\frac{860}{103}\right)=\left(\frac{36}{103}\right)=1 }[/math]

임을 알 수 있다.