이차상호법칙

1. 개요[편집]

---

홀수인 소수 [math(p)], [math(q)]에 대하여, 다음이 성립한다. 분수에 괄호를 씌운 것처럼 생긴 [math(\left(\dfrac{q}{p}\right))] 기호를 르장드르 기호라 하며, 이 기호의 의미에 대해서는 후술한다.

[math(\left(\dfrac{q}{p}\right)=\begin{cases} \left(\dfrac{p}{q}\right) & p \equiv 1 (\text{mod } 4) \text{ or } q \equiv 1 (\text{mod } 4) \\ -\left(\dfrac{p}{q}\right) & p \equiv 3 (\text{mod } 4) \text{ and } q \equiv 3 (\text{mod } 4) \end{cases})]

2. 이차잉여와 이차비잉여[편집]

---

홀수인 소수 [math(p)]에 대하여, 법 [math(p)]에 대한 이차잉여(quadratic residue modulo [math(p)])와 이차비잉여(quadratic nonresidue modulo [math(p)])를 다음과 정의할 수 있다. 정수 [math(a \left ( \not\equiv 0 \left(\text{mod } p \right) \right ))]에 대하여 다음을 만족시키는 정수 [math(b)]가 존재할 때, 정수 [math(a)]가 법 [math(p)]에 대한 이차잉여라 하며, 다음을 만족시키는 정수 [math(b)]가 존재하지 않을 때, 정수 [math(a)]가 법 [math(p)]에 대한 이차비잉여라 한다.[* [math(a \equiv 0 \left(\text{mod } p \right)), 즉, [math(a)]가 [math(p)]의 배수이면, [math(a)]는 법 [math(p)]에 대한 이차잉여도 이차비잉여도 아니다.]

[math(a \equiv b^2 \left(\text{mod } p \right))]

예를 들어, 22가 법 7에 대한 이차잉여인지 아닌지 확인해 보자. 우선 2가 7의 배수가 아님은 명백하고, 다음이 성립하므로, 2는 법 7에 대한 이차잉여이다.
[math(2 \equiv 3^2 \left(\text{mod } 7 \right))]

그러나 3은 법 7에 대한 이차잉여가 아니다. 1부터 6까지의 자연수를 제곱한 후 7로 나눈 나머지를 구하면 아래 표와 같은데, 이 중 3과 합동인 수가 없기 때문이다.

법 7에 대하여 1, 2, 4는 이차잉여이고, 3, 5, 6은 이차비잉여임을 알 수 있다. 여기에서 주목할 것은, 첫째로 위 표의 마지막 행에 나타난 수인 1, 4, 2, 2, 4, 1이 대칭적이라는 점이며, 둘째로 이로 인해 이차잉여와 이차비잉여의 수가 같다는 것이다. (물론 1≤a≤6의 범위에서.) 이를 요약하면 다음과 같다.

홀수인 소수 [math(p)]에 대하여, [math(1)]부터 [math(p-1)]까지의 정수 중 법 [math(p)]에 대한 이차잉여와 이차비잉여의 수는 각각 [math(\dfrac{p-1}{2})]이다.

증명 펼치기·접기

먼저, 앞서 그린 것과 비슷한 표를 그린다고 생각하자. 홀수인 소수 [math(p)]를 고정할 때, [math(b=k)]와 [math(b=p-k)]에 대하여 [math(k^2 \equiv (p-k)^2)]이므로 표의 대칭성을 확인할 수 있다. 따라서 표의 마지막 행에 나타나는 값의 개수(=이차잉여인 수의 개수)은 많아야 [math(\dfrac{p-1}{2})]이다.
다음으로, [math(1^2,~ 2^2,~ 3^2,~ … \left(\frac{p-1}{2}\right)^2)]이 법 [math(p)]에 대해 모두 다르다는 것을 확인하자. 즉 표의 마지막 행에 나타나는 값의 개수(=이차잉여인 수의 개수)이 정확하게 [math(\dfrac{p-1}{2})]임을 확인해 보자. 만일 [math(1)]부터 [math(\dfrac{p-1}{2})]까지의 자연수 중 서로 다른 두 수 [math(b_1,~b_2)]가 [math({b_1}^2 \equiv {b_2}^2 \left(\text{mod } p \right))]를 만족시킨다면, [math({b_1}^2 - {b_2}^2 \equiv 0 \left(\text{mod } p \right))]이다. 좌변을 인수분해하면 [math(\left(b_1+b_2\right)\left(b_1 - b_2 \right) \equiv 0 \left(\text{mod } p \right))]인데, 이때 [math(b_1,~ b_2)]는 [math(\dfrac{p-1}{2})] 이하의 자연수이므로, [math(2≤\left(b_1+b_2\right) < p )]가 되며, 이 값은 0과 합동일 수 없다. 또한 [math(1≤\left(b_1-b_2\right) < \dfrac{p-1}{2} )]이므로 이 수도 0과 합동일 수 없다. 법수가 소수일 때 0과 합동이 아닌 두 수를 곱하더라도 0과 합동이 되지 않으므로, 이는 모순이다. 따라서 이러한 [math(b_1,~b_2)]는 존재하지 않는다.
그러므로 홀수인 소수 [math(p)]에 대한 이차잉여의 개수는 [math(\dfrac{p-1}{2})]이며, 이차비잉여의 개수는 [math((p-1)-\dfrac{p-1}{2} = \dfrac{p-1}{2})]이다.

다른 예로, 법 11에 대한 경우를 살펴보자. 15는 법 11에 대하여 이차잉여일까? 즉, 제곱했을 때 15와 합동이 되는 정수가 있을까? 그런데 15는 법 11에 대하여 4와 합동이므로, 15가 법 11에 대하여 이차잉여인지 확인하는 것은 4가 법 7에 대하여 이차잉여인지 확인하는 것과 같다.
이므로, 4는 법 11에 대하여 이차잉여이고, 15 역시 그러하다.[1]

2.1. 르장드르 기호[편집]

---

정수 [math(a)]가 홀수인 소수 [math(p)]에 대해 이차잉여인 경우와 이차비잉여인 경우를 간단히 나타내기 위하여, 르장드르 기호(Lesendre symbol)를 사용한다. 정의는 다음과 같다.

[math(\left(\dfrac{a}{p}\right)=\begin{cases} 1 & a \text{가 법 } p \text{에 대한 이차잉여일 때 } \\ -1 & a \text{가 법 } p \text{에 대한 이차비잉여일 때 } \end{cases})]

앞 문단에서 살펴본 예에서, [math(\left(\dfrac{2}{7}\right)=1)], [math(\left(\dfrac{3}{7}\right)=-1)], [math(\left(\dfrac{15}{11}\right)=1)]이다.

르장드르 기호를 사용하는 것은 왜일까? 바로 합성수의 이차잉여 여부를 편리하게 판단하기 위해서인데, 가령 6이 법 [math(p)]에 대해 이차잉여인지 확인한다고 생각하자. 앞 문단에서 그린 것과 유사한 표를 그려서 해결할 수도 있지만, 1부터 [math(p-1)]까지의 수를 제곱한 후 [math(p)]로 나눈 나머지를 구해서 표를 그리는 것은 쉽지 않다. 그런데 [math(6=2 \times 3)]을 이용하면, 2와 3의 법 [math(p)]에 대한 이차잉여 여부를 확인하면 된다. 즉 합성수의 이차잉여 여부를 판단하기 위해서는, 소수의 이차잉여 여부만 판단하면 된다는 것이다. 그 방법은 아래와 같다.

먼저 2와 3이 모두 이차잉여라면, 6 역시 이차잉여일 것이다.[2]

한편 만일 2와 3 중 하나만 이차잉여라면, 6은 이차비잉여일 것이다.[3]