르장드르 기호

르장드르 기호 (Legendre symbol)는 정수론에서 주어진 정수 a가 어떤 소수 p를 법으로 하는 이차 잉여인지 아닌지를 나타내는 기호이다. 여기서 p는 홀수인 소수여야 한다. 르장드르 기호는 다음과 같이 정의된다.

\left(\frac{a}{p}\right) = \begin{cases}
0 & \text{if } p \mid a, \\
1 & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } p \nmid a, \\
-1 & \text{if } a \text{ is a quadratic non-residue modulo } p.
\end{cases}

즉, a가 p의 배수이면 0, a가 p를 법으로 하는 이차 잉여이면 1, 이차 비잉여이면 -1의 값을 갖는다. 여기서 a가 p를 법으로 하는 이차 잉여라는 것은, 어떤 정수 x가 존재하여 x² ≡ a (mod p)를 만족한다는 의미이다.

르장드르 기호는 다음 성질들을 만족한다.

오일러의 기준: (a/p) ≡ a^(p-1)/2 (mod p)
a ≡ b (mod p) 이면 (a/p) = (b/p)
(ab/p) = (a/p)(b/p)
(1/p) = 1
(-1/p) = (-1)^(p-1)/2. 즉, p ≡ 1 (mod 4) 이면 (-1/p) = 1, p ≡ 3 (mod 4) 이면 (-1/p) = -1이다.
(2/p) = (-1)^(p²-1)/8. 즉, p ≡ 1, 7 (mod 8) 이면 (2/p) = 1, p ≡ 3, 5 (mod 8) 이면 (2/p) = -1이다.

르장드르 기호는 이차 상호 법칙과 함께 사용하여 임의의 정수 a에 대해 (a/p) 값을 효율적으로 계산할 수 있게 해준다. 이차 상호 법칙은 서로 다른 홀수 소수 p와 q에 대해 (p/q)(q/p) = (-1)^{((p-1)/2)((q-1)/2)} 로 표현된다. 이는 (p/q) = (q/p) 이거나 (p/q) = -(q/p) 임을 의미하며, p ≡ 1 (mod 4) 또는 q ≡ 1 (mod 4) 이면 (p/q) = (q/p)이고, p ≡ 3 (mod 4) 이고 q ≡ 3 (mod 4) 이면 (p/q) = -(q/p) 이다.

르장드르 기호는 정수론의 여러 분야에서 중요한 역할을 하며, 암호학 등 응용 분야에도 활용된다. 예를 들어, 르장드르 기호를 이용하여 주어진 수가 제곱근을 갖는지 판별하거나, 이차 합동식의 해의 존재 여부를 판단할 수 있다.

📖 WIPIVERSE

르장드르 기호