Legendre Symbol

르장드르 기호(Legendre Symbol)은 이차잉여 여부를 판별하는 기호로 홀수인 소수 p와 정수 a에 대해 다음과 같이 정의 합니다.

정의.1

홀수의 소수를 p라 두면, Legendre Symbol은  다음과 같이 정의 된다.

 

예제 1. x² ≡ a (mod 7)에서 Legendre Symbol ( a / 7 )

x = 1 ~ 6 입력한 계산값.

▷ 1² ≡ 1 (mod 7)

▷ 2² ≡ 4 (mod 7)

▷ 3² ≡ 2 (mod 7)

▷ 4² ≡ 2 (mod 7)

▷ 5² ≡ 4 (mod 7)

▷ 6² ≡ 1 (mod 7)

 

a = 1, (1/7) = 1, → QR,

a = 2, (2/7) = 1, → QR,

a = 3, (3/7) = -1, → NQR

a = 4, (4/7) = 1, → QR,

a = 5, (5/7) = -1, → NQR

a = 6,  (6/7) = -1, → NQR

 

∴ 이차 잉여류 판별은 다음과 같다. 

• 이차 잉여류(QR) : (1/7) = (2/7) = (4/7) = 1 
• 이차 비잉여류(NQR): (3/7) = (5/7) = (6/7) = -1 

Legendre Symbol 특성 ( p는 홀수 소수)
1) (1/ p) = 1	(1/p)는 항상 1이다.
2) (a·b / p) = (a /p)·(b /p)	두 수 a와 b에 곱셈 성질 성리
3) (a2 / p) = 1	a2은  항상 이차잉여
4) ① (-1 / p) = +1, 만약 p ≡ 1 (mod 4)     ② (-1 / p) =  -1, 만약 p ≡ 3 (mod 4)	p가 4로 나눈 나머지에 따라 이차잉여 결정
5) ① (2 / p) = +1, 만약 p ≡ ±1 (mod 8)     ② (2 / p) =  -1, 만약 p ≡ ±3 (mod 8)	p가 8로 나눈 나머지에 따라 이차잉여 결정

 

예제 2. p = 7에 대해 특성 적용

1) (1/ p) = 1

   → a = 1일때, (1/ 7) = 1

2) (a·b / p) = (a /p)·(b /p)

  → a = 2,  b = 3일때, ( 2·3 / 7) = (2/ 7)·(3/ 7) = (1)·(-1) = -1

  → a = 3,  b = 5일때,  (3·5 / 7) = (1 /7) = 1,  (3/ 7)·(5/ 7) = (-1)·(-1) = 1

3) (a² / p) = 1

  → a² = { 1 ² , 2 ² , 3 ² , 4 ² , 5 ² , 6 ² } = { 1, 2, 4 }

  → 임의의 a²는 항상 1,

4) (-1/ p)

  → 7  ≡ 3 (mod 4), 여기서 (-1/ 7) = -1

5) (2/ p)

  → p ≡  1 (mod 8) 또는 p ≡ -1 (mod 8)에서  p = 7은 p ≡ -1 (mod 8)

  → (2/ 7) = +1

.