+
편집 토론 역사 역링크 설정

르장드르 기호

최근 수정 시각 : 2023-04-29 20:35:15 | 조회수 : 41
Legendre Symbol

이차 잉여를 이용하여 정의되는 일종의 수론적 함수이다. 이차 잉여 여부를 수치로 나타냈다고 보면 된다.

목차

1. 정의
2. 성질
2.1. 증명
2.2. 오일러의 판정법
2.3. 가우스의 보조정리
2.4. 이차 상반법칙
3. 영상

1. 정의 ✎ ⊖

자연수 nn과 홀소수 pp에 대하여,

(np)={1if ∃x∈Z such that x2≡n (mod p) −1if ∄x∈Z such that x2≡n (mod p) 0if p∣n\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)(n|p)로 표기하기도 한다.

2. 성질 ✎ ⊖

  • (n2∣p)=1 (p∤n)(n^2|p)=1\ (p \nmid n)
  • (1∣p)=1(1|p)=1
  • (ab∣p)=(a∣p)(b∣p)(ab|p)=(a|p)(b|p)
  • 즉 르장드르 기호는 완전히 곱셈적이다.
  • (−1∣p)=(−1)p−12(-1|p)=(-1)^{\frac{p-1}{2}}
  • (2∣p)=(−1)p2−18(2|p)=(-1)^{\frac{p^2-1}{8}}

2.1. 증명 ✎ ⊖

  • (−1∣p)=(−1)p−12(-1|p)=(-1)^{\frac{p-1}{2}}
오일러의 판정법에 의해 자명하다.
  • (2∣p)=(−1)p2−18(2|p)=(-1)^{\frac{p^2-1}{8}}
  • p−1≡1(−1)1 (mod p)2≡2(−1)2 (mod p)p−2≡3(−1)3 (mod p)⋮a≡p−12(−1)p−12 (mod p) (a=p−12 or p+12)\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}
  • ∏i=1p−122i≡(p−12)!(−1)∑i=1p−12i\prod_{i=1}^{\frac{p-1}{2}}2i \equiv \left(\frac{p-1}{2}\right)!(-1)^{\sum_{i=1}^{\frac{p-1}{2}}i}
  • 2p−12(p−12)!≡(p−12)!(−1)p2−182^{\frac{p-1}{2}} \left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)!(-1)^{\frac{p^2-1}{8}}
  • ∴(2∣p)≡2p−12≡(−1)p2−18\therefore (2|p) \equiv 2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p^2-1}{8}}

2.2. 오일러의 판정법 ✎ ⊖

(n∣p)≡np−12(modp)(n|p) \equiv n^{\frac{p-1}{2}}\pmod{p}

2.3. 가우스의 보조정리 ✎ ⊖

홀소수 pp에 대하여 p∤np \nmid n일 때 nℓ mod⁡p ∣ ℓ=1,2,⋯ ,p−12{n\ell\ \operatorname{mod} p\ |\ \ell=1,2,\cdots,\frac{p-1}{2}}의 원소 중 p2\frac{p}{2}보다 큰 것의 개수를 mm이라 하자. 이 때, (n∣p)=(−1)m(n|p)=(-1)^m이다.

2.4. 이차 상반법칙 ✎ ⊖

(p∣q)(q∣p)=(−1)(p−1)(q−1)4(p|q)(q|p)=(-1)^{\frac{(p-1)(q-1)}{4}}

3. 영상 ✎ ⊖



이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.