(+)분류 : 가져온 문서/오메가
Legendre Symbol
이차 잉여를 이용하여 정의되는 일종의 수론적 함수이다. 이차 잉여 여부를 수치로 나타냈다고 보면 된다.
1. 정의 ✎ ⊖
자연수 n과 홀소수 p에 대하여,
\\left(\\frac{n}{p}\\right)=\\begin{cases} 1 & \\text{if}\\ \\exists x \\in \\mathbb{Z}\\ \\text{such that}\\ x^2 \\equiv n\\ (\\text{mod}\\ p) \\ -1 & \\text{if}\\ \\nexists x \\in \\mathbb{Z}\\ \\text{such that}\\ x^2 \\equiv n\\ (\\text{mod}\\ p) \\ 0 & \\text{if}\\ p|n \\end{cases}
(n|p)로 표기하기도 한다.
\\left(\\frac{n}{p}\\right)=\\begin{cases} 1 & \\text{if}\\ \\exists x \\in \\mathbb{Z}\\ \\text{such that}\\ x^2 \\equiv n\\ (\\text{mod}\\ p) \\ -1 & \\text{if}\\ \\nexists x \\in \\mathbb{Z}\\ \\text{such that}\\ x^2 \\equiv n\\ (\\text{mod}\\ p) \\ 0 & \\text{if}\\ p|n \\end{cases}
(n|p)로 표기하기도 한다.
2. 성질 ✎ ⊖
- (n^2|p)=1\\ (p \\nmid n)
- (1|p)=1
- (ab|p)=(a|p)(b|p)
- 즉 르장드르 기호는 완전히 곱셈적이다.
- (-1|p)=(-1)^{\\frac{p-1}{2}}
- (2|p)=(-1)^{\\frac{p^2-1}{8}}
2.1. 증명 ✎ ⊖
- (-1|p)=(-1)^{\\frac{p-1}{2}}
- (2|p)=(-1)^{\\frac{p^2-1}{8}}
- \\begin{aligned}p-1 &\\equiv 1(-1)^{1}\\ (\\text{mod}\\ p) \\\\2 &\\equiv 2(-1)^{2}\\ (\\text{mod}\\ p) \\\\p-2 &\\equiv 3(-1)^{3}\\ (\\text{mod}\\ p) \\\\\\vdots \\\\a &\\equiv \\frac{p-1}{2}(-1)^{\\frac{p-1}{2}}\\ (\\text{mod}\\ p)\\ (a=\\frac{p-1}{2}\\ \\text{or}\\ \\frac{p+1}{2})\\end{aligned}
- \\prod_{i=1}^{\\frac{p-1}{2}}2i \\equiv \\left(\\frac{p-1}{2}\\right)!(-1)^{\\sum_{i=1}^{\\frac{p-1}{2}}i}
- 2^{\\frac{p-1}{2}} \\left(\\frac{p-1}{2}\\right)! \\equiv \\left(\\frac{p-1}{2}\\right)!(-1)^{\\frac{p^2-1}{8}}
- \\therefore (2|p) \\equiv 2^{\\frac{p-1}{2}} \\equiv (-1)^{\\frac{p^2-1}{8}}
2.2. 오일러의 판정법 ✎ ⊖
(n|p) \\equiv n^{\\frac{p-1}{2}}\\pmod{p}
2.3. 가우스의 보조정리 ✎ ⊖
홀소수 p에 대하여 p \\nmid n일 때 {n\\ell\\ \\operatorname{mod} p\\ |\\ \\ell=1,2,\\cdots,\\frac{p-1}{2}}의 원소 중 \\frac{p}{2}보다 큰 것의 개수를 m이라 하자. 이 때, (n|p)=(-1)^m이다.
2.4. 이차 상반법칙 ✎ ⊖
(p|q)(q|p)=(-1)^{\\frac{(p-1)(q-1)}{4}}