합성수 n에 대하여 이차잉여의 성질을 일반화한 것으로 Legendre 확장형으로 아래와 같은 정의한다.
| 정의.1 |
| 합성수 n = ∏(pi)ei (i = 1, 2, ... k) 홀수인 양의 정수이고, 최대공약수 (a, n) = 1을 만족하는 a가 있다고하면 Jacobi Symbol (a/n)는 다음과 같이 정의 된다. (a/n) = (a/p1)e1.(a/p2)e2 ... (a/pk)ek (i = 1, 2, ... k) 여기서, (a/pk)는 Legendre Symbol이다. |
※ Legendre 성질을 그대로 만족하지만, (a/n)=1이라고해서 x2 ≡ a mod n이 해를 갖는다고 할 수 없다.
| 정리.1 |
| m과 n을 홀수의 정수라고 두자. Jacobi Symbol은 다음과 같은 성질이 있다. 1) (a/n) = ((a-n) /n) 2) (u·v/ n) = (u/n)·(v/n) 3) (u/m·n) = (u/m)·(u/n) 4) ① (-1/ n) = 1, 만약 n ≡ 1 (mod 4) ② (-1/ n) = -1, 만약 n ≡ 3 (mod 4) 5) ① ( 2/ n) = 1, 만약 n ≡ ±1 (mod 8) ② ( 2/ n) = -1, 만약 n ≡ ±3 (mod 8) |
.
| 정리.2 |
| 6) m과 n이 홀수의 서로소 정수일때, (m/n)·(n/m) = (-1){(m-1)(n-1)/4} |
예제 1. m = 5, n = 7 일때, Jacobi Symbol 정리 예제.
1) (a/n) = ((a - n) /n)
→ 임의 값 a = 9 일때, (9/7) = ((9-7) /7) = (2/7) = 1,
2) (u·v/ n) = (u/n)·(v/n)
→ 임의값 u = 3, v =4 일때,
→ 좌변: (3·4/ 7) = (12/7) = (5/7) = -1
→ 우변: (3/7)·(4/7) = (-1)·(1) = -1
3) (u/m·n) = (u/m)·(v/n)
→ x^2 = { 12, 22, 32, 42 } (mod 5 ), QR = { 1, 4 }, NQR = { 2, 3 }
→ 임의값 u = 3 일때, (3/ 5·7) = (3/ 35) = (3/5)·(3/7) = (-1)·(-1) = 1
4) (-1/ n)
→ n = 7 일때, 7 ≡ 3 (mod 4)이므로 n =3, (-1/7) = -1
5) (2/ n)
→ n = 7 일때, n ≡ -1 (mod 8)이므로 (2/7) = 1
6) (m/n)·(n/m) = (-1){(m-1)(n-1)/4}
→ (5/7)·(7/5) = (-1){(5-1)(7-1)/4} = 1