[정수론](-)[르장드르, 야코비 기호의 계산]

 

르장드르 기호

p = 홀수 소수일때

• 합동으로 계산
  (kp+r/p) = (r/p)
• (a/p) = (a-p/p)
  이건 특히 큰 수에서 인수분해가 힘들 때 숫자를 줄일 수 있다.
• 제곱은 언제나 1
  (a^2/p) = (a/p)*(a/p)이므로
  (a/p)값에 상관 없이 항상 값이 1이 나온다.
• 이차상호법칙
  • 이차상호법칙 - 1
    홀수 소수 p에 대해 (-1/p)는
    p ≡ 1 (mod 4) 일때 1
    p ≡ 3 (mod 4) 일때 -1
  • 이차상호법칙 - 2
    홀수 소수 p에 대해 (2/p)는
    p ≡ 1 or 7 (mod 8) 일때 1
    p ≡ 3 or 5 (mod 8) 일때 -1
  • 이차상호법칙 - 3
    홀수 소수 p, q에 대해 (q/p)는
    p ≡ 1 (mod 4) or q ≡ 1 (mod 4) 일때 (p/q)
    p, q ≡ 3 (mod 4) 일때 -(p/q)

 

야코비 기호

르장드르 기호가 홀수 소수 p에 대해서만 정의되었지만
야코비 기호는 더 확장해 홀수인 합성수에서도 르장드르 기호를 정의한다.

n = p1p2...pr (단, n은 홀수이므로 p들도 홀수 소수)
(a/n) = (a/p1)(a/p2)...(a/pr)로 정의한다

• 야코비 기호에서도 곱셈법칙을 적용할 수 있다.
  (ab/n) = (ab/p1)(ab/p2)...(ab/pr)
  = (a/p1)(a/p2)...(a/pr)(b/p1)(b/p2)...(b/pr) = (a/n)(b/n)
• 야코비 기호에서도 이차상호법칙을 사용할 수 있다.
  그러나 뒤집기 (a/b) = ±(b/a)는 a가 양수인 홀수여야 성립 가능하다.
  -> 곱셈법칙을 통해 (a/b) = (2/b)(a'/b), (a/b) = (-1/b)(a'/b)로 바꿔 2, -1을 없애고 계산!

예) (24/35)의 계산
    (24/35) = (2^3/35)*(3/35) (곱셈법칙)
    = (2/35)*(3/35) (제곱은 어짜피 1임)
    = (2/5)*(2/7)*(3/5)*(3/7) (야코비 기호의 정의)
     = (-1)*(1)*(-1)*(-1)
     = -1

예) (31706/43789)의 계산
     (31706/43789) = (31706 - 43789/43789) = (-12083 / 43789)
     = (-1/43789) * (12083/43789)
     43789 ≡ 1 (mod 4)이므로,
          (-1/43789) = 1
          (12083/43789) = (43789/12083) = (7540/12083)
     =(-4543/12083) = (-1/12083) * (4543/12083)
     = (-1/12083) * (4543/12083)
     12083 ≡ 3 (mod 4), 4543 ≡ 3 (mod 4)이므로,
          (-1/12083) = -1
          (4543/12083) = -(12083/4543)
     = (12083/4543) = (2997/4543) = (3^3*111/4543)
     = (3/4543)*(111/4543)
     3 ≡ 3 (mod 4), 111 ≡ 3 (mod 4), 4543 ≡ 3 (mod 4)이고, 각각 다 홀수인 정수이므로,
          (3/4543) = -(4543/3) = -(1/3) = -1
          (111/4543) = -(4543/111) = -(103/111)
     = (103/111)
     = (-8/111) = (-1/111)*(2^3/111) = (-1/111)*(2/111)
     111 ≡ 3 (mod 4), 111 ≡ 7 (mod 8)이므로,
          (-1/111) = -1
          (2/111) = 1
     = -1